Generating random primes and testing their primality is essential for many cryptographic algorithms. In this post, we’ll explore methods for generating and testing prime numbers.

What is this about

We want to develop an algorithm that generates a prime in the range [2ᵏ⁻¹, 2ᵏ-1], with k the number of bits required to represent the prime.

Approach:

1. generate of a k bits random integer in the interval;
2. test for primality.

During the random generation observe that for sure the most significant and least significant bits are set to 1 (primes are odd). The intermediate positions are randomly filled.

Termination

The algorithm probabilistically terminates, and we can give an upper bound estimation to the number of iterations. Given

π(n) = number of primes less than n

The Prime Number Theorem gives an asymptotic estimation for the number of primes less than a number n:

π(n) ≈ n/ln(n)

In other words the probability to randomly pick a prime in the set of the first n numbers is:

π(n)/n ≈ 1/ln(n)

This probability steadily decreases, but is always greater than 0.

With our random algorithm the probability to get a 2ᵏ bits prime on first attempt is thus:

π(2ᵏ)/(2ᵏ) ≈ 1/ln(2ᵏ) = 1/[k·ln(2)]

More exactly, since we are ignoring all even numbers, this probability should be doubled.

Note that for simplicity, we are intentionally ignoring the fact that we don’t pick the numbers in the range [0, 2ᵏ⁻¹ - 1]. In practice, we search in the upper half of the possible numbers.

The event to extract a prime can be associated to a Bernoulli’s variable that has a success probability p = 2/[k·ln(2)].

Expected number of attempts

Proposition. Given a Bernulli experiment with success probability p (q = 1-p), the number of attempts before observing a success is on average 1/p.

Proof

Let Y be the number of attempts before a success in a Bernulli experiment.

The probability of a success after the k attempts is:

Pr(Y = k) = qᵏ⁻¹·p

The expected value of Y, i.e. the expected number of attempts before observing a success is:

E[Y] = ∑ k·Pr(Y = k)
     = 1·p + 2·q·p + 3·q²·p + 4·q³·p + ... + n·qⁿ⁻¹·p
     = p·(1 + 2·q + 3·q² + 4·q³ + ...+ n·qⁿ⁻¹)

Multiplying both sides by q:

q·E[Y] = p·(1·q + 2·q² + 3·q³ + 4·q⁴ + ... + n·qⁿ)

Subtracting q·E[Y] = (1-p)·E[Y] from E[Y]

p·E[Y] = p·(1 + q + q² + ... + qⁿ⁻¹ + n·qⁿ)

E[Y] = 1 + q + q² + ... + qⁿ⁻¹ + n·qⁿ

The above contains an infinite geometric series with rational q < 1 and thus converges to 1/(1-q) = 1/p. The last addend (n·qⁿ) approaches 0 as n → ∞.

We can finally assert that E[Y] = 1/p

∎

On average, the number of attempts before observing a success is thus given by 1/p = k·ln(2)/2.

    k | ≈ attempts
------|------------
  100 |   34
 1000 |  346
10000 | 3465

Deterministic Primality Testing

A naive approach to check if a number n is prime is an exhaustive search for a prime factor up to √n.

A composite number should have at least one divisor x less than or equal √n. If not, then it has at least two divisors x and y greater than √n. Follows the impossible condition: n ≥ x·y > √n·√n = n.

Probabilistic Primality Testing

More efficient algorithms to check for primality are Montecarlo algorithms. Which means probabilistic algorithms that always terminate but may produce an incorrect result with a certain probability.

Given a Montecarlo primality test algorithm A:

A(n) = 'true' if n is probably prime, 'false' if is compsite

If A returns true the error probability ε (meaning that n is composite) is related to the algorithm A.

p(n is composite | A(n) = true) = ε

When n is probably prime then the algorithm A can be re-executed and the more it returns true the more likely is that n is indeed prime.

If the runs are independent, then the probability that the algorithm fails k times in a row is thus εᵏ.

If, during the various runs, A returns false once then we can immediately stop and assert that the number is composite.

p(n is composite | A(n) = false) = 1

In other words the algorithm produces only false negatives, never false positives.

Naive Approach

Extract a random number x ∈ [2, n-1] and compute gcd(x,n).

A(n) = 'true' if gcd(x,n) = 1 else 'false'

A witness is a number that allow A to decide that n is not prime.

In this case ε, the probability that gcd(x,n) = 1 when n is not prime, is equal to the probability of choosing x coprime with n. In other words the probability of choosing x ∈ Zₙ* with |Zₙ*| = φ(n).

ε ≈ φ(n)/n = n·∏(1 - 1/pᵢ)/n = ∏(1 - 1/pᵢ)

With pᵢ the primes in the factorization of n.

The more ε is small the higher is the probability to find a witness.

If the prime factors are all big then with this test ε ≈ 1. This means that even though n is not prime it is very unlikely to choose a number (a witness) that is not coprime with n.

In case of RSA we have two big primes p and q, so given n = p·q there is a very low probability to end up choosing a multiple of p or q during our primality test. In this case the probability to choose a witness is 1 - ε = (p + q - 1)/n, which tends to zero.

With this test we can’t fix an error probability ε below an upper bound < 1.

Probabilistically ε = φ(n)/n ≈ 1, that is φ(n) is typically very close to n. Follows that we have to find a better algorithm to find a witness.

Fermat Test

Extends the naive approach by applying the Fermat’s little theorem to a candidate.

Fermat’s Little Theorem. Given a prime number p and a number x such that (x,p) = 1, then xᵖ⁻¹ ≡ 1 (mod p)

Given a candidate n, the idea is to randomly choose 1 < x < n-1 and compute xⁿ⁻¹ mod n. If the result is not 1 then for sure n is not prime, thus we return false.

The result follows because if n is prime and x < n then for sure (x,n) = 1 and the Fermat’s little theorem must hold.

Note that we are not going to test 1 and (n-1) as the Fermat expression returns 1 for all n and for all odd n, respectively. The test is always successful for such values, regardless of x:

• For x = 1: 1ⁿ⁻¹ ≡ 1 (mod n) ∀ n
• For x = n-1: if n = 2·k + 1 → n-1 = 2·k for some k. Thus(n-1)ⁿ⁻¹ ≡ (-1)²ᵏ mod n ≡ 1 (mod n)

If xⁿ⁻¹ ≡ 1 (mod n), then n may be prime with a certain error probability ε.

Fermat Witness. x ∈ Zₙ with 1 < x < n-1 and xⁿ⁻¹ ≢ 1 (mod n).

Because the number of x such that (x,n) = 1 is generally close to n, our algorithm must perform well in Zₙ*. That is, in general we’re going to search for a witness in Zₙ*.

Generally, composite numbers have a fairly high number of Fermat’s witnesses, but unfortunately there are some composite numbers that doesn’t have any witness (Carmichael numbers). Follows that there is no upper bound to the error probability.

Note that if (x,n) ≠ 1 then xⁿ⁻¹ ≢ 1 (mod n).

Proof: if xⁿ⁻¹ ≡ 1 (mod n) then x·xⁿ⁻² ≡ 1 (mod n). Follows that x have an inverse modulo n, but this is not possible as (x,n) ≠ 1.

Carmichael Numbers

A composite number n which satisfies xⁿ⁻¹ ≡ 1 (mod n) for all integers x which are relative prime to n.

In other words, excluded the (small set of) numbers that are not relative prime to n, n doesn’t have any Fermat witness.

A Carmichael number is thus a number for which the Fermat’s theorem always holds even if it is composite.

Using Euler’s theorem, we can assert that if φ(n)|(n-1) then xⁿ⁻¹ ≡ x^[(n-1) mod φ(n)] ≡ 1 (mod n) for any x. Thus, in this case n would be a Carmichael number.

Lehmer’s totient problem. Lehmer conjectured in 1939 that there are no composite numbers with this property.

But this is not a necessary condition, as for all known Carmichal numbers φ(n)∤(n-1).

Theorem. There are Carmichael numbers.

Proof. We prove that 561 = 3·11·17 is a Carmichael number (the first indeed) by proving that ∀ x if (x,561) = 1 then x⁵⁶⁰ mod 561 = 1.

Using the Little Fermat theorem corollary, for each prime factors pᵢ of 561, we can easily check that:

x⁵⁶⁰ ≡ x^(560 mod (pᵢ-1)) ≡ x^[(3·11·17 - 1) mod (pᵢ-1)] ≡ 1 (mod pᵢ)

Thus, using the CRT, x⁵⁶⁰ can be represented as (1, 1, 1).

m = 3·11·17 = 561

c₁ = (11·17) · [(11·17)⁻¹ (mod 3)] = 187·1 = 187
c₂ = (3·17) · [(3·17)⁻¹ (mod 11)] = 51·8 = 408
c₃ = (3·11) · [(3·11)⁻¹ (mod 17)] = 33·16 = 528

X = ∑ (xᵢ·cᵢ) = 1·187 + 1·408 + 1·528 = 1123 ≡ 1 (mod 561)

The solution modulo m is unique and thus x⁵⁶⁰ ≡ 1 (mod 561).

∎

Given that the majority of numbers less than n are relative prime to n, follows that is very hard to find a witness for Carmichael numbers. That is, we have to be lucky enough to pick x such that (x,n) ≠ 1.

Carmichael numbers can be tabulated up to an upper bound. But this is limited and indeed there relatively small pre-built tables.

Miller-Rabin Test

Extends the Fermat test by applying the quadratic remainders’ property to a candidate.

Quadratic remainders

QR Theorem. Given a prime number p and x < p, then:

x² ≡ 1 (mod p) iff x ≡ ±1 (mod p)

Proof:

(←) if `x ≡ ±1 (mod p)` then obviously `x² ≡ 1 (mod p)`

(→) if x² ≡ 1 (mod p) → (x² - 1) ≡ (x - 1)·(x + 1) ≡ 0 (mod p)
→ p | (x - 1)·(x + 1)  →  (because p is prime)  →  p | (x - 1) or p | (x + 1)
If p | (x - 1)  →  x - 1 ≡ 0 (mod p)  →  x ≡  1 (mod p)
If p | (x + 1)  →  x + 1 ≡ 0 (mod p)  →  x ≡ -1 (mod p)

The theorem says that if p is prime, x is its self inverse iff x ≡ ±1 (mod p).

Reformulating the theorem to apply it to our primality test:

if x² ≡ 1 (mod p) and x ≢ ±1 (mod p) then p can't be prime

Example. 3² ≡ 1 (mod 8) and 3 ≢ ±1 (mod 8), thus 8 can’t be prime.

If ∃ x such that x² ≡ 1 (mod p) then 1 is a quadratic residue modulo p.

The theorem gives us another tool to search for a witness.

A(x,n) = Miller-Rabin predicate

Miller-Rabin predicate

Given an odd prime candidate n, we decompose n-1 into its odd and even factors:

(n - 1) = m·2ʳ , with m odd

We compute a sequence {xᵢ} for i = 1..r

x₀ = x^(m·2⁰) mod n
...
xᵢ = x^(m·2ⁱ) mod n
...
xᵣ = x^(m·2ʳ) mod n = xⁿ⁻¹ mod n

Note that the last element of the sequence xᵣ is equal to xⁿ⁻¹, thus if n successfully passes the Fermat’s test then xᵣ = 1.

If n is prime, then for the QR theorem we have that if xᵢ = 1 then xᵢ₋₁ ≡ ±1 (mod n).

If x₀ ≡ ±1 then we can immediately return that it is probably prime. Indeed, if x₀ = ±1 then for any i > 0 we have xᵢ = 1 and thus none of the xᵢ values is a witness.

If x₀ ≢ ±1 then at some point we must find xᵢ ≡ 1. In this case n may be prime for QR theorem only if xᵢ₋₁ ≡ -1, otherwise is composite.

The predicate thus returns false (composite) if:

x₀ ≢ ±1 and ∀i in [1,..,r-1] xᵢ ≢ -1

The error probability ε is the probability to choose x that is not a Rabin witness for a composite number n. In other words we found xᵢ = -1 in the sequence.

Theorem. Every odd composite number n has at least (3/4)·n Rabin witnesses.

The probability of not choosing a witness during the test run is thus ε < 1/4.

Note that there is an easier to prove, companion theorem that shows that there are at least n/2 Rabin witness.

Miller-Rabin test also gives a proof of compositeness represented by the sequence x₀...xₖ.

Factorization attempt

The factorization problem is an independent problem, thus in general primality testing doesn’t help a lot here. But there is an exception.

If we find a non-trivial root of 1 modulo n, for the QR theorem we know that n can’t be prime.

x ≢ ±1  ∧  x² ≡ 1 (mod n)
→  x² - 1 ≡ (x-1)(x+1) ≡ 0 (mod n)  →  n | (x-1)(x+1)

The factors of n should thus be in the product (x-1)(x+1).

They cannot all be in the first factor, otherwise n | (x-1) → x = 1 (mod n). And this can’t be true by hypothesis. A similar result applies to (x+1).

This means that some factors of n are in (x-1) and some others are in (x+1).

Thus, (n, x-1) and (n, x+1) should return some non-trivial factor of n.

The Carmichael numbers are the ones that are really vulnerable since are the ones that are mostly caught by the QR theorem of Miller Rabin.

Quadratic Sieving is a factorization method which leverage this weakness.

References

• Carmichael Numbers OEIS
• Fast Rust implementation using num-bigint and rayon here