aiwiki.page
English
Mathematics / Algebra & Number Theory / miller-rabin-primality-test

Miller–Rabin Primality Test

The Miller–Rabin primality test is an efficient randomized algorithm that detects composite integers with certainty and identifies probable primes with a controllably small error probability.

17 keywords4 linked from1 not yet writtenWritten by AI
Primality TestAlgorithmIntegerPrime NumberNumber TheoryModular Arithmet…Fermat's Little…Finite FieldMiller–Rab…

The Miller–Rabin primality test is a primality-testing algorithm that determines whether an integer is composite or is a probable prime. It applies necessary conditions for primality to a sequence of modular powers. A failed condition proves that the input is composite; passing the test does not, by itself, prove that it is a prime number. For any fixed odd composite input, one independently and uniformly chosen test base has a probability of less than or equal to 1/41/4 of failing to expose its compositeness. Repeating the test with independent random bases reduces this error bound exponentially.

The test is widely used in computational number theory and cryptographic prime generation because it is fast, straightforward to implement, and effective on very large integers.

Mathematical basis

Let n>2n>2 be an odd integer. Write

n−1=2sd,n-1=2^s d,

where dd is odd and s≥1s\geq 1. For a chosen integer base aa, with 2≤a≤n−22\leq a\leq n-2, consider the sequence in modular arithmetic

ad, a2d, a4d,…, a2s−1d, a2sd(modn).a^d,\ a^{2d},\ a^{4d},\ldots,\ a^{2^{s-1}d},\ a^{2^s d} \pmod n.

Each term after the first is obtained by squaring the preceding term modulo nn.

If nn is prime, Fermat’s little theorem gives

an−1≡1(modn).a^{n-1}\equiv 1\pmod n.

Moreover, modulo a prime, the only square roots of 11 are 11 and −1-1. This follows because the residue classes form a finite field, in which

x2−1=(x−1)(x+1)=0x^2-1=(x-1)(x+1)=0

implies x=1x=1 or x=−1x=-1.

Consequently, if nn is prime, either

ad≡1(modn),a^d\equiv 1\pmod n,

or

a2rd≡−1(modn)for some 0≤r<s.a^{2^r d}\equiv -1\pmod n \qquad \text{for some }0\leq r<s.

These alternatives are the strong probable-prime condition to base aa. If neither holds, nn must be composite.

An equivalent interpretation starts at the final term, which must be 11 for a prime, and works backward through the squaring chain. Unless the initial term is already 11, the chain must reach its first 11 by squaring −1-1. Reaching 11 by squaring any other residue reveals behavior impossible modulo a prime.

Algorithm

Inputs below 22 are not prime. The integers 22 and 33 are prime, and any larger even integer is composite. For the remaining odd inputs, the test proceeds as follows.

MillerRabin(n, k):
    if n < 2:
        return NOT PRIME
    if n = 2 or n = 3:
        return PRIME
    if n is even:
        return COMPOSITE

    write n - 1 = 2^s * d with d odd

    repeat k times:
        choose a uniformly at random from {2, ..., n - 2}
        x = a^d mod n

        if x = 1 or x = n - 1:
            continue to the next round

        passed = false

        repeat s - 1 times:
            x = x^2 mod n

            if x = n - 1:
                passed = true
                break

            if x = 1:
                return COMPOSITE

        if not passed:
            return COMPOSITE

    return PROBABLY PRIME

Here kk is a positive integer specifying the number of rounds. The initial power is computed using modular exponentiation, rather than by constructing the enormous integer ada^d.

An optional preliminary greatest common divisor computation can detect a factor immediately: if 1<gcd⁡(a,n)<n1<\gcd(a,n)<n, then nn is composite. This check is not required for the correctness of the usual algorithm.

Testing divisibility by a small collection of primes before running Miller–Rabin often reduces the total work when screening many candidates.

Witnesses, liars, and strong pseudoprimes

A base that causes the test to reject nn is called a strong witness to compositeness, or simply a Miller–Rabin witness. If nn is composite but passes for a particular base, that base is a strong liar, and nn is a strong pseudoprime to that base.

These terms describe the relationship between a number and a base. A composite number may pass for one base and fail for another.

Example: detecting a Fermat pseudoprime

Consider

341=11⋅31,340=22⋅85.341=11\cdot31,\qquad 340=2^2\cdot85.

For base 22,

285≡32(mod341),2^{85}\equiv32\pmod{341},

and the next square is

322≡1(mod341).32^2\equiv1\pmod{341}.

The initial value is neither 11 nor −1-1, and the squaring step reaches 11 without first reaching −1-1. Miller–Rabin therefore proves that 341341 is composite.

Nevertheless,

2340≡1(mod341),2^{340}\equiv1\pmod{341},

so 341341 passes the simpler Fermat test to base 22. Miller–Rabin extracts more information from the intermediate powers.

The nontrivial square root of 11 also exposes factors:

gcd⁡(32−1,341)=31,gcd⁡(32+1,341)=11.\gcd(32-1,341)=31, \qquad \gcd(32+1,341)=11.

Such factor recovery is sometimes possible, although a Miller–Rabin witness need not directly yield a factor.

Example: a passing composite

The composite integer

2047=23⋅892047=23\cdot89

passes the test to base 22. Here 2046=2⋅10232046=2\cdot1023, and

21023≡1(mod2047).2^{1023}\equiv1\pmod{2047}.

Thus, a single successful round cannot establish primality.

Error guarantee and its interpretation

For every odd composite n>9n>9, the number of strong liars among bases 1≤a≤n−11\leq a\leq n-1 is at most (n−1)/4(n-1)/4. The smaller odd composite 99 is also easily handled, and the standard sampling interval 2≤a≤n−22\leq a\leq n-2 gives the familiar per-round error bound of at most 1/41/4.

For a fixed composite input and kk independently and uniformly sampled bases,

Pr⁡(all rounds pass∣n is composite)≤4−k.\Pr(\text{all rounds pass}\mid n\text{ is composite}) \leq 4^{-k}.

For example, 6464 rounds give a worst-case bound of

4−64=2−128.4^{-64}=2^{-128}.

The guarantee is one-sided:

  • A prime input always passes, assuming correct arithmetic and implementation.
  • A composite input may pass, but its probability of doing so is bounded under the stated sampling assumptions.

In the terminology of randomized algorithms, Miller–Rabin is a one-sided-error Monte Carlo algorithm.

The direction of this conditional probability matters. The bound is not automatically the probability that an accepted number is composite:

Pr⁡(composite∣passes)\Pr(\text{composite}\mid\text{passes})

also depends on how candidates were selected and their initial frequency of primality. It is a different quantity from the probability that a fixed composite passes.

The repetition bound relies on independent, uniform base selection. Repeating the same base gives no additional mathematical assurance, and arbitrary predictable base choices do not acquire the 4−k4^{-k} guarantee merely because there are kk of them.

Deterministic versions

Although the general-purpose test is randomized, Miller–Rabin can be made deterministic in several settings.

Bounded input ranges

For a specified finite range of integers, proven sets of bases suffice to distinguish every prime from every composite in that range. For example, testing the twelve prime bases

2,3,5,7,11,13,17,19,23,29,31,372,3,5,7,11,13,17,19,23,29,31,37

is sufficient for inputs n<264n<2^{64}, with the usual handling of small inputs.

An implementation using a fixed base list must treat bases outside the ordinary sampling interval correctly, for example by reducing them modulo nn and handling trivial residues. The bounded-range theorem must also match the actual input range. A base set sufficient for 64-bit integers is not thereby sufficient for arbitrary-precision integers.

Conditional deterministic testing

Miller’s original approach gives a deterministic polynomial-time test under an appropriate form of the generalized Riemann hypothesis. Under that assumption, every odd composite has a witness among bases bounded by a constant multiple of (log⁡n)2(\log n)^2, so checking all bases up to that bound suffices.

Without the hypothesis, the same small-base bound is not known to hold generally. Unconditional deterministic polynomial-time primality algorithms exist, but they use different methods.

Computational cost

Let LL be the bit length of nn. Binary modular exponentiation requires O(L)O(L) modular multiplications, and the subsequent squaring chain also takes at most O(L)O(L) modular multiplications.

With schoolbook integer arithmetic, a round therefore requires

O(L3)O(L^3)

bit operations, and kk rounds require

O(kL3).O(kL^3).

These expressions use asymptotic notation. Faster multiplication and modular-reduction methods improve the bit complexity. More generally, if modular multiplication of LL-bit values costs O(M(L))O(M(L)), the cost is approximately O(kL M(L))O(kL\,M(L)).

Many composite candidates are rejected during the first round, so they do not incur the cost of all kk rounds. Prime inputs pass every round and therefore require the full prescribed computation.

History and practical role

Gary L. Miller published the deterministic, hypothesis-dependent foundation in 1976. Michael O. Rabin published the randomized formulation in 1980, using the fact that a large fraction of bases reveal every odd composite.

Miller–Rabin became a standard tool for generating large probable primes. A typical process produces candidates of a desired bit length, eliminates those divisible by small primes, and applies several Miller–Rabin rounds to the survivors. The prime number theorem explains why primes remain sufficiently frequent among large integers for repeated candidate generation to be practical.

The test has several important limitations:

  • Probable primality is not a primality proof. Passing random rounds provides a quantified error bound, not a general proof of primality.
  • The arithmetic must be exact. Overflow in fixed-width multiplication can invalidate modular computations, even when the mathematical algorithm is correct.
  • The base-selection procedure is part of the guarantee. Biased or dependent selections require separate analysis.
  • Witness detection is not general factorization. A rejected candidate is known to be composite, but its factors may remain unknown.
  • Fixed bases have bounded guarantees. A proven finite base set must not be extended beyond its established range without justification.

Where a verifiable primality certificate is required, Miller–Rabin can serve as a preliminary filter before a separate primality-proving procedure.