Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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

François Morain 1
1 TANC - Algorithmic number theory for cryptology
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
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 cannot be proven rigorously, but heuristic arguments show that it should run in time O ((log N)^5) to prove the primality of N. An asymptotically fast version of it, attributed to J. O. Shallit, runs in time O ((log N)^4). The aim of this article is to describe this version in more details, leading to actual implementations able to handle numbers with several thousands of decimal digits.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00004136
Contributor : François Morain <>
Submitted on : Friday, February 4, 2005 - 5:29:30 PM
Last modification on : Thursday, March 5, 2020 - 6:20:28 PM
Long-term archiving on: : Friday, September 17, 2010 - 6:32:07 PM

Identifiers

Collections

Citation

François Morain. Implementing the asymptotically fast version of the elliptic curve primality proving algorithm. 2005. ⟨hal-00004136v2⟩

Share

Metrics

Record views

556

Files downloads

562