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.

Last modification: 2023-08-01

What is this about

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

Approach:

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

During the random generation we can 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 between less than n

The Prime Number Theorem gives an asymptotic estimate of 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 decreases, but is always greater than 0.

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

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

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

Note that in order to further simplify, we are intentionally ignoring the fact that we don’t pick the numbers in the range [0, 2^(k-1) - 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 equal to Pr = 2/[k·ln(2)].

Expected number of attempts

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

Proof

Let the variable Y be the expected number of attempts before success.

E[Y] = 1·p + 2·q·p + 3·q^2·p + 4·q^3·p + ... + n·q^(n-1)·p
     = p·(1 + 2·q + 3·q^2 + 4·q^3 + ...+ n·q^(n-1))

Multiplying both sides by q:

q·E[Y] = p·(1·q + 2·q^2 + 3·q^3 + 4·q^4 + ... + n·q^n)

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

p·E[Y] = p·(1 + q + q^2 + ... + q^(n-1) + n·q^n)

E[Y] = 1 + q + q^2 + ... + q^(n-1) + n·q^n

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

Thus, we can assert that E[Y] = 1/p

∎

The average number of attempts before observing a success is thus given by 1/Pr = k·ln(2)/2.

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

Primality Testing

A brute force approach to check if a number n is prime is an exhaustive search of 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.

More efficient algorithms to check for primality are Montecarlo probabilistic methods. Which means that the output may be incorrect with a certain probability.

Given a probabilistic 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 directly related to the algorithm A.

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, during the iterations, A returns false then we can immediately stop and assert that the number is composite.

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

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

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 ∈ Zn* with |Zn*| = φ(n).

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

With pi the primes in the factorization of n.

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

If the prime factors are all huge 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 p and q, so given n = p·q there is a very low probability we end up choosing p or q during our primality test. In this case the probability to choose a witness is 2/n, close to zero.

Reformulating the problem, 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^(p-1) ≡ 1 (mod p)

The idea is, given a candidate n, to randomly choose 1 < x < n-1 and compute x^(n-1) 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) bases as the Fermat expression returns 1 for all n and for all odd n, respectively. Thus doesn’t add any value to test such values. That is:

• For x = 1: 1^(n-1) ≡ 1 (mod n) ∀ n
• For x = n-1: if n = 2k + 1 → n-1 = 2k for some k. Thus(n-1)^(n-1) ≡ (-1)^2k mod n ≡ 1 (mod n)

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

As we’ll see there is no upper bound to this probability as for Carmichael numbers the modular reminder is always 1.

Fermat Witness. x ∈ Zn with 1 < x < n-1 and x^(n-1) ≢ 1 (mod n).

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

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.

Note that if (x,n) ≠ 1 then x^(n-1) ≠ 1 (mod n). Trivial proof: x is not invertible modulo n thus x·x^(n-2) = 1 (mod n) doesn’t have a solution.

Carmichael Numbers

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

In other words, excluded the 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 not prime.

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

But this is not a mandatory condition, there are Carmichal numbers for which φ(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^560 mod 561 = 1.

Using the Little Fermat theorem corollary, for each prime factors pi of 561:

x^560 ≡ x^(560 mod (pi-1)) ≡ x^[(3·11·17 - 1) mod (pi-1)] ≡ 1 (mod pi)
                             (... prove this by doing the math)

Thus, using the CRT, x^560 can be represented as (1, 1, 1).

m = 3·11·17 = 561

   c1 = (11·17) · [(11·17)^-1 (mod 3)] = 187·1 = 187
   c2 = (3·17) · [(3·17)^-1 (mod 11)] = 51·8 = 408
   c3 = (3·11) · [(3·11)^-1 (mod 17)] = 33·16 = 528

X = ∑ (xi·ci) = 1·187 + 1·408 + 1·528 = 1123 ≡ 1 (mod 561)

The solution modulo m is unique and thus x^560 ≡ 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 reminders’ property to a candidate.

Quadratic reminders

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

x^2 ≡ 1 (mod p) iff x ≡ ±1 (mod p)

Proof:

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

(→) if x^2 ≡ 1 (mod p) → (x^2 - 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^2 ≡ 1 (mod p) and x ≢ ±1 (mod p) then p can't be prime

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

If ∃ x such that x^2 ≡ 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^r , with m odd

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

x0 = x^m mod n
...
xi = x^(m·2^i) mod n
...
xr = x^(m·2^r) mod n = x^(n-1) mod n

Note that the last element of the sequence xr is equal to x^(n-1), thus if n successfully passes the Fermat’s test then xr = 1.

If n is prime, then for the QR theorem we have that if xi = 1 then x(i-1) ≡ ±1 (mod n).

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

If x0 ≢ ±1 then at some point we must find xi ≡ 1. In this case n may be prime for QR theorem only if x(i-1) ≡ -1, otherwise is composite.

The predicate thus returns false (composite) if:

x0 ≢ ±1 and ∀i in [1,..,r-1] xi ≢ -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 xi = -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 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 x0...xk.

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^2 ≡ 1 (mod n)
→  x^2 - 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 factors 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