This article was accepted into the corpus but its outbound wikilinks were never NER-processed — typical at the deepest BFS hop or when the run's entity cap was reached. No expansion funnel to show.
| Rabin–Miller | |
|---|---|
| Name | Rabin–Miller |
| Caption | Probabilistic primality testing |
| Introduced | 1976 |
| Inventor | Michael O. Rabin; Gary L. Miller |
| Field | Computational number theory, Cryptography |
Rabin–Miller Rabin–Miller is a probabilistic primality testing algorithm used in computational number theory and cryptography to distinguish prime numbers from composite numbers with high confidence. Developed from work by Gary L. Miller and Michael O. Rabin, the method builds on concepts from Lucas sequences, the Solovay–Strassen test, and results related to the Fermat's little theorem and Euler's criterion. The test is widely used in implementations of public-key systems such as RSA, Diffie–Hellman, and in libraries associated with OpenSSL, GnuPG, and LibreSSL.
Rabin–Miller operates by selecting random bases and performing modular exponentiation to reveal witnesses to compositeness; its probabilistic guarantees were motivated by work in complexity theory by Manuel Blum, Silvio Micali, and Michael O. Rabin and connected to deterministic criteria studied by Adleman and Gary L. Miller. The algorithm influenced standards in FIPS and implementations in software projects such as OpenBSD, NetBSD, and FreeBSD, and it is discussed in texts by Donald Knuth, Richard Brent, Ronald Rivest, Adi Shamir, and Leonard Adleman.
The core procedure writes an odd candidate n−1 as 2^s·d with d odd, selects random bases a in (1,n−1), computes x ≡ a^d (mod n) using fast modular exponentiation via algorithms attributed to Peter L. Montgomery and techniques from Karatsuba and Schönhage–Strassen for large multiplications. The algorithm checks x ≡ 1 or x ≡ −1 (mod n) or iterates x ≡ x^2 (mod n) up to s−1 times looking for −1, which arises in proofs linked to Euler's criterion and Jacobi symbol computations used in Solovay–Strassen. Implementations often incorporate deterministic base lists proven sufficient for ranges based on work by Damgård, Pomerance, Selfridge, Feitsma, Jim Sinclair, and computational verification by Miller–Rabin determinism investigations.
Correctness rests on number-theoretic results about nontrivial square roots of 1 modulo composite n and on the distribution of strong liars versus witnesses, with theoretical bounds given by analyses from Michael O. Rabin and refinements by Carl Pomerance and Andrew Odlyzko. The test is one-sided: composite inputs are declared prime only with bounded probability; repeated independent trials reduce this probability exponentially. Worst-case pseudoprime families such as Carmichael numbers and constructs from Poulet numbers expose limitations similar to those studied by Ribenboim and Alford, Granville, and Pomerance; however, combined with deterministic sieves like Sieve of Eratosthenes and small-prime trial division common in implementations in GnuPG and OpenSSL, practical error rates are negligible.
Time complexity for k rounds on an n-bit input is O(k·M(n)·log n) where M(n) denotes multiplication cost; practical implementations achieve O(k·(log n)^3) using classical multiplication or better using Karatsuba or Schönhage–Strassen for very large keys as in PGP and SSH. Performance trade-offs were analyzed in benchmarking studies by teams from IBM, Microsoft Research, Google, and academic groups at MIT and Stanford University; hardware acceleration using Intel's AVX or ARM NEON, and specialized big-integer libraries such as GMP and LibTomMath further optimize runtime. Memory and cache behaviors are important in environments like Android and iOS where cryptographic key generation must balance latency and entropy from sources like /dev/random.
Variants include deterministic variants for bounded n proven by computational verification (work by Jim Sinclair and others), hybrid approaches combining AKS for determinism and Rabin–Miller for speed, and versions using fixed bases optimized for 32-bit and 64-bit ranges following analyses by Damgård, Selfridge, Feitsma, and Jim Sinclair. Improvements engage algorithmic advances in modular exponentiation (windowed exponentiation, Montgomery reduction) and randomized base selection tied to cryptographic RNGs like Yarrow and Fortuna as implemented by OpenSSH and LibreSSL.
Rabin–Miller is central to key generation in asymmetric cryptography for RSA, ECC initialization, and protocols such as TLS, IPsec, PGP, and S/MIME. It supports blockchain technologies including Bitcoin and Ethereum in address and key operations, and cryptographic tooling across Debian, Red Hat, Canonical distributions and cloud providers such as Amazon Web Services, Google Cloud Platform, and Microsoft Azure. Academic applications appear in computational projects at CERN, Los Alamos National Laboratory, and number-theory research at University of Cambridge and Princeton University.
Practical deployment requires secure randomness from NIST SP 800-90A-compliant generators or OS sources, constant-time implementations to avoid timing attacks described by researchers at EPFL and Stanford and side-channel mitigations practiced by Intel and ARM. Implementers must integrate trial division by small primes (as in Sieve of Eratosthenes and tables from OEIS), deterministic base sets for constrained environments (smartcards by NXP Semiconductors), and conformance to standards by IETF and IEEE. Testing and verification use formal methods from Coq and Isabelle/HOL and fuzzing frameworks from Google's OSS-Fuzz.
Category:Primality tests