Overview

A primality test is a procedure used to determine whether a given integer is prime. Tests vary in approach and guarantees: some return a definitive proof of primality while others give a probabilistic answer that a number is prime with high confidence. In computer science and number theory the word often refers to algorithmic techniques; see algorithm for general context. For the notion of the object being tested, see prime number. Primality testing is a routine but critical step in modern cryptography; large primes underpin schemes such as RSA and digital signatures — see cryptography.

Approaches and characteristics

Primality tests can be classified by whether they are deterministic or probabilistic, and by their computational complexity. Deterministic tests either provide a proof that a number is prime or identify a factor; probabilistic tests quickly identify composites with a tiny chance of error when reporting 'probably prime.' Efficiency, memory use, and ease of producing a verifiable certificate are typical design tradeoffs.

Common algorithms

  • Trial division: Try dividing by integers up to the square root; simple but impractical for large inputs.
  • Fermat and related tests: Use properties of powers modulo n; fast but susceptible to Carmichael numbers.
  • Miller–Rabin: A widely used probabilistic test that is very reliable with multiple bases; variants become deterministic under certain number-theoretic assumptions.
  • AKS: A deterministic, polynomial-time test discovered in 2002 that proved primality testing lies in P.
  • Elliptic Curve and ECPP: Practical algorithms that often produce certificates and work well for very large numbers.

History and development

Historically, primality testing grew from elementary divisibility checks to sophisticated algebraic and probabilistic methods. Breakthroughs include randomized tests that make large-scale cryptography feasible and deterministic polynomial-time algorithms that resolved theoretical questions about decidability and complexity. Practical implementations often combine fast probabilistic screening with a final deterministic or certifying step.

Applications and certificates

Beyond cryptography, primality tests are used in computational mathematics and in constructing mathematical objects that require prime moduli. When a formal proof is needed, many tests produce a primality certificate: a compact piece of data that allows a third party to verify the number's primality more cheaply than re-running the full test. Examples include Pratt certificates and those generated by ECPP or variants of Pocklington's theorem.

Notable distinctions

When selecting a test, consider input size and the need for absolute certainty. Probabilistic tests like Miller–Rabin offer speed and negligible error for routine use; deterministic methods (or certificates) are preferred when legal, scientific, or protocol-level proof is required. Implementations balance speed, reliability, and the effort to produce or verify certificates.