occurs with probability 2’r ¤ 1/2. Second, if r = r, then each of events

(1) and (2) occurs with probability 2’r , and so the probability that either

occurs is 2’r+1 ¤ 1/2. That proves the claim.

From the claim, it follows that with probability at least 1/2, we will obtain

a non-trivial divisor d2 of n when j = ’ 1 (if not before).

So we have shown that with probability at least 1/2, one execution of the

body will succeed in splitting n into non-trivial factors. After at most log2 n

such successes, we will have completely factored n. Therefore, the expected

number of recursive invocations of the algorithm is O(len(n)).

266 Probabilistic primality testing

Exercise 10.14. Suppose you are given an integer n of the form n = pq,

where p and q are distinct, -bit primes, with p = 2p + 1 and q = 2q + 1,

where p and q are themselves prime. Suppose that you are also given an

integer m such that gcd(m, p q ) = 1. Show how to e¬ciently factor n.

Exercise 10.15. Suppose there is a probabilistic algorithm A that takes

as input an integer n of the form n = pq, where p and q are distinct, -bit

primes, with p = 2p + 1 and q = 2q + 1, where p and q are prime. The

algorithm also takes as input ±, β ∈ (Z— )2 . It outputs either “failure,” or

n

x β y = 1. Furthermore, assume that

integers x, y, not both zero, such that ±

A runs in strict polynomial time, and that for all n of the above form, and

for randomly chosen ±, β ∈ (Z— )2 , A succeeds in ¬nding x, y as above with

n

probability (n). Here, the probability is taken over the random choice of ±

and β, as well as the random choices made during the execution of A. Show

how to use A to construct another probabilistic algorithm A that takes as

input n as above, runs in expected polynomial time, and that satis¬es the

following property:

if (n) ≥ 0.001, then A factors n with probability at least

0.999.

10.7 Notes

The Miller“Rabin test is due to Miller [63] and Rabin [75]. The paper by

Miller de¬ned the set Ln , but did not give a probabilistic analysis. Rather,

Miller showed that under a generalization of the Riemann hypothesis, for

composite n, the least positive integer a such that [a]n ∈ Zn \ Ln is at

most O((log n)2 ), thus giving rise to a deterministic primality test whose

correctness depends on the above unproved hypothesis. The later paper by

Rabin re-interprets Miller™s result in the context of probabilistic algorithms.

Bach [10] gives an explicit version of Miller™s result, showing that under

the same assumptions, the least positive integer a such that [a]n ∈ Zn \ Ln

is at most 2(log n)2 ; more generally, Bach shows the following holds under

a generalization of the Riemann hypothesis:

For any positive integer n, and any proper subgroup G Z— , n

the least positive integer a such that [a]n ∈ Zn \ G is at most

2(log n)2 , and the least positive integer b such that [b]n ∈ Z— \G

n

2.

is at most 3(log n)

The ¬rst e¬cient probabilistic primality test was invented by Solovay and

Strassen [94] (their paper was actually submitted for publication in 1974).

10.7 Notes 267

Later, in Chapter 22, we shall discuss a recently discovered, deterministic,

polynomial-time (though not very practical) primality test, whose analysis

does not rely on any unproved hypothesis.

Carmichael numbers are named after R. D. Carmichael, who was the

¬rst to discuss them, in work published in the early 20th century. Al-

ford, Granville, and Pomerance [7] proved that there are in¬nitely many

Carmichael numbers.

Exercise 10.6 is based on Lehmann [55].

Theorem 10.7, as well as the table of values just below it, are from Kim

and Pomerance [53]. In fact, these bounds hold for the weaker test based

on Ln .

Our analysis in §10.4.2 is loosely based on a similar analysis in §4.1 of

Maurer [61]. Theorem 10.8 and its generalization in Exercise 10.11 are

certainly not the best results possible in this area. The general goal of

“sieve theory” is to prove useful upper and lower bounds for quantities like

Rf (x, y) that hold when y is as large as possible with respect to x. For

example, using a technique known as Brun™s pure sieve, one can show that

√

for log y < log x, there exist β and β , both of absolute value at most 1,

such that

√

√

’ log x

(1 ’ ωf (p)/p) + β x.

Rf (x, y) = (1 + βe )x

p¤y

Thus, this gives us very sharp estimates for Rf (x, y) when x tends to in¬nity,

and y is bounded by any ¬xed polynomial in log x. For a proof of this

result, see §2.2 of Halberstam and Richert [42] (the result itself is stated

as equation 2.16). Brun™s pure sieve is really just the ¬rst non-trivial sieve

result, developed in the early 20th century; even stronger results, extending

the useful range of y (but with larger error terms), have subsequently been

proved.

Theorem 10.9, as well as the table of values immediately below it, are

from Damg˚ Landrock, and Pomerance [32].

ard,

The algorithm presented in §10.6 for factoring an integer given a multiple

of φ(n) (or, for that matter, »(n)) is essentially due to Miller [63]. However,

just as for his primality test, Miller presents his algorithm as a deterministic

algorithm, which he analyzes under a generalization of the Riemann hypoth-

esis. The probabilistic version of Miller™s factoring algorithm appears to be

“folklore.”

11

Finding generators and discrete logarithms in Z—

p

As we have seen in Theorem 9.16, for a prime p, Z— is a cyclic group of order

p

p ’ 1. This means that there exists a generator γ ∈ Z— , such that for all

p

— , ± can be written uniquely as ± = γ x , where x is an integer with

± ∈ Zp

0 ¤ x < p ’ 1; the integer x is called the discrete logarithm of ± to the

base γ, and is denoted logγ ±.

This chapter discusses some computational problems in this setting;

namely, how to e¬ciently ¬nd a generator γ, and given γ and ±, how to

compute logγ ±.

More generally, if γ generates a subgroup G of Z— of order q, where q |

p

(p ’ 1), and ± ∈ G, then logγ ± is de¬ned to be the unique integer x with

0 ¤ x < q and ± = γ x . In some situations it is more convenient to view

logγ ± as an element of Zq . Also for x ∈ Zq , with x = [a]q , one may write γ x

to denote γ a . There can be no confusion, since if x = [a ]q , then γ a = γ a .

However, in this chapter, we shall view logγ ± as an integer.

Although we work in the group Z— , all of the algorithms discussed in this

p

chapter trivially generalize to any ¬nite cyclic group that has a suitably

compact representation of group elements and an e¬cient algorithm for

performing the group operation on these representations.

11.1 Finding a generator for Z—

p

There is no e¬cient algorithm known for this problem, unless the prime

factorization of p ’ 1 is given, and even then, we must resort to the use of

a probabilistic algorithm. Of course, factoring in general is believed to be a

very di¬cult problem, so it may not be easy to get the prime factorization

of p ’ 1. However, if our goal is to construct a large prime p, together with

a generator for Z— , then we may use Algorithm RFN in §7.7 to generate a

p

random factored number n in some range, test n + 1 for primality, and then

268

11.1 Finding a generator for Z— 269

p

repeat until we get a factored number n such that p = n + 1 is prime. In

this way, we can generate a random prime p in a given range along with the