Top

Published in:

2020 | OriginalPaper | Chapter

Faster Cofactorization with ECM Using Mixed Representations

Authors : Cyril Bouvier, Laurent Imbert

Published in: Public-Key Cryptography – PKC 2020

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper introduces a novel implementation of the elliptic curve factoring method specifically designed for medium-size integers such as those arising by billions in the cofactorization step of the Number Field Sieve. In this context, our algorithm requires fewer modular multiplications than any other publicly available implementation. The main ingredients are: the use of batches of primes, fast point tripling, optimal double-base decompositions and Lucas chains, and a good mix of Edwards and Montgomery representations.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Tight and Optimal Reductions for Signatures Based on Average Trapdoor Preimage Sampleable Functions and Applications to Code-Based Signatures

next chapter Improved Classical Cryptanalysis of SIKE in Practice

Available only for authorised users

This claim is also supported by our experiments with CADO-NFS modular arithmetic functions for 64-bit, 96-bit and 128-bit integers.

You may have observed that two of the given expansions do not satisfy the non-adjacent form, with two consecutive ones in their most significant positions. This is simply because evaluating 3P as \(4P -P\) is more expensive than \(2P+P\).

In this case a decreasing sequence since the parts are distincts.

There is a small mistake in the definition given in [9] which we were able to correct thanks to the examples following the definition.

Barbulescu, R., Bos, J.W., Bouvier, C., Kleinjung, T., Montgomery, P.: Finding ECM-friendly curves through a study of Galois properties. In: ANTS X: Proceedings of the Tenth Algorithmic Number Theory Symposium. Open Book Series, vol. 1, pp. 63–86 (2013). https://doi.org/10.2140/obs.2013.1.63

Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted edwards curves. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 389–405. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68164-9_26CrossRef

Bernstein, D.J., Birkner, P., Lange, T.: Starfish on strike. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010. LNCS, vol. 6212, pp. 61–80. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14712-8_4CrossRef

Bernstein, D.J., Birkner, P., Lange, T., Peters, C.: ECM using Edwards curves. Math. Comput. 82, 1139–1179 (2013)MathSciNetCrossRef

Bernstein, D.J., Birkner, P., Lange, T., Peters, C., et al.: EECM-MPFQ: ECM using Edwards curves. http://eecm.cr.yp.to/index.html

Bernstein, D.J., Chuengsatiansup, C., Lange, T.: Double-base scalar multiplication revisited. Cryptology ePrint Archive, Report 2017/037 (2017). https://eprint.iacr.org/2017/037

Bernstein, D.J., Lange, T.: Explicit-formulas database. http://www.hyperelliptic.org/EFD/. joint work by Daniel J. Bernstein and Tanja Lange, building on work by many authors

Bernstein, D.J., Lange, T.: A complete set of addition laws for incomplete Edwards curves. Cryptology ePrint Archive, Report 2009/580 (2009). https://eprint.iacr.org/2009/580

Bos, J.W., Kleinjung, T.: ECM at work. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 467–484. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_29CrossRef

10.

Castryck, W., Galbraith, S., Farashahi, R.R.: Efficient arithmetic on elliptic curves using a mixed Edwards-Montgomery representation. Cryptology ePrint Archive, Report 2008/218 (2008). https://eprint.iacr.org/2008/218

11.

Dimitrov, V., Imbert, L., Mishra, P.K.: Efficient and secure elliptic curve point multiplication using double-base chains. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 59–78. Springer, Heidelberg (2005). https://doi.org/10.1007/11593447_4CrossRef

12.

Dixon, B., Lenstra, A.K.: Massively parallel elliptic curve factoring. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 183–193. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-47555-9_16CrossRef

13.

Edwards, H.M.: A normal form for elliptic curves. Bull. Am. Math. Soc. 44, 393–422 (2007)MathSciNetCrossRef

14.

Hisil, H., Wong, K.K.-H., Carter, G., Dawson, E.: Twisted edwards curves revisited. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 326–343. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-89255-7_20CrossRef

15.

Ishii, M., Detrey, J., Gaudry, P., Inomata, A., Fujikawa, K.: Fast modular arithmetic on the Kalray MPPA-256 processor for an energy-efficient implementation of ECM. IEEE Transactions on Computers 66(12), 2019–2030 (2017). https://doi.org/10.1109/TC.2017.2704082, https://hal.inria.fr/hal-01299697

16.

Kleinjung, T., et al.: Factorization of a 768-Bit RSA modulus. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 333–350. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_18CrossRef

17.

Lenstra, A.K., Lenstra, H.W. (eds.): The Development of the Number Field Sieve. Lecture Notes in Mathematics, vol. 1554. Springer, Heidelberg (1993). https://doi.org/10.1007/BFb0091534CrossRefMATH

18.

Lenstra, H.W.: Factoring integers with elliptic curves. Ann. Math. 126(3), 649–673 (1987)MathSciNetCrossRef

19.

Meyer, M., Reith, S., Campos, F.: On hybrid SIDH schemes using Edwards and Montgomery curve arithmetic. Cryptology ePrint Archive, Report 2017/1213 (2017). https://eprint.iacr.org/2017/1213

20.

Miele, A.: On the analysis of public-key cryptologic algorithms. Ph.D. thesis, EPFL (2015)

21.

Montgomery, P.L.: Evaluating recurrences of form \({X}_{m+n}=f({X}_m,{X}_n,{X}_{m-n})\) via Lucas chains (1983, unpublished)

22.

Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Math. Comput. 48(177), 243–264 (1987)MathSciNetCrossRef

23.

Méloni, N., Hasan, M.A.: Elliptic curve scalar multiplication combining Yao’s algorithm and double bases. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 304–316. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04138-9_22CrossRef

24.

The CADO-NFS Development Team: CADO-NFS, an implementation of the number field Sieve algorithm (2017). http://cado-nfs.gforge.inria.fr/. release 2.3.0

25.

Yao, A.C.C.: On the evaluation of powers. SIAM J. Comput. 5(1), 100–103 (1976)MathSciNetCrossRef

26.

Zimmermann, P.: 50 largest factors found by ECM. https://members.loria.fr/PZimmermann/records/top50.html

27.

Zimmermann, P., Dodson, B.: 20 Years of ECM. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 525–542. Springer, Heidelberg (2006). https://doi.org/10.1007/11792086_37CrossRef

28.

Zimmermann, P., et al.: GMP-ECM (elliptic curve method for integer factorization). https://gforge.inria.fr/projects/ecm/

Title: Faster Cofactorization with ECM Using Mixed Representations
Authors: Cyril Bouvier
Laurent Imbert
Publisher: Springer International Publishing
Book: Public-Key Cryptography – PKC 2020
Print ISBN: 978-3-030-45387-9

Electronic ISBN: 978-3-030-45388-6

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-45388-6_17

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner