What is elliptic curve primality testing?

Elliptic curve primality testing, or elliptic curve primality proving (ECPP), is one of the quickest and most widely used methods to determine whether a large number is prime. Unlike older methods that required factoring N-1 or N+1, ECPP bypasses this difficulty and produces a quickly verifiable certificate of primality. The fundamental concepts were proposed by Shafi Goldwasser and Joe Kilian in 1986, and turned into a working algorithm by A. O. L. Atkin later that year.

What we know

• Elliptic curve primality testing techniques are among the quickest and most widely used methods in primality proving. [2]
• The core idea of ECPP was put forward by Shafi Goldwasser and Joe Kilian in 1986, and turned into an algorithm by A. O. L. Atkin that same year. [2]
• Older prime-proving methods like Pocklington's required partial factorization of N-1, making them slow and dependent on luck in practice. [2, 4]
• The elliptic curve test proves primality or compositeness with a quickly verifiable certificate. [2]

Where to go next

• whoWho were Shafi Goldwasser and Joe Kilian?
• compared withHow does the Miller-Rabin primality test work?
• what caused itWhy is integer factorization computationally difficult?
• a case in pointWhat is the Pocklington n-1 primality test?
• what followedHow are prime numbers applied in modern cryptography?
• an unexpected connectionHow does elliptic curve cryptography connect to primality proving?The mathematical tools built on elliptic curves are vital both for securing digital communications and for efficiently proving that huge numbers are prime.

Sources

• [1]elliptic curve primality proving (Wikidata Q3611581) · CC0 1.0
• [2]Elliptic curve primality · CC BY-SA 4.0
• [3]Primality test · CC BY-SA 4.0
• [4]Pocklington n − 1 primality test · CC BY-SA 4.0
• [5]Prime number · CC BY-SA 4.0