[1] It is an idea put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin in the same year.
The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and François Morain [de], in 1993.
[2] The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing (and proving) followed quickly.
Primality testing is a field that has been around since the time of Fermat, in whose time most algorithms were based on factoring, which become unwieldy with large input; modern algorithms treat the problems of determining whether a number is prime and what its factors are separately.
[3] Previously-known prime-proving methods such as the Pocklington primality test required at least partial factorization of
As a result, these methods required some luck and are generally slow in practice.
ECPP is currently in practice the fastest known algorithm for testing the primality of general numbers, but the worst-case execution time is not known.
ECPP works the same way as most other primality tests do, finding a group and showing its size is such that
For ECPP the group is an elliptic curve over a finite set of quadratic forms such that
The step that takes the most CPU time is the certificate generation, because factoring over a class field must be performed.
The certificate can be verified quickly, allowing a check of operation to take very little time.
[5] The certification was performed by Andreas Enge using his fastECPP software CM.
If the point-counting algorithm stops at an undefined expression this allows to determine a non-trivial factor of N. If it succeeds, we apply a criterion for deciding whether our curve E is acceptable.
[9][10] Atkin and Morain state "the problem with GK is that Schoof's algorithm seems almost impossible to implement.
However, the original algorithm by Schoof is not efficient enough to provide the number of points in short time.
[11] These comments have to be seen in the historical context, before the improvements by Elkies and Atkin to Schoof's method.
A second problem Koblitz notes is the difficulty of finding the curve E whose number of points is of the form kq, as above.
ECPP uses complex multiplication to construct the curve E, doing so in a way that allows for m (the number of points on E) to be easily computed.
We will now describe this method: Utilization of complex multiplication requires a negative discriminant, D, such that D can be written as the product of two elements
with complex multiplication (described in detail below), and the number of points is given by: For N to split into the two elements, we need that
Now if m has a prime factor q of size use the complex multiplication method to construct the curve E and a point P on it.
[1] For completeness, we will provide an overview of complex multiplication, the way in which an elliptic curve can be created, given our D (which can be written as a product of two elements).
It is necessary to calculate the elliptic j-invariants of the h(D) classes of the order of discriminant D as complex numbers.
This leads to a nested certificate where at each level we have an elliptic curve E, an m and the prime in doubt, q.
Goldwasser and Kilian's elliptic curve primality proving algorithm terminates in expected polynomial time for at least of prime inputs.
If one accepts this conjecture then the Goldwasser–Kilian algorithm terminates in expected polynomial time for every input.
[14] Now consider another conjecture, which will give us a bound on the total time of the algorithm.
such that the amount of primes in the interval Then the Goldwasser Kilian algorithm proves the primality of N in an expected time of For the Atkin–Morain algorithm, the running time stated is For some forms of numbers, it is possible to find 'short-cuts' to a primality proof.
Of course this will also provide a method for proving primality of Mersenne numbers, which correspond to the case where n = 1.
In (1), an elliptic curve, E is picked, along with a point Q on E, such that the x-coordinate of Q is a quadratic nonresidue.