Elliptic curve primality

Elliptic curve primality proving, usually shortened to ECPP, is a family of methods that use the arithmetic of elliptic curves to prove that a large number is prime rather than merely probably prime. The idea was put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into a working algorithm by A. O. L. Atkin in the same year, with later improvements by Atkin and Francois Morain in 1993. The method builds on the earlier Pocklington n minus 1 and Morrison n plus 1 tests, which needed partial factorisation of numbers next to the candidate, and replaces the multiplicative group of integers with the group of points on a suitably chosen elliptic curve. It works recursively and produces a certificate of primality that can be checked quickly even though generating it is the costly step. ECPP is a general-purpose method that needs no special form of number, and it is in practice the fastest known way to prove the primality of general numbers, although its worst-case running time is not known.