In mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin in the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and François Morain [de], in 1993. The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing (and proving) followed quickly.

Primality testing is a field that has been around since the time of Fermat, in whose time most algorithms were based on factoring, which become unwieldy with large input; modern algorithms treat the problems of determining whether a number is prime and what its factors are separately. It became of practical importance with the advent of modern cryptography. Although many current tests result in a probabilistic output (N is either shown composite, or probably prime, such as with the Baillie–PSW primality test or the Miller–Rabin test), the elliptic curve test proves primality (or compositeness) with a quickly verifiable certificate.

Previously-known prime-proving methods such as the Pocklington primality test required at least partial factorization of ${\displaystyle N\pm 1}$ in order to prove that ${\displaystyle N}$ is prime. As a result, these methods required some luck and are generally slow in practice.

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. The fastest variant executes in Õ(L⁴) time, where ${\displaystyle L=\left\lceil {\log _{2}{n}}\right\rceil }$ is the bit-length of the number to be tested. Parallization is possible for all steps to L cores so the wall-clock time is actually around Õ(L³).

ECPP works the same way as most other primality tests do, finding a group and showing its size is such that ${\displaystyle p}$ is prime. For ECPP the group is an elliptic curve over a finite set of quadratic forms such that ${\displaystyle 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 November 2025^[update], the largest prime that has been proved with ECPP method is R(109297) = ${\displaystyle (10^{109297}-1)/9}$, a repunit of 109297 digits. The certification was performed Paul Underwood using Andreas Enge's fastECPP software CM. It was submitted in May 2025. Enge himself has set a few records using his software, which he details on his software website.

The elliptic curve primality tests are based on criteria analogous to the Pocklington criterion, on which that test is based, where the group ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ is replaced by ${\displaystyle E(\mathbb {Z} /n\mathbb {Z} ),}$ and E is a properly chosen elliptic curve. We will now state a proposition on which to base our test, which is analogous to the Pocklington criterion, and gives rise to the Goldwasser–Kilian–Atkin form of the elliptic curve primality test.