Elliptic curve primality proving Information & Elliptic curve primality proving Links at HealthHaven.com

Elliptic Curve Primality Proving (ECPP) is a method based on elliptic curves to prove the primality of a number. It is a general-purpose algorithm, meaning it does not depend on the number being 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:^[1]

$O((\log n)^{5+\epsilon})\,$

for some $ε > 0$ . This exponent may be decreased to $4 + ε$ for some versions by heuristic arguments. This exponent is less than that of the AKS method. ECPP works the same way as most other primality tests do, finding a group and showing its size is such that $p$ is prime. For ECPP the group is an elliptic curve over a finite set of quadratic forms such that $p - 1$ 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.

As of April 2008^[update] the largest prime that has been proved with ECPP is the 20,562-digit Mills' prime:^[2]^[3]

(((((((((2 3 + 3) 3 + 30) 3 + 6) 3 + 80) 3 + 12) 3 + 450) 3 + 894) 3 + 3636) 3 + 70756) 3 + 97220.

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 Processor 250 at 2.39 GHz for 2219 days (near 6 years).^[4]

[edit] References

^ Lenstra, Jr., A. K.; Lenstra, Jr., H. W. (1990). "Algorithms in number theory". Handbook of Theoretical Computer Science: Algorithms and Complexity (Amsterdam and New York: The MIT Press) A: 673–715.
^ Martin, Marcel. ECPP records (multiprocessor). Retrieved on 2007-06-09.
^ Caldwell, Chris. The Top Twenty: Elliptic Curve Primality Proof from the Prime Pages. Retrieved on 2007-06-09.
^ Morain, François (2006-06-05). "A new prime". NMBRTHRY mailing list. http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0606&L=nmbrthry&T=0&P=159. Retrieved 2007-06-09.

[edit] External links

Elliptic Curves and Primality Proving by Atkin and Morain.
Weisstein, Eric W., "Elliptic Curve Primality Proving" from MathWorld.
Chris Caldwell, "Primality Proving 4.2: Elliptic curves and the ECPP test" at the Prime Pages.
François Morain, "The ECPP home page" (includes old ECPP software for some architectures).
Marcel Martin, "Primo" (Windows implementation).
LiDIA - a semi-free library with ECPP

This number theory-related article is a stub. You can help Wikipedia by expanding it.

[Lenstra-0] Lenstra, Jr., A. K.; Lenstra, Jr., H. W. (1990). "Algorithms in number theory". Handbook of Theoretical Computer Science: Algorithms and Complexity (Amsterdam and New York: The MIT Press) A: 673–715.

[1] Martin, Marcel. ECPP records (multiprocessor). Retrieved on 2007-06-09.

[2] Caldwell, Chris. The Top Twenty: Elliptic Curve Primality Proof from the Prime Pages. Retrieved on 2007-06-09.

[3] Morain, François (2006-06-05). "A new prime". NMBRTHRY mailing list. http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0606&L=nmbrthry&T=0&P=159. Retrieved 2007-06-09.

[1]

[2]

[3]

[4]