The ECPP home page
Version française
General overview
ECPP is a package containing a primality proving program. It
implements the algorithms described here.
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
DuboisSelfridgeMillerRabin algorithm, halts with the answer
Yes, it is composite
or
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 ECPPV11.0.5alpha.
 010828: 903^376+376^903 (2326 decimal digits) with ECPPV11.0.5alpha.
 010727: 883^394+394^883 (2292 decimal digits) with ECPPV11.0.5alpha.
 (2^73311)/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^56891) / 919724609777 (1701 decimal digits)
by E. Mayer with my program with
150 hours on a 400 MHz Alpha, october 1997.
 (2^52271) / (1129033 * 47126633 * 227482218017) (1549
digits) by E. Mayer.
 (2^50871) / (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

A. O. L. Atkin and François Morain.
Elliptic curves and primality proving.
Math. Comp., 61(203):2968, 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 111127. SpringerVerlag,
1998. Third International Symposium, ANTSIII, 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.,
SpringerVerlag, pp. 252266.
5th International Symposium, ANTSV, 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., SpringerVerlag, pp. 194207.
6th International Symposium, ANTSVI, 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), 663681.
[ bib 
.pdf ]
 Morain, F.
Implementing the asymptotically fast version of the elliptic curve
primality proving algorithm.
Math. Comp. 76 (2007), 493505.
[ 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. 175182.
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 ErrorCorrecting
Codes (2003), M. Fossorier, T. Høholdt, and A. Poli, Eds., vol. 2643 of
Lecture Notes in Comput. Sci., SpringerVerlag, pp. 254264.
15th International Symposium, AAECC15, Toulouse, France, May 2003,
Proceedings.
[ bib 
.ps.gz 
.ps.gz ]
 For the CM method
 Dupont, R., Enge, A., and Morain, F.
Building curves with arbitrary small MOV degree over finite prime
fields.
J. of Cryptology 18, 2 (2005), 7989.
[ bib ]
See also my web page for more articles.