Mathematics of Computation

Implementing the asymptotically fast version of the elliptic curve primality proving algorithm

Author(s): F. Morain.
Journal: Math. Comp. 76 (2007), 493-505.
MSC (2000): Primary 11Y11, 11A51, 11G15, 11G20
Posted: September 1, 2006
Retrieve article in: PDF

Abstract: The elliptic curve primality proving (ECPP) algorithm is one of the current fastest practical algorithms for proving the primality of large numbers. Its running time currently cannot be proven rigorously, but heuristic arguments show that it should run in time $\tilde{O}((\log N)^5)$ to prove the primality of

. An asymptotically fast version of it, attributed to J. O. Shallit, is expected to run in time $\tilde{O}((\log N)^4)$ . We describe this version in more detail, leading to actual implementations able to handle numbers with several thousands of decimal digits.

1.: L. M. Adleman, C. Pomerance, and R. S. Rumely.
On distinguishing prime numbers from composite numbers.
Ann. of Math. (2), 117(1):173-206, 1983. MR 0683806 (84e:10008)
2.: M. Agrawal, N. Kayal, and N. Saxena.
PRIMES is in P.
Ann. of Math. (2), 160(2):781-793, 2004. MR 2123939 (2006a:11170)
3.: A. O. L. Atkin and F. Morain.
Elliptic curves and primality proving.
Math. Comp., 61(203):29-68, July 1993. MR 1199989 (93m:11136)
4.: M. Ayad.
Points -entiers des courbes elliptiques.
Manuscripta Math., 76(3-4):305-324, 1992. MR 1185022 (93i:11064)
5.: D. Bernstein.
Proving primality after Agrawal-Kayal-Saxena.
http://cr.yp.to/papers /aks.ps, January 2003.
6.: D. Bernstein.
Proving primality in essentially quartic expected time.
http://cr.yp.to /papers/quartic.ps, January 2003.
7.: P. Berrizbeitia.
Sharpening ``Primes is in P" for a large family of numbers.
Math. Comp., 74(252):2043-2059, 2005. MR 2164112 (2006e:11191)
8.: R. Bröker and P. Stevenhagen.
Elliptic curves with a given number of points.
In D. Buell, editor, Algorithmic Number Theory, volume 3076 of Lecture Notes in Comput. Sci., pages 117-131. Springer-Verlag, 2004.
6th International Symposium, ANTS-VI, Burlington, VT, USA, June 2004, Proceedings.MR 2137348 (2005m:11113)
9.: Q. Cheng.
Primality proving via one round in ECPP and one iteration in AKS.
In D. Boneh, editor, Advances in Cryptology - CRYPTO 2003, volume 2729 of Lecture Notes in Comput. Sci., pages 338-348. Springer Verlag, 2003.MR 2093202 (2005e:68088)
10.: H. Cohen and H. W. Lenstra, Jr.
Heuristics on class groups of number fields.
In H. Jager, editor, Number Theory, Noordwijkerhout 1983, volume 1068 of Lecture Notes in Math., pages 33-62. Springer-Verlag, 1984.
Proc. of the Journées Arithmétiques 1983, July 11-15. MR 0756082 (85j:11144)
11.: H. Cohen and H. W. Lenstra, Jr.
Primality testing and Jacobi sums.
Math. Comp., 42(165):297-330, 1984. MR 0726006 (86g:11078)
12.: J.-M. Couveignes and T. Henocq.
Action of modular correspondences around CM points.
In C. Fieker and D. R. Kohel, editors, Algorihmic Number Theory, volume 2369 of Lecture Notes in Comput. Sci., pages 234-243. Springer-Verlag, 2002.
5th International Symposium, ANTS-V, Sydney, Australia, July 2002, Proceedings.MR 2041087 (2005b:11077)
13.: D. A. Cox.
Primes of the form .
John Wiley & Sons, 1989.MR 1028322 (90m:11016)
14.: R. Crandall and C. Pomerance.
Prime numbers - A Computational Perspective.
Springer-Verlag, 2000.MR 1821158 (2002a:11007)
15.: A. Enge.
The complexity of class polynomial computations via floating point approximations.
Preprint, February 2004.
16.: A. Enge and F. Morain.
Comparing invariants for class fields of imaginary quadratic fields.
In C. Fieker and D. R. Kohel, editors, Algorithmic Number Theory, volume 2369 of Lecture Notes in Comput. Sci., pages 252-266. Springer-Verlag, 2002.
5th International Symposium, ANTS-V, Sydney, Australia, July 2002, Proceedings.MR 2041089 (2005a:11179)
17.: A. Enge and F. Morain.
Fast decomposition of polynomials with known Galois group.
In M. Fossorier, T. Høholdt, and A. Poli, editors, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, volume 2643 of Lecture Notes in Comput. Sci., pages 254-264. Springer-Verlag, 2003.
15th International Symposium, AAECC-15, Toulouse, France, May 2003, Proceedings.MR 2043632 (2005b:12007)
18.: A. Enge and R. Schertz.
Modular curves of composite level.
Acta Arith., 181(2):129-141, 2005. MR 2141046 (2006a:11074)
19.: A. Enge and P. Zimmermann.
mpc -- a library for multiprecision complex arithmetic with exact rounding, 2002.
Version 0.4.1, available from http://www.lix.polytechnique.fr/Labo/Andreas.Enge.
20.: J. Franke, T. Kleinjung, F. Morain, and T. Wirth.
Proving the primality of very large numbers with fastecpp.
In D. Buell, editor, Algorithmic Number Theory, volume 3076 of Lecture Notes in Comput. Sci., pages 194-207. Springer-Verlag, 2004.
6th International Symposium, ANTS-VI, Burlington, VT, USA, June 2004, Proceedings.MR 2137354 (2006a:11172)
21.: J. Franke, T. Kleinjung, F. Morain, and T. Wirth.
A new large primality proof using fastecpp.
http://listserv.nodak.edu/archives/nmbrthry.html, July 2004.
22.: W. F. Galway.
Analytic computation of the prime-counting function.
Ph.D. thesis, University of Urbana-Champaign, 2004.
http://www.math.uiuc.edu/~galway/PhD_Thesis/.
23.: J. von zur Gathen and J. Gerhard.
Modern Computer Algebra.
Cambridge University Press, 1999. MR 1689167 (2000j:68205)
24.: A. Gee.
Class invariants by Shimura's reciprocity law.
J. Théor. Nombres Bordeaux, 11:45-72, 1999. MR 1730432 (2000i:11171)
25.: A. Gee and P. Stevenhagen.
Generating class fields using Shimura reciprocity.
In J. P. Buhler, editor, Algorithmic Number Theory, volume 1423 of Lecture Notes in Comput. Sci., pages 441-453. Springer-Verlag, 1998.
Third International Symposium, ANTS-III, Portland, Oregon, June 1998, Proceedings.MR 1726092 (2000m:11112)
26.: GNU.
The GNU Multiple Precision arithmetic library.
Available from http://www.swox.com/gmp/.
27.: S. Goldwasser and J. Kilian.
Primality testing using elliptic curves.
Journal of the ACM, 46(4):450-472, July 1999. MR 1812127 (2002e:11182)
28.: G. Hanrot, V. Lefèvre, and P. Zimmermann et. al.
mpfr -- a library for multiple-precision floating-point computations with exact rounding, 2002.
Version contained in GMP. Available from http://www.mpfr.org.
29.: G. Hanrot and F. Morain.
Solvability by radicals from an algorithmic point of view.
In B. Mourrain, editor, Symbolic and algebraic computation, pages 175-182. ACM, 2001.
Proceedings ISSAC'2001, London, Ontario. MR 2049746 (2005a:11200)
30.: A. K. Lenstra and H. W. Lenstra, Jr.
Algorithms in number theory.
In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity, chapter 12, pages 674-715. North-Holland, 1990.MR 1127178
31.: H. W. Lenstra, Jr. and C. Pomerance.
Primality testing with Gaussian periods.
Preprint. Available as http://www.math.dartmouth.edu/~carlp/PDF/complexity072805.pdf, July 2005.
32.: Stéphane Louboutin.
Computation of class numbers of quadratic number fields.
Math. Comp., 71(240):1735-1743 (electronic), 2002. MR 1933052 (2003i:11163)
33.: P. Mihailescu.
Fast convolutions meet Montgomery.
Preprint, March 2004.
34.: P. Mihailescu and R. Avanzi.
Efficient quasi-deterministic primality test improving AKS.
Available from http://www-math.uni-paderborn.de/~preda/papers/myaks1.ps, April 2003.
35.: F. Morain.
Primality proving using elliptic curves: an update.
In J. P. Buhler, editor, Algorithmic Number Theory, volume 1423 of Lecture Notes in Comput. Sci., pages 111-127. Springer-Verlag, 1998.
Third International Symposium, ANTS-III, Portland, Oregon, June 1998, Proceedings.MR 1726064 (2000i:11190)
36.: F. Morain.
La primalité en temps polynomial [d'après Adleman, Huang ; Agrawal, Kayal, Saxena].
Astérisque, pages Exp. No. 917, ix, 205-230, 2004.
Séminaire Bourbaki. Vol. 2002/2003. MR 2111645 (2005h:11275)
37.: W. Narkiewicz.
Elementary and analytic theory of algebraic numbers.
PWN-Polish Scientific Publishers, 1974. MR 0347767 (50:268)
38.: A. Nitaj.
L'algorithme de Cornacchia.
Exposition. Math., 13:358-365, 1995. MR 1358213 (97a:11044)
39.: R. Schertz.
Weber's class invariants revisited.
J. Théor. Nombres Bordeaux, 14:325-343, 2002. MR 1926005 (2003j:11139)

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y11, 11A51, 11G15, 11G20

F. Morain
Affiliation: LIX École Polytechnique, CNRS/UMR 7161, INRIA/Futurs, F-91128 Palaiseau Cedex, France
Email: morain@lix.polytechnique.fr

DOI: 10.1090/S0025-5718-06-01890-4
PII: S 0025-5718(06)01890-4
Keywords: Primality proving, elliptic curves, ECPP algorithm.
Received by editor(s): January 27, 2005
Received by editor(s) in revised form: October 24, 2005
Posted: September 1, 2006
Additional Notes: Projet TANC, Pôle Commun de Recherche en Informatique du Plateau de Saclay, CNRS, École polytechnique, INRIA, Université Paris-Sud. The author is on leave from the French Department of Defense, Délégation Générale pour l'Armement.
Copyright of article: Copyright 2006, by the author

			Journals Home Search Author Info Subscribe Tech Support Help
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


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS