Background: two ways to test a prime
The Miller-Rabin test picks a base, does one modular exponentiation, and either proves the number composite or says it is probably prime. For a composite number at most one base in four gives the wrong answer (Rabin 1980), so k rounds with random bases are wrong with probability at most 4-k. For a number chosen at random, as in key generation, the chance is far smaller than that worst case (Damgård, Landrock and Pomerance 1993), which is why standards allow so few rounds.
Miller's original 1976 version has no randomness. It tries every base up to a limit, and if the extended Riemann hypothesis is true a composite number cannot pass them all. Eric Bach showed in 1990 that the limit can be 2(ln n)². Until the hypothesis is proven, a number that passes is "prime if GRH holds". With a proof it would simply be prime. Since 2002 the AKS test has shown that a deterministic polynomial-time test needs no hypothesis at all.
Do all bases have to be tried, or only the prime ones? Every published statement we found, in Bach's paper, Schoof's survey and Keith Conrad's notes, uses every integer base up to the bound, and so do the headline numbers here. The table also gives a second count, prime bases only, which we think is enough for this reason. The bases that wrongly pass a composite n lie inside a proper subgroup of the integers modulo n (Conrad, Corollary 5.1), and Bach's bound comes from a theorem that every proper subgroup misses some number below it. The smallest number a subgroup misses is always prime, because a product of numbers inside a subgroup is also inside it. We did not find that last step in a published source, so the prime-only count is our own observation.
Findings
Few rounds, by design. None of the 10 probabilistic libraries runs more than 8 Miller-Rabin rounds on a 1024-bit RSA prime. The lowest count is 2 (LibreSSL and OpenJDK, both of which add a Lucas test). Several say in comments that the low counts are safe only because the candidate is random, and use 64 rounds, an error of at most 2-128, for a number supplied by someone else.
Rounds go down as primes get larger. A larger random number that passes one round is less likely to be composite. OpenSSL, BoringSSL, Go, NSS, Mbed TLS and OpenJDK all use fewer rounds for larger primes. Bouncy Castle is the exception at 2048 bits, because its default certainty rises with the key size. OpenSSL uses 64 rounds for 512-bit primes because keys under 2048 bits take an older code path.
One library already builds proven primes. Nettle, which GnuTLS uses, constructs each RSA prime from a smaller proven prime with Maurer's algorithm and Pocklington's theorem. The result comes with a proof and no error probability, and needs no hypothesis. FIPS 186-5 also permits provable primes.
Miller's test is hundreds of thousands of times more work. For a 1024-bit prime the deterministic test tries 1,007,581 bases where the standard asks for 5 rounds: 201,516 times as many. Even against 64 rounds it is 15,743 times as many. Testing only the 79,060 prime bases, if that is enough, would still be 15,812 times the standard's count. The gap grows with size: 4,030,330 bases for a 2048-bit prime, 16,121,326 for a 4096-bit number.
What a proof of GRH changes here: the wording, not the software. Composite candidates would still be rejected after a round or two, so the cost falls on the primes that are kept. A test that takes about 7 minutes (32 seconds with prime bases only) to confirm one 1024-bit prime, on a machine where 5 rounds take about 1.8 ms, buys a certainty that a probability of 2-100 or less already gives for practical purposes, and libraries that want a proof already have faster ways to get one. We found nothing in the code we read that waits on GRH.
What the standard requires
FIPS 186-5 (February 2023), Table B.1, gives the minimum number of Miller-Rabin rounds for the two RSA primes. It lists two error targets for each size:
- 1024-bit primes: 4 rounds for an error of 2-100, 5 rounds for 2^-112.
- 1536-bit primes: 3 rounds for an error of 2-100, 4 rounds for 2^-128.
- 2048-bit primes: 2 rounds for an error of 2-100, 4 rounds for 2^-144.
The standard requires a modulus of at least 2048 bits, so it has no row for 512-bit primes. It allows Miller-Rabin alone, or Miller-Rabin followed by one Lucas test, and it also allows primes built with a proof.
Method
Part A. On 20 November 2026 we downloaded the files that generate RSA primes from the main development branch of each project and read the code path from "generate an RSA key" to the primality test. We recorded the test, the number of rounds for each size, and any error bound written in the code or its comments. 29 files were read. The data file records each file's address and the first 16 digits of its SHA-256 as downloaded.
Part B, computed. For each size we took the largest number of that size, computed Bach's bound 2(ln n)² with 200-bit arithmetic, and counted the integers and the primes up to it with a sieve. These counts do not depend on the machine.
Part B, measured. We generated one random prime of each size with a fixed seed and timed, with GMP 6.3.0 through gmpy2 2.3.2 on Python 3.13.18: one Miller-Rabin round with a random base (200 rounds, median and mean), and the whole deterministic test with every prime base. For 512, 1024, 1536 and 2048 bits the whole test was run to the end. For 3072 and 4096 bits we timed about 2,000 evenly spaced prime bases and multiplied. The all-integer times are the measured time per base multiplied by the number of bases. Every base passed, as it must for a prime. The run was on 21 November 2026 with nothing else running on the machine; the script records its load average.
The script and all data are published below. Run in the site's repository, the script writes its results into the data file, and the site build makes the page and the CSV files from that file, so every published number comes from the code.
Limits
- We read development branches on one day. Released versions, distribution patches and FIPS-validated builds can differ, and we did not record commit identifiers, only file fingerprints.
- We read code and did not run each library. Round counts are for default settings and standard two-prime RSA keys. Diffie-Hellman and DSA parameter generation use other paths that we did not survey.
- Round counts alone do not rank libraries. Trial division, Fermat and Lucas tests, how bases are chosen and how candidates are generated all matter, and every library here meets or exceeds its stated target.
- The timings come from one 2-core cloud machine, not a dedicated benchmark computer. Read them as orders of magnitude. The ratios of base counts are exact.
- Each size was timed on a single prime. Our loop is a plain one in Python over GMP, not an optimized implementation of Miller's test, and the 3072 and 4096-bit times are extrapolated.
- Bach's theorem is stated in his paper under the extended Riemann hypothesis, and Schoof states Miller's test under GRH for quadratic Dirichlet characters. We did not check that either proof claim covers the form the test needs.
- The prime-bases count is our own observation from how Bach's bound is proved, not a published result. The headline numbers use every integer base. If you rely on the prime-only count, check the argument.
Data and code
The full data (every library, round count, note and source file), the two tables as CSV, and the Python script that produced Part B. The script needs only gmpy2 and prints what it measures and what it extrapolates.
prime-testing-grh.json · prime-testing-grh.csv · prime-testing-grh-libraries.csv · prime-testing-grh.py
Sources
Library source files are linked from the table and listed with fingerprints in the data file. Other sources, read on 20 and 21 November 2026:
- NIST, FIPS 186-5, Digital Signature Standard, February 2023, Appendix B.3 and Table B.1: nvlpubs.nist.gov.
- Eric Bach, "Explicit bounds for primality testing and related problems", Mathematics of Computation 55 (1990), 355-380: ams.org.
- Gary L. Miller, "Riemann's hypothesis and tests for primality", Journal of Computer and System Sciences 13 (1976), 300-317: sciencedirect.com.
- Michael O. Rabin, "Probabilistic algorithm for testing primality", Journal of Number Theory 12 (1980), 128-138: sciencedirect.com.
- Ivan Damgård, Peter Landrock, Carl Pomerance, "Average case error estimates for the strong probable prime test", Mathematics of Computation 61 (1993), 177-194: ams.org.
- René Schoof, "Four primality testing algorithms", section 1: arXiv:0801.3840.
- Keith Conrad, "The Miller-Rabin test", expository notes, sections 2, 3 and 5: kconrad.math.uconn.edu.
- Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), 781-793: annals.math.princeton.edu.
Questions and answers
How does software check that a number is prime?
Most cryptographic libraries use the Miller-Rabin test: a few rounds with random bases, often after trial division by small primes. Of the 12 libraries we read, 10 do this for RSA keys, and 2 of those add a Lucas test.
How many Miller-Rabin rounds are used for an RSA-2048 key?
Between 2 and 8 in the libraries we read, for each 1024-bit prime. FIPS 186-5 sets a minimum of 5 rounds for an error probability of 2-112.
Would a proof of the generalized Riemann hypothesis change how primes are tested?
It would make Miller's 1976 deterministic test a proof of primality. For a 1024-bit prime that test tries 1,007,581 bases instead of 5 random rounds, so it is unlikely that any library would adopt it.
Is a "probable prime" a security risk?
Not for keys you generate yourself. The libraries that state a target give error probabilities between 2-80 and 2-144 for a random candidate. The low round counts are not meant for numbers chosen by an attacker, and several libraries use 64 rounds for those.
Can primality be proved without any hypothesis?
Yes. The AKS test (2002) is a deterministic polynomial-time proof with no assumption, and practical methods exist too. Nettle, used by GnuTLS, builds RSA primes that come with a proof.
