The algorithmic process of deciding whether a given integer is prime, producing either a deterministic certificate of primality or a probabilistic verdict that the number is prime with high confidence.

Principle

Primality tests exploit number-theoretic properties that distinguish primes from composites (Fermat's little theorem, strong probable-prime conditions, polynomial identities, elliptic curve properties) and either produce an unambiguous proof or a randomized witness that a number is almost certainly prime.

Demonstration

Examples include deterministic polynomial-time tests such as AKS (which checks a polynomial congruence), probabilistic algorithms like Miller–Rabin (testing strong probable-prime bases), and certificate-producing methods like ECPP that output a verifiable primality proof; e.g., Miller–Rabin rapidly filters composites, while ECPP can generate an explicit certificate for large primes used in cryptography.

Misapplication

Relying on a single Fermat test to assert primality without accounting for Carmichael numbers or composite witnesses; using a probabilistic test where a deterministic proof is required; or applying tests intended for odd integers to even or trivially small inputs without preprocessing.

Consequence

Efficient primality testing enables practical generation and validation of large primes for cryptographic protocols and computational number theory; when a deterministic certificate is produced, one attains absolute certainty suitable for formal verification and mathematical proofs.

Reversal

The reversal is integer factorization: knowing the full factorization immediately decides primality but is usually far harder computationally; conversely, primality testing can often be substantially cheaper than full factorization and sometimes supplies certificates without factoring.

Boundary

Concerned with the primality decision of integers presented in an explicit representation; excludes related but distinct tasks such as integer factorization, primality of algebraic integers without transport to Z, or heuristics that lack provable error bounds unless explicitly probabilistic and quantified.

Semantic Tension

Tension exists between probabilistic primality tests (fast, with tiny error probability) and deterministic proofs (slower but certain); also between testing as a yes/no decision and producing a verifiable certificate — both achieve the goal but serve different applications and assurances.

Synthesis

Primality testing comprises algorithmic criteria, ranging from fast probabilistic checks to slower deterministic proofs, that decide whether an integer is prime; it balances speed and certainty according to application needs and separates the decision problem from the harder task of full factorization.