# Elliptic curve primality proving

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:[1]

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

for some $\varepsilon > 0$. This exponent may be decreased to $4+\varepsilon$ 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 $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 2011 the largest prime [2] that has been proved with ECPP method is the 26,643-digits prime value of the Ramanujan tau function: [3]

$LR(157,2207) = \tau\left(157^{2206}\right).$

The distributed computation with fastECPP software by François Morain started in January 2011 and ended in April 2011. The total CPU time is equal to 2355 days.[4]

## References

1. ^ 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.
2. ^ Caldwell, Chris. The Top Twenty: Elliptic Curve Primality Proof from the Prime Pages.
3. ^ Lygeros N., Rozier O. (2013). "Odd prime values of the Ramanujan tau function". Ramanujan Journal. doi:10.1007/s11139-012-9420-8.
4. ^ Morain F. Some primes proven by my programs.