In the above analysis, we assumed that IsPrime was a deterministic,

polynomial-time algorithm. While such an algorithm exists, there are in

fact simpler and more e¬cient algorithms that are probabilistic. We shall

discuss such an algorithm in greater depth later, in Chapter 10. This al-

gorithm (like several other algorithms for primality testing) has one-sided

error in the following sense: if the input n is prime, then the algorithm

always outputs true; otherwise, if n is composite, the output may be true

or false, but the probability that the output is true is at most c, where

c < 1 is a constant. In the terminology of §7.2, such an algorithm is essen-

tially a Monte Carlo algorithm for the language of composite numbers. If

we want to reduce the error probability for composite inputs to some very

small value , we can iterate the algorithm t times, with t chosen so that

ct ¤ , outputting true if all iterations output true, and outputting false

otherwise. This yields an algorithm for primality testing that makes errors

only on composite inputs, and then only with probability at most .

Let us analyze the behavior of Algorithm RP under the assumption that

IsPrime is implemented by a probabilistic algorithm (such as described

in the previous paragraph) with an error probability for composite inputs

bounded by . Let us de¬ne Wn to be the expected running time of IsPrime

on input n, and as before, we de¬ne

M

1

WM := Wn .

M ’1

n=2

Thus, WM is the expected running time of algorithm IsPrime, where the

average is taken with respect to randomly chosen n and the random choices

of the algorithm itself.

Consider a single loop iteration of Algorithm RP. For any ¬xed prime p

between 2 and M , the probability that n takes the value p is 1/(M ’ 1).

Thus, if the algorithm halts with a prime, every prime is equally likely. Now,

the algorithm will halt if n is prime, or if n is composite and the primality

test makes a mistake; therefore, the the probability that it halts at all is at

least π(M )/(M ’ 1). So we see that the expected number of loop iterations

7.5 Generating a random prime 165

should be no more than in the case where we use a deterministic primality

test. Using the same argument as was used before to estimate the expected

total running time of Algorithm RP, we ¬nd that this is O(kWM ).

As for the probability that Algorithm RP mistakenly outputs a composite,

one might be tempted to say that this probability is at most , the probability

that IsPrime makes a mistake. However, in drawing such a conclusion, we

would be committing the fallacy of Example 6.12”to correctly analyze the

probability that Algorithm RP mistakenly outputs a composite, one must

take into account the rate of incidence of the “primality disease,” as well as

the error rate of the test for this disease.

Let us be a bit more precise. Again, consider the probability distribution

de¬ned by a single loop iteration, and let A be the event that IsPrime

outputs true, and B the event that n is composite. Let β := P[B] and

± := P[A | B]. First, observe that, by de¬nition, ± ¤ . Now, the probability

δ that the algorithm halts and outputs a composite in this loop iteration is

δ = P[A § B] = ±β.

The probability δ that the algorithm halts and outputs either a prime or

composite is

δ = P[A] = P[A § B] + P[A § B] = P[A § B] + P[B] = ±β + (1 ’ β).

Now consider the behavior of Algorithm RP as a whole. With T being

the number of loop iterations as before, we have

1 1

E[T ] = = , (7.1)

±β + (1 ’ β)

δ

and hence

M ’1

1

E[T ] ¤ = = O(k).

(1 ’ β) π(M )

Let us now consider the probability γ that the output of Algorithm RP

is composite. For i ≥ 1, let Ci be the event that the algorithm halts and

outputs a composite number in the ith loop iteration. The events Ci are

pairwise disjoint, and moreover,

P[Ci ] = P[Ci § T ≥ i] = P[Ci | T ≥ i]P[T ≥ i] = δP[T ≥ i].

So we have

±β

δP[T ≥ i] = δE[T ] =

γ= P[Ci ] = , (7.2)

±β + (1 ’ β)

i≥1 i≥1

166 Probabilistic algorithms

and hence

M ’1

±

γ¤ ¤ = = O(k ).

(1 ’ β) (1 ’ β) π(M )

Another way of analyzing the output distribution of Algorithm RP is to

consider its statistical distance ∆ from the uniform distribution on the set of

primes between 2 and M . As we have already argued, every prime between

2 and M is equally likely to be output, and in particular, any ¬xed prime p

is output with probability at most 1/π(M ). It follows from Theorem 6.15

that ∆ = γ.

7.5.2 Generating a random k-bit prime

Instead of generating a random prime between 2 and M , we may instead

want to generate a random k-bit prime, that is, a prime between 2k’1 and

2k ’ 1. Bertrand™s postulate (Theorem 5.7) tells us that there exist such

primes for every k ≥ 2, and that in fact, there are „¦(2k /k) such primes.

Because of this, we can modify Algorithm RP, so that each candidate n

is chosen at random from the interval {2k’1 , . . . , 2k ’ 1}, and all of the

results of this section carry over essentially without change. In particular,

the expected number of trials until the algorithm halts is O(k), and if a

probabilistic primality test as in §7.5.1 is used, with an error probability of

, the probability that the output is not prime is O(k ).

Exercise 7.14. Design and analyze an e¬cient probabilistic algorithm that

takes as input an integer M ≥ 2, and outputs a random element of Z— .

M

Exercise 7.15. Suppose Algorithm RP is implemented using an imper-

fect random number generator, so that the statistical distance between the

output distribution of the random number generator and the uniform dis-

tribution on {2, . . . , M } is equal to δ (e.g., Algorithm RN in §7.4). Assume

that 2δ < π(M )/(M ’ 1). Also, let » denote the expected number of itera-

tions of the main loop of Algorithm RP, let ∆ denote the statistical distance

between its output distribution and the uniform distribution on the primes

up to M , and let k := len(M ).

(a) Assuming the primality test is deterministic, show that » = O(k) and

∆ = O(δk).

(b) Assuming the primality test is probabilistic, with one-sided error ,

as in §7.5.1, show that » = O(k) and ∆ = O((δ + )k).

7.6 Generating a random non-increasing sequence 167

Exercise 7.16. Analyze Algorithm RP assuming that the primality test

is implemented by an “Atlantic City” algorithm with error probability at

most .

Exercise 7.17. Consider the following probabilistic algorithm that takes as

input a positive integer M :

S←…

repeat

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

S ← S ∪ {n}

until |S| = M

Show that the expected number of iterations of the main loop is ∼ M log M .

The following exercises assume the reader has studied §7.1.1.

Exercise 7.18. Consider the following algorithm (which takes no input):

j←1

repeat

j ←j+1

n ←R {0, . . . , j ’ 1}

until n = 0

Show that this algorithm halts with probability 1, but that its expected

running time does not exist. (Compare this algorithm with the one in Ex-

ample 7.2, which does not even halt with probability 1.)

Exercise 7.19. Now consider the following modi¬cation to the algorithm

in the previous exercise:

j←2

repeat