Primality Testing | Aevum Encyclopedia

Introduction

Primality testing is a class of computational algorithms that determines whether a given positive integer is prime (has exactly two distinct positive divisors: 1 and itself) or composite. Unlike integer factorization, which seeks to decompose a composite number into its prime factors, primality testing only answers a binary question: Is this number prime?

The problem holds foundational significance in number theory, computational mathematics, and modern cryptography. With the widespread adoption of asymmetric encryption standards like RSA, efficient and reliable primality testing has become critical to digital security infrastructure.

Key Distinction Primality testing does not factor the number. Determining that a number is composite (a primality certificate) can often be done far more efficiently than finding its actual prime factors.

Classical Methods

Trial Division

The most intuitive approach checks whether an integer \( n \) is divisible by any integer from 2 up to \( \sqrt{n} \). If no divisor is found, \( n \) is prime.

n \) is prime \( \iff \nexists \, d \in \{2, \dots, \lfloor\sqrt{n}\rfloor\} \) such that \( d \mid n

While mathematically sound, trial division has a time complexity of \( O(\sqrt{n}) \), making it computationally infeasible for large integers (e.g., 2048-bit keys used in modern cryptography).

Probabilistic Tests

For cryptographic applications, deterministic tests were historically too slow. Instead, probabilistic (Monte Carlo) algorithms trade absolute certainty for exponential speed. These tests may occasionally misclassify a composite number as prime (a false positive), but the error probability can be made arbitrarily small by repeating the test.

Fermat Primality Test

Based on Fermat's Little Theorem, which states that for a prime \( p \) and integer \( a \) where \( 1 \le a < p \):

a^{p-1} \equiv 1 \pmod{p}

If \( a^{n-1} \not\equiv 1 \pmod{n} \) for some base \( a \), then \( n \) is definitely composite. However, certain composite numbers called Carmichael numbers satisfy the condition for all bases coprime to \( n \), leading to false positives.

Miller–Rabin Primality Test

Introduced in the 1970s, the Miller–Rabin test is the industry standard for probabilistic primality testing. It strengthens Fermat's test by examining the structure of modular square roots of 1.

By writing \( n-1 = 2^s \cdot d \) with \( d \) odd, the test checks whether a random base \( a \) satisfies:

a^d \equiv 1 \pmod{n} \) or \( \exists \, r \in \{0, \dots, s-1\} : a^{2^r d} \equiv -1 \pmod{n}

If neither condition holds, \( n \) is composite. The probability that a composite number passes \( k \) independent rounds is at most \( 4^{-k} \). In practice, 20–40 iterations reduce the error rate below \( 10^{-24} \), making it cryptographically secure.

Deterministic Algorithms

AKS Primality Test

In 2002, Agrawal, Kayal, and Saxena published the AKS primality test, the first algorithm proven to be both deterministic and polynomial-time. Its theoretical complexity is \( \tilde{O}(\log^6 n) \).

The test relies on the algebraic identity:

(X + a)^n \equiv X^n + a \pmod{n, X^r - 1}

While AKS was a landmark achievement in complexity theory, its constant factors and practical overhead make it slower than Miller–Rabin for numbers of cryptographic size.

Lucas–Lehmer Test

A specialized deterministic test for Mersenne primes of the form \( M_p = 2^p - 1 \). It is the algorithm powering the Great Internet Mersenne Prime Search (GIMPS), which has discovered all known largest prime numbers since 1998.

Computational Complexity

Algorithm	Complexity	Type
Trial Division	\( O(\sqrt{n}) \)	Deterministic
Miller–Rabin	\( O(k \log^3 n) \)	Probabilistic
AKS	\( \tilde{O}(\log^6 n) \)	Deterministic
Lucas–Lehmer	\( O(p^2 \log p \log \log p) \)	Deterministic (Mersenne only)

The existence of the AKS test proves that PRIMES ∈ P, resolving a decades-old question in computational complexity. This means primality can be verified in polynomial time without relying on unproven conjectures.

Real-World Applications

RSA Cryptography: Requires generating two large distinct primes. Miller–Rabin is used during key generation.
Diffie–Hellman Key Exchange: Relies on safe primes (where \( (p-1)/2 \) is also prime), verified via primality testing.
Randomized Algorithms: Used in hash table resizing, Monte Carlo simulations, and cryptographic commitment schemes.
Computational Number Theory: Fundamental for elliptic curve cryptography (ECC) and post-quantum lattice-based schemes.

References

Agrawal, M., Kayal, N., & Saxena, N. (2004). "PRIMES is in P". Annals of Mathematics, 160(2), 781–793.
Miller, G. L. (1976). "Riemann's Hypothesis and Tests for Primality". Journal of Computer and System Sciences, 13(3), 300–317.
Rabin, M. O. (1980). "Probabilistic Algorithm for Testing Primality". Journal of Number Theory, 12(1), 128–138.
Koblitz, N. (2012). A Course in Number Theory and Cryptography (3rd ed.). Springer.
OpenSSL Project. (2023). "Prime Number Generation and Verification". OpenSSL Documentation. https://www.openssl.org/docs/man3.0/man3/BN_generate_prime.html