Factorization with genus 2 curves

Cosset, Romain

doi:10.1090/S0025-5718-09-02295-9

Factorization with genus 2 curves
HTML articles powered by AMS MathViewer

by Romain Cosset PDF

Math. Comp. 79 (2010), 1191-1208 Request permission

Abstract:

The elliptic curve method (ECM) is one of the best factorization methods available. It is possible to use hyperelliptic curves instead of elliptic curves but it is in theory slower. We use special hyperelliptic curves and Kummer surfaces to reduce the complexity of the algorithm. Our implementation GMP-HECM is faster than GMP-ECM for factoring large numbers.

References

D. J. Bernstein, P. Birkner, T. Lange, and C. Peters, ECM using Edwards curves, Cryptology ePrint Archive, 2008, http://eprint.iacr.org/2008/016.
Sylvain Duquesne, Improving the arithmetic of elliptic curves in the Jacobi model, Inform. Process. Lett. 104 (2007), no. 3, 101–105. MR 2348218, DOI 10.1016/j.ipl.2007.05.012
P. Gaudry, Fast genus 2 arithmetic based on theta functions, J. Math. Cryptol. 1 (2007), no. 3, 243–265. MR 2372155, DOI 10.1515/JMC.2007.012
P. Gaudry and É. Schost, On the invariants of the quotients of the Jacobian of a curve of genus 2, Applied algebra, algebraic algorithms and error-correcting codes (Melbourne, 2001) Lecture Notes in Comput. Sci., vol. 2227, Springer, Berlin, 2001, pp. 373–386. MR 1913484, DOI 10.1007/3-540-45624-4_{3}9
A. Kruppa, Factoring into large primes with $P-1$, $P+1$ and ECM, 2008, Available at http://cado.gforge.inria.fr/workshop/slides/kruppa.pdf.
H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
P. L. Montgomery, Evaluating recurrences of form $x_{m+n}=f\left (x_{m},x_{n},x_{m-n}\right )$ via Lucas chains, 1983, Available at ftp.cwi.nl/pub/pmontgom/Lucas.ps.gz.
Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243–264. MR 866113, DOI 10.1090/S0025-5718-1987-0866113-7
David Mumford, Tata lectures on theta. I, Progress in Mathematics, vol. 28, Birkhäuser Boston, Inc., Boston, MA, 1983. With the assistance of C. Musili, M. Nori, E. Previato and M. Stillman. MR 688651, DOI 10.1007/978-1-4899-2843-6
David Mumford, Tata lectures on theta. II, Progress in Mathematics, vol. 43, Birkhäuser Boston, Inc., Boston, MA, 1984. Jacobian theta functions and differential equations; With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman and H. Umemura. MR 742776, DOI 10.1007/978-0-8176-4578-6
T. Shaska, Genus two curves covering elliptic curves: a computational approach, Computational aspects of algebraic curves, Lecture Notes Ser. Comput., vol. 13, World Sci. Publ., Hackensack, NJ, 2005, pp. 206–231. MR 2182041, DOI 10.1142/9789812701640_{0}013
Paul van Wamelen, Equations for the Jacobian of a hyperelliptic curve, Trans. Amer. Math. Soc. 350 (1998), no. 8, 3083–3106. MR 1432144, DOI 10.1090/S0002-9947-98-02056-X
Paul Zimmermann and Bruce Dodson, 20 years of ECM, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 4076, Springer, Berlin, 2006, pp. 525–542. MR 2282947, DOI 10.1007/11792086_{3}7