What is a primality test?

A primality test is an algorithm used to determine whether a given input number is prime. Unlike integer factorization, these tests generally do not reveal prime factors, but instead state whether the number is prime or composite. While some tests provide absolute mathematical proof, others are probabilistic and rely on statistical methods.

What we know

• Primality tests are algorithms used to determine whether an input number is prime. [1, 2]
• Unlike integer factorization, primality testing has a running time that is polynomial in the size of the input and is considered comparatively easy. [2]
• Some primality tests, such as Miller-Rabin, are probabilistic and determine if a number is likely to be prime or definitely composite. [2, 4]
• The AKS primality test is a deterministic algorithm that can determine if a number is prime or composite in polynomial time without relying on unproven mathematical conjectures. [5]

Where to go next

• how it workedHow does the Miller-Rabin test work?
• what followedWhy is primality testing crucial for cryptography?
• how we knowWhat was the significance of the AKS primality test?
• compared withHow does integer factorization differ from primality testing?
• a case in pointWhat are elliptic curve primality proving methods?
• an unexpected connectionHow do elliptic curves help prove prime numbers?Curves originally studied for geometry and factorization can also be deployed to provide quickly verifiable certificates of primality.

Sources

• [1]primality test (Wikidata Q829546) · CC0 1.0
• [2]Primality test · CC BY-SA 4.0
• [3]Elliptic curve primality · CC BY-SA 4.0
• [4]Miller–Rabin primality test · CC BY-SA 4.0
• [5]Agrawal–Kayal–Saxena primality test · CC BY-SA 4.0