Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

Author: F. Morain
Journal: Math. Comp. 76 (2007), 493-505
MSC (2000): Primary 11Y11, 11A51, 11G15, 11G20
Published electronically: September 1, 2006
MathSciNet review: 2261033
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

References [Enhancements On Off] (What's this?)

Similar Articles

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

Retrieve articles in all journals with MSC (2000): 11Y11, 11A51, 11G15, 11G20

Additional Information

F. Morain
Affiliation: LIX École Polytechnique, CNRS/UMR 7161, INRIA/Futurs, F-91128 Palaiseau Cedex, France

Keywords: Primality proving, elliptic curves, ECPP algorithm.
Received by editor(s): January 27, 2005
Received by editor(s) in revised form: October 24, 2005
Published electronically: 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.
Article copyright: © Copyright 2006 by the author