(original) (raw)

The ECPP home page

Version française

General overview

ECPP is a package containing a primality proving program. It implements the algorithms described here.

Some primality proofs.

Frequently asked questions about ECPP

How do I get ECPP?

Click here for the entire procedure.

What does ECPP mean?

ECPP stands for Elliptic Curve Primality Proving.

Why do I need ECPP?

Proving the primality of a given integer is a basic task in number theory. You can also use the program to build primes for cryptographic reasons.

Why is ECPP superior to primality testing algorithms?

Ordinary primality testing algorithms, such as the Dubois-Selfridge-Miller-Rabin algorithm, halts with the answer

Yes, it is composite

I could not find any reason why this number should not be prime.

In the latter case, there is some probability of error, namely a composite number recognized as a prime. Primality proving algorithms give a proof of that fact, called a primality certificate.What is a primality certificate?

The program produces a long list of numbers that constitute the proof of primality for that number. In brief, a decreasing sequence of primes is built, the primality of the successor in the list implying that of the predecessor. This certificate can be checked either by the program checkcertif given in the package or by any other program any user can write for herself. Such a simple program is given in Maple.

Why is ECPP superior to other primality proving algorithms?

The only concurrent of ECPP is the Jacobi Sums test, of H. Cohen and H. W. Lenstra, Jr., as implemented for instance by H. Cohen and A. K. Lenstra. For them, primality boils down to a huge computation in a huge number ring. Proving primality or checking the certificate takes almost the same time and requires a careful implementation. For ECPP, the checking part can be done in polynomial time and in practice takes much less time than the program that builds the certificate. It is also very easy to program (give a look at the checkcertif.map program).

What are the largest numbers ever proved prime by your implementation of ECPP?

They are:

010903: 907^694+694^907 (2578 decimal digits) with ECPP-V11.0.5alpha.
010828: 903^376+376^903 (2326 decimal digits) with ECPP-V11.0.5alpha.
010727: 883^394+394^883 (2292 decimal digits) with ECPP-V11.0.5alpha.
(2^7331-1)/458072843161 (2196 decimal digits), found by E. Mayer and F. Morain with ECPP, october 1997, with one month of CPU on an Alpha 400MHz.
(2^5689-1) / 919724609777 (1701 decimal digits) by E. Mayer with my program with 150 hours on a 400 MHz Alpha, october 1997.
(2^5227-1) / (1129033 * 47126633 * 227482218017) (1549 digits) by E. Mayer.
(2^5087-1) / (40697 * 1678711 * 114097014833) (1510 digits) by E. Mayer.
p(1840926) (a 1505 decimal digit number containing the number of ways of writing 1840926 as a sum of nonnegative integers), computation done in 1992. Can ECPP really prove the primality of any number with less than 2578 decimal digits?

Of course! At least in theory. As a matter of fact, I have to be a bit more careful. The package contains a finite number of data that can be used to prove the primality of a number. In case of problem (hard numbers), these data will not be enough. This explains why the current version contains a backtracking mecanism. This will be explained elsewhere. In my experience, ECPP does not give up on numbers with less than 500 decimal digits. Anybody finding a counterexample is asked to send me such numbers.

Where can I find more information?

For (fast)ECPP
- Morain, F. Easy numbers for the Elliptic Curve Primality Proving algorithm. In ISSAC '92 (New York, 1992), P. S. Wang, Ed., ACM Press, pp. 263-268. Proceedings, July 27-29, Berkeley.
  [ bib | .ps.gz ]
- A. O. L. Atkin and François Morain. Elliptic curves and primality proving.Math. Comp., 61(203):29--68, July 1993.
- 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.
- Enge, A., and Morain, F. Comparing invariants for class fields of imaginary quadratic fields. In Algorithmic Number Theory (2002), C. Fieker and D. R. Kohel, Eds., vol. 2369 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 252-266. 5th International Symposium, ANTS-V, Sydney, Australia, July 2002, Proceedings.
  [ bib | .ps.gz ]
- Franke, J., Kleinjung, T., Morain, F., and Wirth, T. Proving the primality of very large numbers with fastecpp. In Algorithmic Number Theory (2004), D. Buell, Ed., vol. 3076 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 194-207. 6th International Symposium, ANTS-VI, Burlington, VT, USA, June 2004, Proceedings.
  [ bib | http ]
- Morain, F. Computing the cardinality of CM elliptic curves using torsion points.J. Th�or. Nombres Bordeaux 19, 3 (2007), 663-681.
  [ bib | .pdf ]
- Morain, F. Implementing the asymptotically fast version of the elliptic curve primality proving algorithm.Math. Comp. 76 (2007), 493-505.
  [ bib | .pdf ]
For the Galois theory used in ECPP
- Hanrot, G., and Morain, F. Solvability by radicals from an algorithmic point of view. In Symbolic and algebraic computation (2001), B. Mourrain, Ed., ACM, pp. 175-182. Proceedings ISSAC'2001, London, Ontario.
  [ bib | .ps.gz ]
- Enge, A., and Morain, F. Fast decomposition of polynomials with known Galois group. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (2003), M. Fossorier, T. Høholdt, and A. Poli, Eds., vol. 2643 of_Lecture Notes in Comput. Sci._, Springer-Verlag, pp. 254-264. 15th International Symposium, AAECC-15, Toulouse, France, May 2003, Proceedings.
  [ bib | .ps.gz | .ps.gz ]
For the CM method
- Morain, F. Building cyclic elliptic curves modulo large primes. In Advances in Cryptology - EUROCRYPT '91 (1991), D. Davies, Ed., vol. 547 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 328-336. Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques, Brighton, United Kingdom, April 8-11, 1991.
  [ bib ]
- Dupont, R., Enge, A., and Morain, F. Building curves with arbitrary small MOV degree over finite prime fields.J. of Cryptology 18, 2 (2005), 79-89.
  [ bib ]