Elliptic Curve Primality Proving (ECPP) is a method based on elliptic curves to prove the primality of a number (see Elliptic curve primality testing). It is a general-purpose algorithm, meaning it does not depend on the number being of a special form. 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 heuristically runs in time:
for some . This exponent may be decreased to for some versions by heuristic arguments. ECPP works the same way as most other primality tests do, finding a group and showing its size is such that is prime. For ECPP the group is an elliptic curve over a finite set of quadratic forms such that is trivial to factor over the group.
ECPP generates an Atkin-Goldwasser-Kilian-Morain certificate of primality by recursion and then attempts to verify the certificate. 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.
In 2006 the largest prime that has been proved with ECPP is the 20,562-digit Mills' prime:
The distributed computation with software by François Morain started in September 2005 and ended in June 2006. The cumulated time corresponds to one AMD Opteron 250 processor at 2.39 GHz for 2219 days (near 6 years).
As of 2011 the largest prime that has been proved with ECPP is the 26,642-digits LR prime. The distributed computation with software by François Morain started in January 2011 and ended in April 2011. The cumulated time corresponds to one processor for 2255 days (more than 6 years).
Famous quotes containing the words curve and/or proving:
“Nothing ever prepares a couple for having a baby, especially the first one. And even baby number two or three, the surprises and challenges, the cosmic curve balls, keep on coming. We can’t believe how much children change everything—the time we rise and the time we go to bed; the way we fight and the way we get along. Even when, and if, we make love.”
—Susan Lapinski (20th century)
“One can prove or refute anything at all with words. Soon people will perfect language technology to such an extent that they’ll be proving with mathematical precision that twice two is seven.”
—Anton Pavlovich Chekhov (1860–1904)