primalitytesting

Primality testing is the computational problem of determining whether a given integer n greater than 1 is prime. It is foundational in number theory and cryptography. A primality test may be probabilistic, returning prime with high confidence and a small chance of error, or deterministic, giving a definitive answer for all inputs. Some tests also produce a primality certificate that can be independently checked.

Historically, simple methods such as trial division are impractical for large n. Early probabilistic tests based on Fermat's little theorem revealed that many composites pass as primes (Fermat pseudoprimes). Modern probabilistic tests include the Miller-Rabin test and the Solovay-Strassen test; both have adjustable error probability that decreases with the number of bases examined. Repeating the test with independent bases yields arbitrarily small error.

In 2002, the Agrawal–Kayal–Saxena (AKS) primality test showed that primality can be determined in deterministic polynomial time, placing primality testing in P. In practice, randomized tests remain widely used for their speed, and many cryptographic systems rely on probabilistic tests with carefully chosen parameters. For applications requiring a verifiable proof, elliptic curve primality proving (ECPP) and related algorithms produce a formal prime certificate.

Applications of primality testing include key generation for public-key cryptography, primality pruning in algorithms, and various mathematical computations. While primality testing answers whether a number is prime, in some settings a primality proof or certificate is preferred to verify primality independently of the algorithm used.