# Miller–Rabin primality test

The Miller–Rabin primality test is a randomized algorithm that decides whether an odd integer is prime: it never rejects a prime, and it declares a prime with an error probability of at most 
\( 4^{-t} \) after 
\( t \) independent rounds with random bases. It was introduced by Gary L. Miller in 1976 in a form conditional on the Extended Riemann Hypothesis and made unconditional by [Michael O. Rabin](https://www.edgepedia.org/michael-o-rabin) in 1980, and it remains the standard primality test inside cryptographic libraries.<sup>[1](https://www.sciencedirect.com/science/article/pii/S0022000076800438)</sup><sup> • </sup><sup>[2](https://www.sciencedirect.com/science/article/pii/0022314X80900840)</sup>

| Key fact | Detail |
|---|---|
| Origin | Gary L. Miller, "Riemann's Hypothesis and Tests for Primality", *Journal of Computer and System Sciences* 13(3):300–317, December 1976; a preliminary version appeared at STOC in May 1975<sup>[1](https://www.sciencedirect.com/science/article/pii/S0022000076800438)</sup><sup> • </sup><sup>[3](https://doi.org/10.1145/800116.803773)</sup> |
| Randomized form | Michael O. Rabin, "Probabilistic algorithm for testing primality", *Journal of Number Theory* 12(1):128–138, February 1980<sup>[2](https://www.sciencedirect.com/science/article/pii/0022314X80900840)</sup> |
| One-round error bound | A composite number, including a Carmichael number, passes a single round with probability at most 1/4; 
\( t \) rounds fail with probability below 
\( (1/4)^{t} \)<sup>[4](https://crypto.stanford.edu/pbc/notes/numbertheory/millerrabin.html)</sup><sup> • </sup><sup>[5](https://www.cs.yale.edu/homes/aspnes/classes/4690/notes.pdf)</sup> |
| Nature of the result | Strictly a compositeness test: a failure proves the input composite, while a pass only makes primality probable<sup>[4](https://crypto.stanford.edu/pbc/notes/numbertheory/millerrabin.html)</sup> |
| Standard use | Specified for prime generation in NIST FIPS 186-5; used by GMP, OpenSSL, and most RSA implementations<sup>[6](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf)</sup><sup> • </sup><sup>[7](https://gmplib.org/manual/Prime-Testing-Algorithm)</sup> |
| Typical round counts | FIPS 186-5 requires 2 rounds for 2048-bit RSA primes at error probability 
\( 2^{-100} \); OpenSSL uses at least 64 rounds, bounding the false positive rate at 
\( 2^{-128} \)<sup>[6](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf)</sup><sup> • </sup><sup>[8](https://docs.openssl.org/3.6/man3/BN_generate_prime/)</sup> |

## How the test works

The test builds on [Fermat's little theorem](https://www.edgepedia.org/fermats-little-theorem), which says that if 
\( n \) is prime then 
\( a^{n-1} = 1 \pmod{n} \) for any base 
\( a \). The plain Fermat test checks exactly this congruence, but it is defeated by Carmichael numbers such as 
\( 561 = 3 \times 11 \times 17 \), composites for which the congruence holds for every base coprime to 
\( n \), and there are infinitely many of them.<sup>[4](https://crypto.stanford.edu/pbc/notes/numbertheory/millerrabin.html)</sup>

Miller–Rabin strengthens the check using the fact that an odd 
\( n \) is prime if and only if the only solutions of 
\( x^{2} = 1 \pmod{n} \) are 
\( x = \pm 1 \). Write 
\( n - 1 = 2^{s} q \) with 
\( q \) odd, and consider the sequence

\[ a^{n-1} = a^{2^{s} q},\ a^{2^{s-1} q},\ \ldots,\ a^{q}, \]

in which each member is a square root of the one before it. If 
\( n \) is prime, the sequence begins with 1 and either every member is 1 or the first member different from 1 is 
\( -1 \). The test picks a random base 
\( a \) and rejects 
\( n \) as composite if the sequence does not begin with 1, or if the first member that is not 1 is also not 
\( -1 \).<sup>[4](https://crypto.stanford.edu/pbc/notes/numbertheory/millerrabin.html)</sup> In pseudocode form, a single round computes 
\( z = a^{q} \bmod n \), accepts if 
\( z \) is 1 or 
\( n-1 \), then squares 
\( z \) repeatedly up to 
\( s-1 \) times, accepting if any square equals 
\( n-1 \) and rejecting if a square equals 1 before that.<sup>[4](https://crypto.stanford.edu/pbc/notes/numbertheory/millerrabin.html)</sup><sup> • </sup><sup>[6](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf)</sup>

A pass is never a proof of primality. Composites that pass for a given base are called strong pseudoprimes to that base, and no 
\( n \) is a strong pseudoprime to more than 1/4 of all bases, so a randomly chosen base catches a composite with probability at least 3/4.<sup>[7](https://gmplib.org/manual/Prime-Testing-Algorithm)</sup><sup> • </sup><sup>[5](https://www.cs.yale.edu/homes/aspnes/classes/4690/notes.pdf)</sup> A failure can even yield more information: if 
\( n \) fails with a sequence starting at 1, the run has produced a nontrivial square root of 1 modulo 
\( n \), from which a factor of 
\( n \) can be computed efficiently, so Carmichael numbers are always easy to factor once the test exposes them.<sup>[4](https://crypto.stanford.edu/pbc/notes/numbertheory/millerrabin.html)</sup>

## Error bounds and running time

The worst-case guarantee is simple to state and use. Rabin showed that a random witness exposes a composite with probability at least 3/4, so testing 
\( t \) random witnesses fails less than 
\( (1/4)^{t} \) of the time, and for a fixed ratio the error drops as 
\( (d/r)^{k} \) after 
\( k \) trials, needing 
\( O(\log(1/\varepsilon)) \) iterations to reach any target error 
\( \varepsilon \).<sup>[5](https://www.cs.yale.edu/homes/aspnes/classes/4690/notes.pdf)</sup> In practice the bound is loose: strong pseudoprimes are rare, so the test is much more powerful than the 1/4 analysis suggests, and for random odd numbers the chance of a composite surviving one round is closer to 1/8 than 1/4.<sup>[7](https://gmplib.org/manual/Prime-Testing-Algorithm)</sup>

NIST's FIPS 186-5 treats the question from the generator's side. Its Appendix C defines 
\( p_{k,t} \), the probability that an odd 
\( k \)-bit integer that passes 
\( t \) rounds of Miller–Rabin testing with random bases is actually composite, estimated as a ratio over all odd 
\( k \)-bit integers following work of Pomerance and colleagues. For sufficiently large 
\( k \) (for example 
\( k \geq 51 \)), 
\( p_{k,t} \leq 4^{-t} \) under the same assumptions about candidate selection. The standard also warns that the probability a composite survives 
\( t \) rounds is not the same as 
\( p_{k,t} \), the probability that a survivor is composite; the latter is usually what a prime generator cares about, while the former matters to a party validating someone else's prime.<sup>[6](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf)</sup>

Each round costs one modular exponentiation, about 
\( \Theta(\log n) \) modular multiplications by square-and-multiply, so a single test runs in roughly cubic time in the bit length of 
\( n \). Generating an 
\( n \)-bit RSA prime by trial and error, testing about 
\( \Theta(\log n) \) candidates, brings the total worst-case cost to about 
\( \Theta((\log n)^{4}) \) multiplications.<sup>[9](https://www.usna.edu/Users/cs/wcbrown/courses/S17SI335/notes/03/notes.html)</sup>

## History

Gary L. Miller, a computer scientist then at the [University of California](https://www.edgepedia.org/university-of-california), Berkeley, presented the underlying test in a May 1975 STOC paper and in his 1976 journal paper "Riemann's Hypothesis and Tests for Primality". The paper gave two algorithms: one running in 
\( O(n^{1/7}) \) steps, improving the previously best known bound of 
\( O(n^{1/4}) \) due to Pollard, and one running in 
\( O((\log n)^{4}) \) steps under the Extended Riemann Hypothesis, showing that primality is testable in time polynomial in the length of the binary representation. The paper also gave a partial answer to the relationship between computing prime factorization, computing the Euler phi function, and related functions.<sup>[1](https://www.sciencedirect.com/science/article/pii/S0022000076800438)</sup><sup> • </sup><sup>[3](https://doi.org/10.1145/800116.803773)</sup>

Michael O. Rabin, a computer scientist and cryptographer, removed the hypothesis in his February 1980 paper in the *Journal of Number Theory*, presenting a practical probabilistic algorithm for large numbers of arbitrary form in which a composite verdict is always true and a prime verdict carries a provably small error probability; he used it to generate large probable primes of arbitrary and special forms, including very large twin-prime candidates.<sup>[2](https://www.sciencedirect.com/science/article/pii/0022314X80900840)</sup> NIST's original Digital Signature Standard appendix described its probabilistic primality test as Rabin's, based in part on ideas of Gary L. Miller.<sup>[10](https://en.wikisource.org/wiki/Page%3AFips186-2-change1.pdf/16)</sup> A 1980 comparative study of the Rabin formulation of Miller's test and the Solovay–Strassen test found the Miller–Rabin-derived algorithm always more efficient, both probabilistically and algorithmically.<sup>[11](https://www.sciencedirect.com/science/article/pii/0304397580900079)</sup> Deterministic polynomial-time primality tests now exist, notably the Agrawal–Kayal–Saxena algorithm, but they remain impractical compared with Miller–Rabin, which continues to be the most efficient and widely used test.<sup>[4](https://crypto.stanford.edu/pbc/notes/numbertheory/millerrabin.html)</sup>

## Use in cryptography

Prime generation for RSA, DSA, and elliptic-curve systems relies on Miller–Rabin, usually preceded by trial division by small primes to discard most composites cheaply.<sup>[4](https://crypto.stanford.edu/pbc/notes/numbertheory/millerrabin.html)</sup><sup> • </sup><sup>[7](https://gmplib.org/manual/Prime-Testing-Algorithm)</sup> NIST's FIPS 186-5, the current Digital Signature Standard published on February 3, 2023, specifies the test in Appendix B.3.1 with a number of iterations drawn from Table B.1: for RSA primes 
\( p \) and 
\( q \) of 1024 bits, 4 rounds at error probability 
\( 2^{-100} \) and 5 at 
\( 2^{-112} \); for 1536 bits, 3 and 4 rounds; for 2048 bits, 2 rounds at 
\( 2^{-100} \) and 4 at 
\( 2^{-144} \). The auxiliary primes 
\( p_{1}, p_{2}, q_{1}, q_{2} \), being much smaller, need far more rounds, 22 to 44 depending on size and target error.<sup>[6](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf)</sup> FIPS 186-5 also offers an enhanced variant that, on detecting compositeness, reports whether a factor was found or the number is not a prime power.<sup>[6](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf)</sup>

**Library practice.** GMP's `mpz_probab_prime_p` performs trial divisions, a Baillie–PSW probable prime test, then 
\( \mathit{reps} - 24 \) Miller–Rabin tests, identifying a composite as prime with asymptotic probability under 
\( 4^{-\mathit{reps}} \); reasonable values of 
\( \mathit{reps} \) are 15 to 50, and versions up to 6.1.2 used only Miller–Rabin.<sup>[12](https://gmplib.org/gmp-man-6.3.0.pdf)</sup> OpenSSL's `BN_check_prime` and related functions always use at least 64 rounds of Miller–Rabin, giving a maximum false positive rate of 
\( 2^{-128} \), and at least 128 rounds for numbers above 2048 bits, bounding the rate at 
\( 2^{-256} \).<sup>[8](https://docs.openssl.org/3.6/man3/BN_generate_prime/)</sup><sup> • </sup><sup>[13](https://docs.openssl.org/3.0/man7/migration_guide/)</sup> The Baillie–PSW combination, a base-2 Miller–Rabin test followed by a strong Lucas test, has no publicly known counterexample, and FIPS 186-5 notes that no non-prime values are known to pass its prescribed Miller–Rabin rounds followed by one Lucas test, which is why the combination may add assurance.<sup>[6](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf)</sup><sup> • </sup><sup>[14](https://citeseerx.ist.psu.edu/document?doi=4942adaa84bbd075a58e73f8eea0eb6d669262c0&repid=rep1&type=pdf)</sup>

**Residual risks.** The formal error bound assumes correct execution and honest randomness. A hardware fault can defeat it: although each iteration rejects a composite with probability at least 0.75, the probability that a stray cosmic ray flips a bit in the machine code and causes the test to accept composites is substantially greater than 
\( 2^{-128} \), so naive implementations cannot reach the advertised security level.<sup>[15](https://pmc.ncbi.nlm.nih.gov/articles/PMC4841483/)</sup> The bound also describes random inputs; an adversary who supplies the candidate can search for composites tailored to evade a fixed testing routine, a setting analyzed in work on primality testing under adversarial conditions.<sup>[15](https://pmc.ncbi.nlm.nih.gov/articles/PMC4841483/)</sup> For randomly self-generated candidates, by contrast, a few rounds suffice at cryptographic sizes, which is why FIPS 186-5 can demand only 2 rounds for a 2048-bit prime drawn from an approved random bit generator.<sup>[6](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf)</sup>

## References

1. [Gary L. Miller (1976). Riemann's Hypothesis and Tests for Primality. Journal of Computer and System Sciences 13(3):300–317.](https://www.sciencedirect.com/science/article/pii/S0022000076800438)
2. [Michael O. Rabin (1980). Probabilistic algorithm for testing primality. Journal of Number Theory 12(1):128–138.](https://www.sciencedirect.com/science/article/pii/0022314X80900840)
3. [Gary L. Miller (1975). Riemann's Hypothesis and tests for primality. STOC '75, pages 234–239.](https://doi.org/10.1145/800116.803773)
4. [Primality Tests: The Miller-Rabin Test, Stanford notes by Paul Burchard](https://crypto.stanford.edu/pbc/notes/numbertheory/millerrabin.html)
5. [James Aspnes, Randomized Algorithms course notes, Yale University](https://www.cs.yale.edu/homes/aspnes/classes/4690/notes.pdf)
6. [FIPS 186-5, Digital Signature Standard (DSS), NIST, February 3, 2023](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf)
7. [Prime Testing Algorithm, GNU MP 6.3.0 manual](https://gmplib.org/manual/Prime-Testing-Algorithm)
8. [BN_generate_prime, OpenSSL 3.6 documentation](https://docs.openssl.org/3.6/man3/BN_generate_prime/)
9. [SI335, Unit 3: Number-Theoretic Computations, United States Naval Academy](https://www.usna.edu/Users/cs/wcbrown/courses/S17SI335/notes/03/notes.html)
10. [FIPS 186-2 Change 1, Appendix: A Probabilistic Primality Test, Wikisource transcription](https://en.wikisource.org/wiki/Page%3AFips186-2-change1.pdf/16)
11. [Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoretical Computer Science 12(1):97–108, 1980](https://www.sciencedirect.com/science/article/pii/0304397580900079)
12. [GNU MP 6.3.0 manual, section 5.9 Number Theoretic Functions](https://gmplib.org/gmp-man-6.3.0.pdf)
13. [OpenSSL 3.0 migration guide](https://docs.openssl.org/3.0/man7/migration_guide/)
14. [A version of the Baillie-PSW test, Mathematics of Computation](https://citeseerx.ist.psu.edu/document?doi=4942adaa84bbd075a58e73f8eea0eb6d669262c0&repid=rep1&type=pdf)
15. [Too good to be true: when overwhelming evidence fails to convince, Proceedings of the Royal Society A (2016)](https://pmc.ncbi.nlm.nih.gov/articles/PMC4841483/)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Number theory › Computational and probabilistic number theory › Primality testing algorithms*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026; Oct 25, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license