only if 2n’1 ≡ 1 (mod n).

252 Probabilistic primality testing

Exercise 10.6. Here is another primality test that takes as input an odd

integer n > 1, and a positive integer parameter t. The algorithm chooses

±1 , . . . , ±t ∈ Z+ at random, and computes

n

(n’1)/2

βi := ±i (i = 1, . . . , t).

If (β1 , . . . , βt ) is of the form (±1, ±1, . . . , ±1), but is not equal to (1, 1, . . . , 1),

the algorithm outputs true; otherwise, the algorithm outputs false. Show

that if n is prime, then the algorithm outputs false with probability at most

2’t , and if n is composite, the algorithm outputs true with probability at

most 2’t .

In the terminology of §7.2, the algorithm in the above exercise is an exam-

ple of an “Atlantic City” algorithm for the language of prime numbers (or

equivalently, the language of composite numbers), while the Miller“Rabin

test is an example of a “Monte Carlo” algorithm for the language of com-

posite numbers.

10.4 Generating random primes using the Miller“Rabin test

The Miller“Rabin test is the most practical algorithm known for testing

primality, and because of this, it is widely used in many applications, espe-

cially cryptographic applications where one needs to generate large, random

primes (as we saw in §7.8). In this section, we discuss how one uses the

Miller“Rabin test in several practically relevant scenarios where one must

generate large primes.

10.4.1 Generating a random prime between 2 and M

Suppose one is given an integer M ≥ 2, and wants to generate a random

prime between 2 and M . We can do this by simply picking numbers at

random until one of them passes a primality test. We discussed this problem

in some detail in §7.5, where we assumed that we had a primality test

IsPrime. The reader should review §7.5, and §7.5.1 in particular. In this

section, we discuss aspects of this problem that are speci¬c to the situation

where the Miller“Rabin test is used to implement IsPrime.

To be more precise, let us de¬ne the following algorithm MR(n, t), which

takes as input integers n and t, with n > 1 and t ≥ 1, and runs as follows:

10.4 Generating random primes using the Miller“Rabin test 253

Algorithm MR(n, t):

if n = 2 then return true

if n is even then return false

repeat t times

± ←R {1, . . . , n ’ 1}

if ± ∈ Ln return false

return true

So we shall implement IsPrime(·) as MR(·, t), where t is an auxiliary

parameter. By Theorem 10.6, if n is prime, the output of MR(n, t) is always

true, while if n is composite, the output is true with probability at most 4’t .

Thus, this implementation of IsPrime satis¬es the assumptions in §7.5.1,

with = 4’t .

Let γ(M, t) be the probability that the output of Algorithm RP in §7.5”

using this implementation of IsPrime ”is composite. Then as we discussed

in §7.5.1,

M ’1

γ(M, t) ¤ 4’t = O(4’t k), (10.2)

π(M )

where k = len(M ). Furthermore, if the output of Algorithm RP is prime,

then every prime is equally likely; that is, conditioning on the event that

the output is prime, the conditional output distribution is uniform over all

primes.

Let us now consider the expected running time of Algorithm RP. As was

shown in §7.5.1, this is O(kWM ), where WM is the expected running time

of IsPrime where the average is taken with respect to the random choice of

input n ∈ {2, . . . , M } and the random choices of the primality test itself.

Clearly, we have WM = O(tk 3 ), since MR(n, t) executes at most t iterations

of the Miller“Rabin test, and each such test takes time O(k 3 ). This leads to

an expected total running time bound of O(tk 4 ). However, this estimate for

WM is overly pessimistic. Intuitively, this is because when n is composite, we

expect to perform very few Miller“Rabin tests” only when n is prime do we

actually perform all t of them. To make a rigorous argument, consider the

experiment in which n is chosen at random from {2, . . . , M }, and MR(n, t)

is executed. Let Y be the number of times the basic Miller“Rabin test is

actually executed. Conditioned on any ¬xed, odd, prime value of n, the

value of Y is always t. Conditioned on any ¬xed, odd, composite value of

n, the distribution of Y is geometric with an associated success probability

of at least 3/4; thus, the conditional expectation of Y is at most 4/3 in this

254 Probabilistic primality testing

case. Thus, we have

E[Y ] = E[Y | n prime]P[n prime] + E[Y | n composite]P[n composite]

¤ tπ(M )/(M ’ 1) + 4/3.

Thus, E[Y ] ¤ 4/3 + O(t/k), from which it follows that WM = O(k 3 + tk 2 ),

and hence the expected total running time of Algorithm RP is actually

O(k 4 + tk 3 ).

Note that the above estimate (10.2) for γ(M, t) is actually quite pes-

simistic. This is because the error probability 4’t is a worst-case estimate;

in fact, for “most” composite integers n, the probability that MR(n, t) out-

puts true is much smaller than this. In fact, γ(M, 1) is very small for large

M . For example, the following is known:

Theorem 10.7. We have

γ(M, 1) ¤ exp[’(1 + o(1)) log(M ) log(log(log(M )))/ log(log(M ))].

Proof. Literature”see §10.7. 2

The bound in the above theorem goes to zero quite quickly” faster than

(log M )’c for any positive constant c. While the above theorem is asymp-

totically very good, in practice, one needs explicit bounds. For example, the

following lower bounds for ’ log2 (γ(2k , 1)) are known:

k 200 300 400 500 600

3 19 37 55 74

Given an upper bound on γ(M, 1), we can bound γ(M, t) for t ≥ 2 using

the following inequality:

γ(M, 1) ’t+1

γ(M, t) ¤ 4 . (10.3)

1 ’ γ(M, 1)

To prove (10.3), it is not hard to see that on input M , the output distribution

of Algorithm RP is the same as that of the following algorithm:

repeat

repeat

n ←R {2, . . . , M }

until MR(n, 1)

n1 ← n

until MR(n1 , t ’ 1)

output n1

10.4 Generating random primes using the Miller“Rabin test 255

Consider for a moment a single execution of the outer loop of the above

algorithm. Let β be the probability that n1 is composite, and let ± be the

conditional probability that MR(n1 , t ’ 1) outputs true, given that n1 is

composite. Evidently, β = γ(M, 1) and ± ¤ 4’t+1 .

Now, using exactly the same reasoning as was used to derive equation

(7.2) in §7.5.1, we ¬nd that

4’t+1 γ(M, 1)

±β ±β

¤ ¤

γ(M, t) = ,

±β + (1 ’ β) 1’β 1 ’ γ(M, 1)

which proves (10.3).

Given that γ(M, 1) is so small, for large M , Algorithm RP actually

exhibits the following behavior in practice: it generates a random value

n ∈ {2, . . . , M }; if n is odd and composite, then the very ¬rst iteration of

the Miller“Rabin test will detect this with overwhelming probability, and no

more iterations of the test are performed on this n; otherwise, if n is prime,

the algorithm will perform t ’ 1 more iterations of the Miller“Rabin test,

“just to make sure.”

Exercise 10.7. Consider the problem of generating a random Sophie Ger-

main prime between 2 and M (see §5.5.5). One algorithm to do this is as

follows:

repeat

n ←R {2, . . . , M }

if MR(n, t) then