Miller-Rabin primality test

Miller-Rabin primality test is a probabilistic algorithm for determining whether a given integer is prime. It is a refinement of Gary Miller's 1976 deterministic test, made probabilistic by Michael Rabin using randomness to avoid the unproven assumptions Miller required. The test works by checking whether the number behaves like a prime in a set of randomly chosen modular arithmetic trials. For a composite number, the probability that a single round falsely declares it prime is at most 1/4; with k independent rounds, the error probability drops to 4^{-k}.\n\nThe test is the workhorse of modern cryptography. Every RSA key generation, every TLS handshake parameter, every elliptic curve setup uses Miller-Rabin or a variant to filter candidate primes. Its dominance reflects a deep principle of cryptographic engineering: for security parameters where the hardware failure rate exceeds the algorithmic error rate, probabilistic certainty is indistinguishable from deterministic certainty. The test also illustrates the computational power of randomness as a resource: with a small number of random bits, Miller-Rabin achieves confidence levels that deterministic methods cannot match at comparable cost.\n\nMiller-Rabin is not a compromise between rigor and speed; it is a revelation that the distinction between proof and high-confidence verification collapses at the scale where computation meets physics. When the probability of algorithmic error is below the probability of cosmic ray bit flips, what does 'deterministic' even mean?\n\n\n\n