- Elliptic curve primality proving
Elliptic Curve Primality Proving (ECPP) is a method based on
elliptic curves to prove the primality of a number. It is a general-purposealgorithm , 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 theworst-case execution time is not known. ECPP heuristically runs in time:cite journal|last=Lenstra, Jr.|first=A. K.|coauthors=Lenstra, Jr., H. W.|title=Algorithms in number theory|journal=Handbook of Theoretical Computer Science: Algorithms and Complexity|volume=A|publisher=The MIT Press|location=Amsterdam and New York|pages=673–715|year=1990] :O((ln n)^{5+epsilon})for some epsilon > 0. This exponent may be decreased to 4+epsilon for some versions by
heuristic arguments. This exponent is less than that of the AKS method. ECPP works the same way as most otherprimality test s 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 divide and conquer and thenattempts to verify the certificate. The step that takes the most
CPU time is the certificate generation, because factoring over aclass field must be performed. The certificate can be verified quickly, allowing a check of operation to take very little time.As of April 2008 the largest prime that has been proved with ECPP is the 20,562-digitMills' prime : [Martin, Marcel. [http://www.ellipsa.net/primo/record.html#03 "ECPP records (multiprocessor)"] . Retrieved on2007-06-09 .] [Caldwell, Chris. [http://primes.utm.edu/top20/page.php?id=27 "The Top Twenty: Elliptic Curve Primality Proof"] from thePrime Pages . Retrieved on2007-06-09 .] :2^3+3)^3+30)^3+6)^3+80)^3+12)^3+450)^3+894)^3+3636)^3+70756)^3+97220The distributed computation with software byFrançois Morain started inSeptember 2005 and ended inJune 2006 . The cumulated time corresponds to oneAMD Opteron Processor 250 at 2.39 GHz for 2219 days (near 6 years). [cite mailing list |url=http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0606&L=nmbrthry&T=0&P=159 |title=A new prime |date=2006-06-05 |accessdate=2007-06-09 |mailinglist=NMBRTHRY |last=Morain |first=François |authorlink= ]References
External links
* [http://citeseer.ist.psu.edu/rd/9227084%2C72628%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/papers/cs/426/ftp:zSzzSzftp.inria.frzSzINRIAzSzpublicationzSzpubli-ps-gzzSzRRzSzRR-1256.pdf/atkin93elliptic.pdf Elliptic Curves and Primality Proving] by Atkin and Morain.
*MathWorld|urlname=EllipticCurvePrimalityProving|title=Elliptic Curve Primality Proving
*Chris Caldwell, [http://primes.utm.edu/prove/prove4_2.html "Primality Proving 4.2: Elliptic curves and the ECPP test"] at thePrime Pages .
*François Morain, [http://www.lix.polytechnique.fr/~morain/Prgms/ecpp.english.html "The ECPP home page"] (includes old ECPP software for some architectures).
*Marcel Martin, [http://www.ellipsa.net/public/primo/index.html "Primo"] (Windows implementation).
Wikimedia Foundation. 2010.