Available in electronic format
Available in print format		 Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

Factorization with genus 2 curves

Author(s): Romain Cosset.
Journal: Math. Comp.
MSC (2000): Primary 11Y05; Secondary 11Y16, 11Y40
Posted: August 20, 2009
Retrieve article in: PDF

Abstract | References | Similar articles | Additional information

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:

1.
D. J. Bernstein, P. Birkner, T. Lange, and C. Peters, ECM using Edwards curves, Cryptology ePrint Archive, 2008, http://eprint.iacr.org/2008/016.

2.
S. Duquesne, Improving the arithmetic of elliptic curve in the Jacobi model, Inform. Process. Lett. 104 (2007), 101-105. MR 2348218 (2008h:94055)

3.
P. Gaudry, Fast genus $ 2$ arithmetic based on theta functions, J. Math. Cryptol. 1 (2007), 243-265. MR 2372155 (2009f:11156)

4.
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 (S. Boztaş and I. Shparlinski, eds.), Lecture Notes in Comput. Sci., vol. 2227, Springer-Verlag, 2001, pp. 373-386. MR 1913484 (2003e:14020)

5.
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.

6.
H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649-673. MR 916721 (89g:11125)

7.
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.

8.
-, Speeding the Pollard and Elliptic Curve Methods of Factorization, Math. Comp. 48 (1987), no. 177, 243-264. MR 866113 (88e:11130)

9.
D. Mumford, Tata lectures on theta. I, Progr. Math., vol. 28, Birkhäuser, 1983. MR 688651 (85h:14026)

10.
-, Tata lectures on theta. II, Progr. Math., vol. 43, Birkhäuser, 1984. MR 742776 (86b:14017)

11.
T. Shaska, Genus $ 2$ curves covering elliptic curves, a computational approach, Lecture Notes Ser. Comput. 13 (2005), 151-195. MR 2182041 (2006g:14051)

12.
P. van Wamelen, Equations for the Jacobian of a hyperelliptic curve, Trans. Amer. Math. Soc. 350 (1998), no. 8, 3083-3106. MR 1432144 (98k:14038)

13.
P. Zimmermann and B. Dodson, 20 years of ECM, Algorithmic Number Theory Symposium VII, Lecture Notes in Comput. Sci., vol. 4076, Springer-Verlag, 2006, pp. 525-542. MR 2282947 (2007j:11172)

Similar Articles:

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y05, 11Y16, 11Y40

Retrieve articles in all Journals with MSC (2000): 11Y05, 11Y16, 11Y40

Additional Information:

Romain Cosset
Affiliation: LORIA, Campus Scientifique - BP 239, 54506 Vandoeuvre-lès-Nancy, France
Email: romain.cosset@loria.fr

DOI: 10.1090/S0025-5718-09-02295-9
PII: S 0025-5718(09)02295-9
Received by editor(s): February 10, 2009
Received by editor(s) in revised form: April 4, 2009
Posted: August 20, 2009
Copyright of article: Copyright 2009, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google