inclusion/exclusion (see Exercise 6.3), we have

µ(d)(x/d) ’

R(x, y) = µ(d) x/d = µ(d){x/d}.

d|P d|P d|P

Moreover,

(1 ’ 1/p),

µ(d)(x/d) = x µ(d)/d = x

p¤y

d|P d|P

and

1 = 2π(y) .

µ(d){x/d} ¤

d|P d|P

That proves the theorem. 2

This theorem only says something non-trivial when y is quite small. Nev-

ertheless, using Chebyshev™s theorem on the density of primes, along with

Mertens™ theorem, it is not hard to see that this theorem implies that

„ (M, s) = O(1/ log s) when s = O(log M log log M ), which implies the esti-

mate (10.4) above. We leave the details as an exercise for the reader.

Exercise 10.10. Prove the claim made above that „ (M, s) = O(1/ log s)

when s = O(log M log log M ). More precisely, show that there exist con-

stants c, d, and s0 , such that for all M and d satisfying s0 ¤ s ¤

c log M log log M , we have „ (M, s) ¤ d/ log s. From this, derive the esti-

mate (10.4) above.

Exercise 10.11. Let f be a polynomial with integer coe¬cients. For real

x ≥ 0 and y ≥ 0, de¬ne Rf (x, y) to be the number of integers m up to x

such that f (m) is y-rough. For positive integer M , de¬ne ωf (M ) to be the

number of integers m ∈ {0, . . . , M ’ 1} such that f (m) ≡ 0 (mod M ). Show

that

Rf (x, y) ’ x (1 ’ ωf (p)/p) ¤ (1 + ωf (p)).

p¤y p¤y

Exercise 10.12. Consider again the problem of generating a random Sophie

Germain prime, as discussed in Exercises 10.7 and 10.8. A useful idea is to

260 Probabilistic primality testing

¬rst test if either n or 2n + 1 are divisible by any small primes up to some

bound s, before performing any more expensive tests. Using this idea, design

and analyze an algorithm that improves the running time of the algorithm

in Exercise 10.8 to O(k 5 / len(k)2 + tk 3 )”under the same assumptions, and

achieving the same error probability bound as in that exercise. Hint: ¬rst

show that the previous exercise implies that the number of positive integers

m up to x such that both m and 2m + 1 are y-rough is at most

1

(1 ’ 2/p) + 3π(y) .

x·

2

2<p¤y

Exercise 10.13. Design an algorithm that takes as input a prime q and

a bound M , and outputs a random prime p between 2 and M such that

p ≡ 1 (mod q). Clearly, we need to assume that M is su¬ciently large

with respect to q. Analyze your algorithm assuming Conjecture 5.24 (and

using the result of Exercise 5.22). State how large M must be with respect

to q, and under these assumptions, show that your algorithm runs in time

O(k 4 / len(k)+tk 3 ), and that its output is incorrect with probability O(4’t k).

As usual, k := len(M ).

10.4.3 Generating a random k-bit prime

In some applications, we want to generate a random prime of ¬xed size ”

a random 1024-bit prime, for example. More generally, let us consider the

following problem: given integer k ≥ 2, generate a random k-bit prime, that

is, a prime in the interval [2k’1 , 2k ).

Bertrand™s postulate (Theorem 5.7) implies that there exists a constant

c > 0 such that π(2k ) ’ π(2k’1 ) ≥ c2k’1 /k for all k ≥ 2.

Now let us modify Algorithm RP so that it takes as input integer k ≥ 2,

and repeatedly generates a random n in the interval {2k’1 , . . . , 2k ’ 1} until

IsPrime(n) returns true. Let us call this variant Algorithm RP . Further,

let us implement IsPrime(·) as MR(·, t), for some auxiliary parameter t, and

de¬ne γ (k, t) to be the probability that the output of Algorithm RP ” with

this implementation of IsPrime ”is composite.

Then using exactly the same reasoning as above,

2k’1

’t

= O(4’t k).

γ (k, t) ¤ 4 k ) ’ π(2k’1 )

π(2

As before, if the output of Algorithm RP is prime, then every k-bit prime

is equally likely, and the expected running time is O(k 4 + tk 3 ). By doing

some trial division as above, this can be reduced to O(k 4 / len(k) + tk 3 ).

10.5 Perfect power testing and prime power factoring 261

The function γ (k, t) has been studied a good deal; for example, the fol-

lowing is known:

Theorem 10.9. For all k ≥ 2, we have

√

γ (k, 1) ¤ k 2 42’ k

.

Proof. Literature”see §10.7. 2

Upper bounds for γ (k, t) for speci¬c values of k and t have been computed.

The following table lists some known lower bounds for ’ log2 (γ (k, t)) for

various values of k and t:

t\k 200 300 400 500 600

1 11 19 37 56 75

2 25 33 46 63 82

3 34 44 55 70 88

4 41 53 63 78 95

5 47 60 72 85 102

Using exactly the same reasoning as the derivation of (10.3), one sees that

γ (k, 1) ’t+1

γ (k, t) ¤ 4 .

1 ’ γ (k, 1)

10.5 Perfect power testing and prime power factoring

Consider the following problem: we are given a integer n > 1, and want to

determine if n is a perfect power, which means that n = de for integers d

and e, both greater than 1. Certainly, if such d and e exist, then it must be

the case that 2e ¤ n, so we can try all possible candidate values of e, running

from 2 to log2 n . For each such candidate value of e, we can test if n = de

for some d as follows. Suppose n is a k-bit number, that is, 2k’1 ¤ n < 2k .

Then 2(k’1)/e ¤ n1/e < 2k/e . So any integer eth root of n must lie in the

set {u, . . . , v ’ 1}, where u := 2 (k’1)/e and v := 2 k/e . Using u and v as

starting values, we can perform a binary search:

262 Probabilistic primality testing

repeat

w ← (u + v)/2

z ← we

if z = n then

declare than n = we is an a perfect eth power, and stop

else if z < n then

u←w+1

else

v←w

until u ≥ v

declare that n is not a perfect eth power

If n = de for some integer d, then the following invariant holds (verify):

at the beginning of each loop iteration, we have u ¤ d < v. Thus, if n is

a perfect eth power, this will be discovered. That proves the correctness of

the algorithm.

As to its running time, note that with each loop iteration, the length v ’u

of the search interval decreases by a factor of at least 2 (verify). Therefore,

after t iterations the interval will be of length at most 2k/e+1 /2t , so after

at most k/e + 2 iterations, the interval will be of length less than 1, and

hence of length zero, and the algorithm will halt. So the number of loop

iterations is O(k/e). The power we computed in each iteration is no more

than 2(k/e+1)e = 2k+e ¤ 22k , and hence can be computed in time O(k 2 ) (see