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

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:

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?

See also my web page for more articles.