Click here for the entire procedure.

ECPP stands for Elliptic Curve Primality Proving.

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.

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

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

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

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.

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.

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

- Morain, F.
Easy numbers for the Elliptic Curve Primality Proving
algorithm.
In
- 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 ]

- Hanrot, G., and Morain, F.
Solvability by radicals from an algorithmic point of view.
In
- 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 ]

- Morain, F.
Building cyclic elliptic curves modulo large primes.
In

See also my web page for more articles.