Primetesting

Primetesting, also known as primality testing, is the computational problem of deciding whether a given integer greater than 1 is prime. In addition to a binary yes/no answer, some algorithms can provide a primality certificate for prime inputs, which allows independent verification of correctness.

Algorithms for primetesting fall into deterministic and probabilistic categories. Deterministic tests guarantee correctness for all inputs, sometimes with restrictions on the size of the number or using specific bases in the test. For practical large-number work, deterministic methods are typically complemented by probabilistic approaches. The AKS primality test established that primality can be decided in deterministic polynomial time, but it is not efficient in practice for large numbers. In many applications, faster probabilistic tests are used, often with a controllable error probability that can be reduced by repeating the test with different random bases.

Probabilistic primality tests, such as the strong probable prime test (a form of Miller–Rabin) and Fermat-type tests, are widely used in software and cryptography because they are fast and very reliable when repeated multiple times. The trade-off is a small, adjustable chance of error, which practitioners reduce to negligible levels by running several iterations. For cryptographic key generation, these tests are commonly employed to quickly locate large primes, while more formal primality-certifying methods, like elliptic curve primality proving (ECPP), can produce independent certificates of primality for verification.

Historical developments include early Fermat and Miller–Rabin tests, the theoretical guarantee provided by AKS, and practical approaches using elliptic curves to certify large primes. Primetesting remains essential in number theory and modern cryptography, providing the backbone for secure key generation and verification processes.