output n and halt

forever

Assuming Conjecture 5.26, show that this algorithm runs in expected time

O(k 5 + tk 4 ), and outputs a number that is not a Sophie Germain prime with

probability O(4’t k 2 ). As usual, k := len(M ).

Exercise 10.8. Improve the algorithm in the previous exercise, so that un-

der the same assumptions, it runs in expected time O(k 5 +tk 3 ), and outputs

a number that is not a Sophie Germain prime with probability O(4’t k 2 ),

or even better, show that this probability is at most γ(M, t)π — (M )/π(M ) =

O(γ(M, t)k), where π — (M ) is de¬ned as in §5.5.5.

Exercise 10.9. Suppose in Algorithm RFN in §7.7 we implement algorithm

IsPrime(·) as MR(·, t), where t is a parameter satisfying 4’t (2 + log M ) ¤

256 Probabilistic primality testing

1/2, if M is the input to RFN. Show that the expected running time of

Algorithm RFN in this case is O(k 5 + tk 4 len(k)). Hint: use Exercise 7.20.

10.4.2 Trial division up to a small bound

In generating a random prime, most candidates n will in fact be composite,

and so it makes sense to cast these out as quickly as possible. Signi¬cant

e¬ciency gains can be achieved by testing if a given candidate n is divisible

by any small primes up to a given bound s, before we subject n to a Miller“

Rabin test. This strategy makes sense, since for a small, “single precision”

prime p, we can test if p | n essentially in time O(len(n)), while a single

iteration of the Miller“Rabin test takes time O(len(n)3 ) steps.

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

which takes as input integers n, t, and s, with n > 1, t ≥ 1, and s > 1:

Algorithm MRS (n, t, s):

for each prime p ¤ s do

if p | n then

if p = n then return true else return false

repeat t times

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

if ± ∈ Ln return false

return true

In an implementation of the above algorithm, one would most likely use

the sieve of Eratosthenes (see §5.4) to generate the small primes.

Note that MRS (n, t, 2) is equivalent to MR(n, t). Also, it is clear that the

probability that MRS (n, t, s) makes a mistake is no more than the prob-

ability that MR(n, t) makes a mistake. Therefore, using MRS in place of

MR will not increase the probability that the output of Algorithm RP is a

composite ”indeed, it is likely that this probability decreases signi¬cantly.

Let us now analyze the impact on the running time. To do this, we need

to estimate the probability „ (M, s) that a randomly chosen number between

2 and M is not divisible by any primes up to s. If M is su¬ciently large

with respect to s, the following heuristic argument can be made rigorous,

as we will discuss below. The probability that a random number is divisible

by a prime p is about 1/p, so the probability that it is not divisible by p is

about 1 ’ 1/p. Assuming that these events are essentially independent for

10.4 Generating random primes using the Miller“Rabin test 257

di¬erent values of p (this is the heuristic part), we estimate

„ (M, s) ≈ (1 ’ 1/p) ∼ B1 / log s,

p¤s

where B1 ≈ 0.56146 is the constant from Exercise 5.14 (see also Theo-

rem 5.21).

Of course, performing the trial division takes some time, so let us also

estimate the expected number κ(M, s) of trial divisions performed. If

p1 , p2 , . . . , pr are the primes up to s, then for i = 1, . . . , r, the probabil-

ity that we perform at least i trial divisions is precisely „ (M, pi ’ 1). From

this, it follows (see Theorem 6.8) that

„ (M, p ’ 1) ≈

κ(M, s) = B1 / log p.

p¤s p¤s

Using Exercise 5.9 and the Prime number theorem, we obtain

B1 / log p ∼ B1 π(s)/ log s ∼ B1 s/(log s)2 .

κ(M, s) ≈

p¤s

If k = len(M ), for a random n ∈ {2, . . . , M }, the expected amount of

time spent within MRS (n, t, s) performing the Miller“Rabin test is now

easily seen to be O(k 3 / len(s) + tk 2 ). Further, assuming that each individual

trial division step takes time O(len(n)), the expected running time of trial

division up to s is O(ks/ len(s)2 ). This estimate does not take into account

the time to generate the small primes using the sieve of Eratosthenes. These

values might be pre-computed, in which case this time is zero, but even if we

compute them on the ¬‚y, this takes time O(s len(len(s))), which is dominated

by O(ks/ len(s)2 )) for any reasonable value of s (in particular, for s ¤ k O(1) ).

So provided s = o(k 2 len(k)), the running time of MRS will be dominated

by the Miller“Rabin test, which is what we want, of course ” if we spend

as much time on trial division as the time it would take to perform a single

Miller“Rabin test, we might as well just perform the Miller“Rabin test. In

practice, one should use a very conservative bound for s, probably no more

than k 2 , since getting s arbitrarily close to optimal does not really provide

that much bene¬t, while if we choose s too large, it can actually do signi¬cant

harm.

From the above estimates, we can conclude that with k ¤ s ¤ k 2 , the

expected running time WM of MRS (n, t, s), with respect to a randomly

chosen n between 2 and M , is

WM = O(k 3 / len(k) + tk 2 ). (10.4)

258 Probabilistic primality testing

From this, it follows that the expected running time of Algorithm RP on

input M is O(k 4 / len(k) + tk 3 ). Thus, we e¬ectively reduce the running

time by a factor proportional to len(k), which is a very real and noticeable

improvement in practice.

The reader may have noticed that in our analysis of MRS , we as-

sumed that computing n mod p for a “small” prime p takes time

O(len(n)). However, if we strictly followed the rules established in

Theorem 3.3, we should charge time O(len(n) len(p)) for this divi-

sion step. To answer this charge that we have somehow “cheated,”

we o¬er the following remarks.

First, in practice the primes p are so small that they surely will

¬t into a single digit in the underlying representation of integers as

vectors of digits, and so estimating the cost as O(len(n)) rather than

O(len(n) len(p)) seems more realistic.

Second, even if one uses the bound O(len(n) len(p)), one can carry

out a similar analysis, obtaining the same result (namely, a speedup

by a factor proportional to len(k)) except that one should choose s

from a slightly smaller range (namely, s = o(k 2 )).

As we already mentioned, the above analysis is heuristic, but the results

are correct. We shall now discuss how this analysis can be made rigorous;

however, we should remark that any such rigorous analysis is mainly of the-

oretical interest only ” in any practical implementation, the optimal choice

of the parameter s is best determined by experiment, with the analysis being

used only as a rough guide. Now, to make the analysis rigorous, we need

prove that the estimate „ (M, s) ≈ p¤s (1 ’ 1/p) is su¬ciently accurate.

Proving such estimates takes us into the realm of “sieve theory.” The larger

M is with respect to s, the easier it is to prove such estimates. We shall

prove only the simplest and most naive such estimate, but it is still good

enough for our purposes, if we do not care too much about hidden big-O

constants.

Before stating any results, let us restate the problem slightly. For real

y ≥ 0, let us call a positive integer “y-rough” if it is not divisible by any

prime p up to y. For real x ≥ 0, let us de¬ne R(x, y) to be the number

of y-rough integers up to x. Thus, since „ (M, s) is the probability that a

random integer between 2 and M is s-rough, and 1 is by de¬nition s-rough,

we have „ (M, s) = (R(M, s) ’ 1)/(M ’ 1).

Theorem 10.8. For any real x ≥ 0 and y ≥ 0, we have

(1 ’ 1/p) ¤ 2π(y) .

R(x, y) ’ x

p¤y

Proof. To simplify the notation, we shall use the M¨bius function µ (see

o

10.4 Generating random primes using the Miller“Rabin test 259

§2.6). Also, for a real number u, let us write u = u + {u}, where 0 ¤

{u} < 1. Let P be the product of the primes up to the bound y.

Now, there are x positive integers up to x, and of these, for each prime

p dividing P , precisely x/p are divisible by p, for each pair p, p of distinct