Random Primes Generation
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
- random generation of a
kbits integer in the interval;
- 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.
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/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
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
q = 1-p), the number of attempts before observing a success is on average
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·E[Y] = p·(1·q + 2·q^2 + 3·q^3 + 4·q^4 + ... + n·q^n)
q·E[Y] = (1-p)·E[Y] from
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
1/p. The last addend
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
A brute force approach to check if a number
n is prime is an exhaustive search
of a prime factor up to
A composite number should have at least one divisor
x less than or equal
If not, then it has at least two divisors
y greater than
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(n) = 'true' if n is probably prime, 'false' if is compsite
true the error probability
ε (meaning that
n is composite)
is directly related to the algorithm
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,
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
times in a row is thus
Extract a random number
x ∈ [2, n-1] and compute
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)
pi the primes in the factorization of
ε 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
n is not prime it is very unlikely to choose a number (a witness)
that is not coprime with
In case of RSA we have two big
q, so given
n = p·q there is a very
low probability we end up choosing
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
ε = φ(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.
Extends the naive approach by applying the Fermat’s little theorem to a candidate.
Fermat’s Little Theorem. Given a prime number
pand a number
(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
(n-1) bases as the Fermat
1 for all
n and for all odd
n, respectively. Thus
doesn’t add any value to test such values. That is:
x = 1:
1^(n-1) ≡ 1 (mod n) ∀ n
x = n-1: if
n = 2k + 1→
n-1 = 2kfor some
(n-1)^(n-1) ≡ (-1)^2k mod n ≡ 1 (mod n)
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
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
algorithm must perform well in
Zn*. That is, in general we’re going to search
for a witness in
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).
x is not invertible modulo
x·x^(n-2) = 1 (mod n)
doesn’t have a solution.
A composite number
n which satisfies
x^(n-1) ≡ 1 (mod n) for all integers
x which are relative prime to
In other words, excluded the numbers that are not relative prime to
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
x^(n-1) ≡ x^[(n-1) mod φ(n)] ≡ 1 (mod n) for any
x. Thus, in this case
would be a Carmichael number.
But this is not a mandatory condition, there are Carmichal numbers for which
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
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
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.
Extends the Fermat test by applying the quadratic reminders’ property to a candidate.
QR Theorem. Given a prime number
x < p, then:
x^2 ≡ 1 (mod p) iff x ≡ ±1 (mod p)
(←) 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
3^2 ≡ 1 (mod 8) and
3 ≢ ±1 (mod 8), thus
8 can’t be prime.
∃ x such that
x^2 ≡ 1 (mod p) then
1 is a quadratic residue modulo
The theorem gives us another tool to search for a witness.
A(x,n) = Miller-Rabin predicate
Given an odd prime candidate
n, we decompose
n-1 into its odd and even
(n - 1) = m·2^r , with m odd
We compute a sequence
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
n successfully passes the Fermat’s test then
xr = 1.
n is prime, then for the QR theorem we have that if
xi = 1 then
x(i-1) ≡ ±1 (mod n).
x0 ≡ ±1 then we can immediately return that it is probably prime.
x0 = ±1 then for any
i > 0 we have
xi = 1 and thus none of the
xi values is a witness.
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
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
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
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
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
This means that some factors of
n are in
(x-1) and some others are in
(n, x-1) and
(n, x+1) should return some non-trivial factors of
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.