Vaultan

Home › Research › How encryption software tests for prime numbers, and what a proof of GRH would change

How encryption software tests for prime numbers, and what a proof of GRH would change

Every RSA key starts with two large primes, and software cannot afford to prove they are prime the slow way. We read the source code of 12 cryptographic libraries to see what they do instead, then measured the test that a proof of the generalized Riemann hypothesis (GRH) would make rigorous.

Source files read on 20 November 2026. Timings measured on 21 November 2026. This study was prepared by Gridlock App LLC, the publisher of Vaultan.

This study accompanies Does a proof of the Riemann hypothesis break encryption? Two proofs were announced on 20 November 2026 and neither has been peer reviewed. Nothing below depends on either being correct.

Summary

Part A: what each library does

Miller-Rabin rounds run on a candidate that keeps passing, when generating one RSA prime with default settings. A 512-bit prime is for a 1024-bit key, 1024 for 2048, 1536 for 3072 and 2048 for 4096. Source files are linked in the last column and were read on 20 November 2026.

LibraryTest512-bit1024-bit1536-bit2048-bitError bound stated in the sourceNotesSource
OpenSSLMiller-Rabin after trial division64544The 64-round path is commented as giving a false positive rate of 2^-128 (128 rounds above 2048 bits: 2^-256). The 5 and 4 round counts are taken from FIPS 186-5 Table B.1.Standard two-prime keys of 2048 bits or more with a public exponent above 65536 use the FIPS 186-5 routine: 5 rounds for a modulus under 3072 bits, 4 from 3072 bits. Smaller keys and multi-prime keys use the older routine, which runs the minimum of 64 rounds (128 above 2048 bits). BN_check_prime, for numbers of unknown origin, uses the same 64 or 128.[1] [2] [3]
BoringSSLMiller-Rabin after trial division5544Round counts are generated from the formula in FIPS 186-5 for a stated security level per size (80 bits at 476 to 851 bits, 112 bits from 852, 128 bits from 1080). Checking a prime supplied by someone else uses 64 rounds, stated as at most 2^-128.The count is the number of uniformly random bases. To hide timing, the loop runs at least 16 iterations on a number that keeps passing, so the two secret primes see 16 or more.[1] [2] [3]
LibreSSLBaillie-PSW: Miller-Rabin base 2, one random-base round, strong Lucas-Selfridge2222None stated in the files read for the generation path.Prime generation calls the Baillie-PSW test with one extra random-base round: 2 Miller-Rabin rounds in all (base 2 plus one random base), then a Lucas test. BN_is_prime_ex with the default setting adds 5 or 4 random rounds by size instead of one.[1] [2] [3] [4]
Nettle (used by GnuTLS)Provable primes: Maurer's algorithm with Pocklington's theorem––––Not applicable: the construction yields a proof that the number is prime.RSA key generation calls nettle_random_prime, which builds each prime from a smaller proven prime. GnuTLS calls this routine by default; in FIPS mode or with the provable flag it uses the FIPS 186-4 provable-prime construction instead.[1] [2] [3]
Libgcrypt (used by GnuPG)Fermat test base 2, then Miller-Rabin5555None stated for the standard path. The FIPS path cites FIPS 186-4 Table C.2. Checks of numbers that may not be random use 64 rounds.The first Miller-Rabin round uses base 2, the rest random bases. The FIPS path asks for 5 rounds up to 1024 bits and 4 above, but the test routine raises any count below 5 to 5.[1] [2]
Mozilla NSSFermat test base 2, then Miller-Rabin after sieving7543None stated as a number. The comment says the counts come from the Handbook of Applied Cryptography, table 4.4, with the FIPS 186 tables C.2 and C.3.RSA key generation calls generate_prime, which calls mpp_make_prime with securely random bases.[1] [2] [3]
Go crypto/rsaMiller-Rabin after trial division5544The comment cites a worst-case false positive rate of 1/4 per round and says 64 rounds would be needed for adversarial input; the lower counts rely on the candidate being random. It points to BoringSSL for the formula.Trial division by the odd primes up to 1619 first. The general-purpose big.Int.ProbablyPrime(n) is a different routine: n Miller-Rabin rounds plus a Baillie-PSW test, documented as 100% accurate below 2^64.[1] [2]
OpenJDK (BigInteger)Miller-Rabin, then a Lucas-Lehmer test8222The documentation of probablePrime says the chance that the result is composite does not exceed 2^-100.The RSA key pair generator calls BigInteger.probablePrime, which uses certainty 100. The comment says the round counts follow the draft standard ANSI X9.80.[1] [2]
Bouncy Castle (Java)Miller-Rabin after a small-factor check55412Expressed as a certainty: 80 for keys up to 1024 bits, 112 for 2048, 128 for 3072, 144 for 4096 (cited to FIPS 186-4 Table C.1). Rounds follow FIPS 186-4 tables C.2 and C.3, with extra rounds at the worst-case rate above them.Counts are for the provider's default certainty at each key size. A caller of the low-level class can pass a different certainty.[1] [2] [3]
wolfSSLMiller-Rabin after trial division by the first 256 primes8888None stated as a number in the file read.The same 8 rounds with random bases for every key size.[1]
Mbed TLS (TF-PSA-Crypto)Miller-Rabin after a small-factor check86442^-80 for keys up to 1024 bits and 2^-100 for larger keys, with counts cited to the Handbook of Applied Cryptography (table 4.4 and fact 4.48).RSA key generation asks for the lower error rate when the modulus is longer than 1024 bits.[1] [2]
Python cryptographyCalls OpenSSL––––See OpenSSL.RSA key generation calls the OpenSSL library the package is built against, so the test is whatever that library does.[1]

Part B: what Miller's test would cost

Bach's bound is 2(ln n)² for the largest n of each size. Counts are exact. Times are from one 2-core cloud machine (Intel(R) Xeon(R) Processor @ 2.10GHz) with GMP 6.3.0, with nothing else running: its 1-minute load average was 0.41 at the start and at most 1.43 during the run, about 1 of which is the test itself. The summary compares whole-test times with the mean time of a round.

Size of the prime (bits)Bach's boundBases, all integersBases, primes onlyBases ÷ 64 roundsOne Miller-Rabin round (median)Whole test, all integer basesWhole test, prime bases only
512251,895251,89422,1943,9360.059 ms16 seconds
estimated: time per base × bases
1.4 seconds
measured, run to the end
10241,007,5821,007,58179,06015,7430.36 ms7 minutes
estimated: time per base × bases
32 seconds
measured, run to the end
15362,267,0612,267,060167,26435,4231.2 ms43 minutes
estimated: time per base × bases
3 minutes
measured, run to the end
20484,030,3314,030,330285,15062,9742.7 ms2.9 hours
estimated: time per base × bases
12 minutes
measured, run to the end
30729,068,2469,068,245606,682141,6918 ms21.6 hours
estimated: time per base × bases
87 minutes
extrapolated from 2,003 sampled bases
409616,121,32716,121,3261,038,400251,89618 ms3.4 days
estimated: time per base × bases
5.3 hours
extrapolated from 2,001 sampled bases

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:

  1. NIST, FIPS 186-5, Digital Signature Standard, February 2023, Appendix B.3 and Table B.1: nvlpubs.nist.gov.
  2. Eric Bach, "Explicit bounds for primality testing and related problems", Mathematics of Computation 55 (1990), 355-380: ams.org.
  3. Gary L. Miller, "Riemann's hypothesis and tests for primality", Journal of Computer and System Sciences 13 (1976), 300-317: sciencedirect.com.
  4. Michael O. Rabin, "Probabilistic algorithm for testing primality", Journal of Number Theory 12 (1980), 128-138: sciencedirect.com.
  5. 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.
  6. René Schoof, "Four primality testing algorithms", section 1: arXiv:0801.3840.
  7. Keith Conrad, "The Miller-Rabin test", expository notes, sections 2, 3 and 5: kconrad.math.uconn.edu.
  8. 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.

Research