I think prime numbers are the quiet workhorses behind almost every public-key cryptosystem I’ve ever studied. Whenever I generate an RSA key pair, or set up Diffie-Hellman parameters, the very first thing that has to happen behind the scenes is finding a large prime number — often 1024, 2048, or even 4096 bits long. What I find genuinely interesting is that we don’t actually prove these huge numbers are prime in the strict mathematical sense most of the time; instead, we use probabilistic primality tests that make the chance of error so astronomically small that it’s considered secure enough for real-world cryptography. In this file, I want to walk through how large primes are generated and tested in practice.
History and Background
I trace the mathematical study of primality testing back centuries, to the Sieve of Eratosthenes from ancient Greece, which is still the simplest method for finding all small primes up to some bound. But the modern cryptographic need — testing whether an enormous, randomly chosen number (hundreds of digits long) is prime, quickly — is a much more recent story. Fermat’s Little Theorem, from the 17th century, provided an early necessary (but not sufficient) condition for primality, which became the basis of the Fermat primality test. In 1976, Gary Miller proposed a primality test based on the (then-unproven) extended Riemann hypothesis; Michael Rabin turned it into a practical probabilistic algorithm in 1980, giving us the Miller-Rabin test, which remains the most widely used primality test in cryptographic libraries today. Meanwhile, in 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena published the AKS primality test, which was the first algorithm proven to determine primality in deterministic polynomial time for any input — a landmark theoretical result, even though it’s slower in practice than probabilistic tests for cryptographic-sized numbers.
Problem Statement
The problem I need to solve is twofold: first, given a candidate integer, determine (with very high confidence, or with certainty for smaller numbers) whether it is prime; second, generate a large random integer that is prime, suitable for use as a cryptographic parameter (like an RSA modulus factor). Because truly deterministic primality proofs for enormous numbers were historically slow, cryptography almost universally relies on probabilistic tests that can be made arbitrarily confident by repeating them, trading a vanishingly small (and controllable) error probability for dramatically better performance.
Core Concepts
- Primality test – an algorithm that determines whether a given number is prime, either definitively (deterministic test) or with high probability (probabilistic test).
- Trial division – the simplest primality check: dividing the candidate by all integers up to its square root; efficient for small numbers, hopelessly slow for cryptographic-sized numbers.
- Fermat’s Little Theorem – states that for a prime $p$ and any integer $a$ not divisible by $p$, $a^{p-1} \equiv 1 \pmod{p}$; used as the basis of the Fermat test, though it has known exceptions (Carmichael numbers) that can fool it.
- Miller-Rabin test – a stronger probabilistic test based on properties of square roots of unity modulo a prime, which has no equivalent of Carmichael numbers (no composite number fools it for more than 1/4 of possible witnesses).
- Witness – a randomly chosen base used in a probabilistic primality test; if a witness reveals the number is composite, the test is conclusive; if not, confidence in primality increases.
- Sieve of Eratosthenes – a method for finding all primes up to a bound by iteratively marking multiples of each prime as composite; used as a fast pre-filter before applying expensive probabilistic tests to large random candidates.
How It Works
I typically generate a large prime for cryptographic use with a pipeline like this:
- I generate a random odd integer of the desired bit length (odd because even numbers greater than 2 can never be prime).
- I run quick trial division by small primes (2, 3, 5, 7, 11, … up to some small bound like a few hundred or a thousand) to immediately reject candidates with small factors — this is cheap and filters out the vast majority of composite candidates before I invest in expensive probabilistic testing.
- For any candidate surviving the sieve step, I run the Miller-Rabin test with several randomly chosen witness bases.
- If the candidate passes all the Miller-Rabin rounds, I accept it as prime (with an error probability I control by choosing the number of rounds — commonly 20+ rounds are used in cryptographic libraries, driving the false-positive probability down to less than $4^{-20}$, astronomically small).
- If the candidate fails at any stage, I discard it and generate a new random candidate, repeating the whole process.
- For applications requiring extremely high assurance, I may follow up with a deterministic primality proof (like a Lucas-based certificate or, more rarely, AKS) on the final candidate, though in most cryptographic practice, sufficiently many Miller-Rabin rounds are considered adequate.
Working Principle
The Miller-Rabin test, which I rely on most, works by refining Fermat’s Little Theorem to also check the behavior of square roots of unity. If $n$ is prime, then the only square roots of 1 modulo $n$ are $1$ and $-1$ (this follows because $\mathbb{Z}_n$ is a field when $n$ is prime, and $x^2 \equiv 1 \pmod n$ factors as $(x-1)(x+1) \equiv 0$, meaning $x \equiv \pm 1$). Miller-Rabin writes $n – 1 = 2^s \cdot d$ (factoring out all powers of 2), then computes $a^d \bmod n$ and repeatedly squares it, checking at each step whether the sequence unexpectedly produces a square root of 1 other than $\pm 1$ — if it does, $n$ is definitely composite (this is called a “nontrivial square root,” and its existence is impossible modulo a prime). If no such violation occurs across all the squarings for a given witness $a$, the number passes that round; repeating with multiple independent random witnesses drives down the probability that a composite number could pass every round purely by chance.
Mathematical Foundation
Fermat’s Little Theorem: for prime $p$ and integer $a$ with $\gcd(a,p)=1$:
$$a^{p-1} \equiv 1 \pmod{p}$$
Miller-Rabin setup: write $n – 1 = 2^s d$ with $d$ odd. A number $n$ is declared “probably prime” with respect to witness $a$ if either:
$$a^d \equiv 1 \pmod{n}$$
or there exists some $r$ with $0 \le r < s$ such that:
$$a^{2^r d} \equiv -1 \pmod{n}$$
If neither condition holds for any $r$, then $n$ is definitely composite (this is a mathematically rigorous conclusion, not probabilistic — a composite fails to satisfy Fermat/Miller-Rabin identically to how a prime does, and this test’s structure guarantees the violation is detected).
Error bound: for a random odd composite $n$, the probability that a single randomly chosen witness $a$ fails to detect compositeness is at most $\frac{1}{4}$. Repeating with $k$ independent witnesses reduces the false-positive probability to at most:
$$4^{-k}$$
So for $k = 20$ rounds, the probability of incorrectly declaring a composite number prime is at most $4^{-20} \approx 9.1 \times 10^{-13}$, a risk considered negligible for essentially all cryptographic purposes.
Density of primes (Prime Number Theorem): the number of primes less than $x$ is approximately:
$$\pi(x) \sim \frac{x}{\ln x}$$
which tells me that the “density” of primes near a large number $N$ is roughly $\frac{1}{\ln N}$, so I expect, on average, to test about $\ln N$ random odd candidates near $N$ before finding one that’s prime — this is what makes random-candidate-generation-and-testing a practical strategy rather than a hopeless search.
Diagrams
flowchart TD
A[Generate random odd candidate n of target bit length] --> B[Trial division by small primes]
B --> C{Divisible by any small prime?}
C -- Yes --> A
C -- No --> D[Run Miller-Rabin with k random witnesses]
D --> E{Passes all k rounds?}
E -- No, composite detected --> A
E -- Yes --> F[Accept n as prime with error less than 4^-k]
Pseudocode
function generate_large_prime(bit_length, rounds):
while true:
candidate = random_odd_integer(bit_length)
if passes_small_prime_filter(candidate):
if miller_rabin(candidate, rounds):
return candidate
function passes_small_prime_filter(n):
for p in small_primes_list: // e.g., 2, 3, 5, 7, ..., 997
if n mod p == 0 and n != p:
return false
return true
function miller_rabin(n, rounds):
if n < 2: return false
if n == 2 or n == 3: return true
if n mod 2 == 0: return false
// write n-1 as 2^s * d with d odd
d = n - 1
s = 0
while d mod 2 == 0:
d = d / 2
s = s + 1
for i in 1..rounds:
a = random_integer(2, n - 2)
x = pow_mod(a, d, n)
if x == 1 or x == n - 1:
continue // passes this round
composite = true
for r in 1..s-1:
x = (x * x) mod n
if x == n - 1:
composite = false
break
if composite:
return false // definitely composite
return true // probably prime
Step-by-Step Example
I’ll test the small number n = 221 (which is 13 * 17, so it’s composite — a good test case since it’s known to fool the basic Fermat test with some bases) using Miller-Rabin.
n - 1 = 220 = 2^2 * 55, sos = 2,d = 55.- I pick a witness, say
a = 174. - I compute
x = 174^55 mod 221. Working this out (using fast modular exponentiation), I getx = 47. - Is
x == 1orx == 220? No,47is neither. - I enter the squaring loop, for
r = 1(sinces-1 = 1):x = 47^2 mod 221 = 2209 mod 221 = 2209 - 9*221 = 2209-1989=220. x == 220 == n-1, so this round passes (174 does not reveal 221 as composite).- I try a second witness, say
a = 137. - I compute
x = 137^55 mod 221 = 188(via modular exponentiation). xis neither1nor220.- Squaring loop,
r=1:x = 188^2 mod 221 = 35344 mod 221.221*159 = 35139, so35344-35139=205. x = 205, not220, and I’ve exhausted my squaring rounds (s-1=1iteration only) — so this witness reveals221as composite.- Since witness
137detected compositeness, Miller-Rabin correctly concludesn = 221is not prime — matching the known factorization13*17.
This example is a classic one I like because it also shows why a single witness (like 174) isn’t always enough — this is exactly why multiple independent rounds with different random witnesses are used in practice.
Time Complexity
- Trial division up to $\sqrt{n}$: $O(\sqrt{n})$, which is exponential in the bit-length of $n$ (since $n$ has roughly $\log n$ bits, $\sqrt{n} = O(2^{(\log n)/2})$) — hopelessly slow for cryptographic-sized numbers, but useful as a cheap pre-filter against small factors.
- Miller-Rabin (single round): dominated by the modular exponentiation, which is $O(\log^3 n)$ using schoolbook multiplication, or faster with more advanced multiplication algorithms; for $k$ rounds, total time is $O(k \log^3 n)$.
- AKS primality test: proven deterministic polynomial time, originally $O(\log^{12} n)$ in the first published version, later improved to around $O(\log^6 n)$ with refinements — theoretically important, but slower in practice than Miller-Rabin for the sizes used in real cryptography, which is why it’s rarely used operationally.
- Overall prime generation: given the Prime Number Theorem’s density estimate, I expect to test around $O(\log n)$ random candidates before finding a prime, so total expected generation time is roughly $O(k \log^4 n)$ (candidates tested times cost per Miller-Rabin test).
Space Complexity
Both trial division and Miller-Rabin require only $O(\log n)$ space to store the candidate and intermediate values during modular exponentiation (since big-integer arithmetic representations scale with the bit-length of $n$), plus a small fixed table of small primes for the pre-filtering step. This makes primality testing very memory-efficient even for very large cryptographic key sizes.
Correctness Analysis
Miller-Rabin’s correctness rests on the mathematical fact I described earlier: if $n$ is truly prime, every witness $a$ (coprime to $n$) will satisfy the test conditions, since $\mathbb{Z}_n^*$ being a field guarantees no nontrivial square roots of unity exist — so a prime number will never be incorrectly rejected (there are no false negatives). The one-sided error is in the other direction: it’s mathematically proven that for any composite $n$, at most 1/4 of the possible witnesses in $[2, n-2]$ will fail to reveal compositeness — this bound was proven rigorously by Rabin, building on Miller’s earlier deterministic version (which itself relied on the unproven extended Riemann hypothesis for a slightly different, deterministic guarantee). Because this per-round error is bounded and independent across randomly chosen witnesses, repeated rounds multiply the error bound down, giving me a provably tiny (though not literally zero) probability of error for any fixed number of rounds.
Advantages
- Miller-Rabin is extremely fast in practice, letting cryptographic libraries generate 2048-bit or larger primes in a reasonable amount of time, which would be completely infeasible with trial division.
- The error probability is precisely quantifiable and can be driven arbitrarily low simply by adding more rounds, giving implementers a clear, tunable security/performance tradeoff.
- It never falsely rejects a true prime, so I never need to worry about accidentally discarding a genuinely prime candidate.
Disadvantages
- It is fundamentally probabilistic, not a proof of primality — for applications demanding absolute certainty (rare in practice, but they exist in some formal number-theoretic contexts), a deterministic test or a primality certificate is needed instead.
- A maliciously chosen candidate (rather than a randomly generated one) could, in principle, be constructed to have a much higher chance of fooling Miller-Rabin with a small, fixed, and known set of witnesses — this is why cryptographic implementations should always use randomly chosen witnesses for untrusted or adversarially-supplied candidates, not a small fixed set of small bases (a technique that is fine when the candidate itself is honestly randomly generated).
- Deterministic tests like AKS, while theoretically important, remain too slow for practical cryptographic key generation at current key sizes.
Applications
Prime generation underlies RSA key generation directly (an RSA modulus is the product of two large random primes), Diffie-Hellman and DSA parameter generation (finding a large prime modulus and a generator of appropriate order), and various other number-theoretic cryptographic constructions. Beyond cryptography, primality testing is also used in computational number theory research, in generating primes for hash table sizing and pseudo-random number generator design, and in recreational and competitive mathematics for search projects like finding new large Mersenne primes.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
/* modular exponentiation: base^exp mod mod, using unsigned 64-bit
with care to avoid overflow on multiplication (educational scale) */
uint64_t mulmod(uint64_t a, uint64_t b, uint64_t mod) {
return (uint64_t)(( (__uint128_t)a * b ) % mod);
}
uint64_t pow_mod(uint64_t base, uint64_t exp, uint64_t mod) {
uint64_t result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = mulmod(result, base, mod);
base = mulmod(base, base, mod);
exp >>= 1;
}
return result;
}
/* single Miller-Rabin round with a given witness */
int miller_rabin_round(uint64_t n, uint64_t a, uint64_t d, int s) {
uint64_t x = pow_mod(a, d, n);
if (x == 1 || x == n - 1) return 1; /* passes this round */
for (int r = 1; r < s; r++) {
x = mulmod(x, x, n);
if (x == n - 1) return 1;
}
return 0; /* composite, revealed by this witness */
}
int is_probable_prime(uint64_t n, int rounds) {
if (n < 2) return 0;
if (n == 2 || n == 3) return 1;
if (n % 2 == 0) return 0;
uint64_t d = n - 1;
int s = 0;
while (d % 2 == 0) { d /= 2; s++; }
for (int i = 0; i < rounds; i++) {
uint64_t a = 2 + rand() % (n - 3); /* random witness in [2, n-2] */
if (!miller_rabin_round(n, a, d, s)) {
return 0; /* definitely composite */
}
}
return 1; /* probably prime */
}
int main(void) {
srand((unsigned)time(NULL));
uint64_t test221 = 221;
uint64_t test_prime = 104729; /* known prime (10000th prime) */
printf("Is 221 probably prime? %s\n", is_probable_prime(test221, 20) ? "YES" : "NO");
printf("Is 104729 probably prime? %s\n", is_probable_prime(test_prime, 20) ? "YES" : "NO");
/* generate a random probable prime under 1,000,000 for demonstration */
uint64_t candidate;
do {
candidate = (uint64_t)(rand() % 999999) | 1; /* force odd */
} while (!is_probable_prime(candidate, 20));
printf("Randomly generated probable prime: %llu\n", (unsigned long long)candidate);
return 0;
}
I kept this implementation to 64-bit integers for clarity and portability; real cryptographic implementations use arbitrary-precision “big integer” libraries (like GMP or OpenSSL’s BIGNUM) to handle the 1024-4096 bit numbers actually used in RSA and Diffie-Hellman key generation.
Sample Input and Output
Input: testing n = 221 (composite, 13*17) and n = 104729 (a known prime) with 20 Miller-Rabin rounds, then generating a random probable prime under 1,000,000.
Output:
Is 221 probably prime? NO
Is 104729 probably prime? YES
Randomly generated probable prime: 613597
(The final randomly generated prime will vary between runs since it depends on the random seed, but it will always be a genuinely prime number, consistent with the Miller-Rabin guarantees described above.)
Optimization Techniques
- Filtering candidates against a precomputed table of small primes (the first few hundred, say) before running any Miller-Rabin rounds eliminates the vast majority of composite candidates cheaply, since most composites have small factors.
- Choosing candidates only from arithmetic progressions that are odd and not divisible by 3 (i.e., testing $6k \pm 1$ forms) immediately rules out two-thirds of all integers as candidates, without any division at all.
- Using efficient modular exponentiation (square-and-multiply, as I implemented above) instead of naive repeated multiplication reduces exponentiation cost from $O(n)$ multiplications to $O(\log n)$.
- For very large-scale prime generation (like RSA key generation), using Montgomery multiplication or other specialized modular arithmetic techniques substantially speeds up the repeated modular exponentiations that dominate Miller-Rabin’s cost.
- Running the first few rounds of Miller-Rabin with small, fixed witnesses (2, 3, 5, 7…) for numbers below certain well-studied thresholds is deterministic and proven correct for those specific ranges, letting implementations skip randomization entirely for smaller numbers.
Common Mistakes
- Using too few Miller-Rabin rounds for high-stakes cryptographic key generation, leaving an unnecessarily (if still small) elevated risk of accepting a composite number as prime.
- Reusing a small, fixed set of witnesses against adversarially chosen (not randomly generated) candidates, which can be deliberately crafted to fool those specific witnesses — random witness selection is important when the candidate’s origin isn’t trusted.
- Forgetting to handle small edge cases (
n < 2,n == 2, even numbers) explicitly before running the general Miller-Rabin loop, which can cause incorrect results or division-by-zero-style errors. - Using naive multiplication for very large numbers in modular exponentiation, causing integer overflow — this is why real implementations use big-integer libraries with proper overflow handling, and why I used the 128-bit intermediate
__uint128_ttype in my C example to avoid overflow at 64-bit scale. - Assuming a “probable prime” from Miller-Rabin is exactly as good as a full mathematical proof of primality in every possible context — while the error probability is negligible for essentially all practical purposes, contexts requiring absolute certainty should use additional primality-proving techniques.
Further Reading
- Rabin, M., “Probabilistic Algorithm for Testing Primality,” Journal of Number Theory, 1980: https://www.sciencedirect.com/science/article/pii/0022314X80900840
- Miller, G., “Riemann’s Hypothesis and Tests for Primality,” Journal of Computer and System Sciences, 1976: https://www.sciencedirect.com/science/article/pii/S0022000076800438
- Agrawal, M., Kayal, N., and Saxena, N., “PRIMES is in P,” Annals of Mathematics, 2004: https://annals.math.princeton.edu/2004/160-2/p12
- Menezes, van Oorschot, and Vanstone, Handbook of Applied Cryptography, Chapter 4: https://cacr.uwaterloo.ca/hac/about/chap4.pdf
- NIST FIPS 186-5, Digital Signature Standard (parameter and primality requirements): https://csrc.nist.gov/pubs/fips/186-5/final
