this algorithm is O(k 3 /e).

Trying all candidate values of e from 1 to log2 n yields an overall running

time for perfect power testing of O( e k 3 /e), which is O(k 3 len(k)). To ¬nd

the largest possible value of e for which n is an eth power, we should examine

the candidates from highest to lowest.

Using the above algorithm for perfect power testing and an e¬cient pri-

mality test, we can determine if an integer n is a prime power pe , and if so,

compute p and e: we ¬nd the largest positive integer e (possibly 1) such

that n = de for integer d, and test if d is a prime using an e¬cient primality

test.

10.6 Factoring and computing Euler™s phi function

In this section, we use some of the ideas developed to analyze the Miller“

Rabin test to prove that the problem of factoring n and the problem of

computing φ(n) are equivalent. By equivalent, we mean that given an e¬-

10.6 Factoring and computing Euler™s phi function 263

cient algorithm to solve one problem, we can e¬ciently solve the other, and

vice versa.

Clearly, one direction is easy: if we can factor n into primes, so

n = pe1 · · · per , (10.5)

r

1

then we can simply compute φ(n) using the formula

φ(n) = pe1 ’1 (p1 ’ 1) · · · per ’1 (pr ’ 1).

r

1

For the other direction, ¬rst consider the special case where n = pq, for

distinct primes p and q. Suppose we are given n and φ(n), so that we have

two equations in the unknowns p and q:

n = pq and φ(n) = (p ’ 1)(q ’ 1).

Substituting n/p for q in the second equation, and simplifying, we obtain

p2 + (φ(n) ’ n ’ 1)p + n,

which can be solved using the quadratic formula.

For the general case, it is just as easy to prove a stronger result: given

any non-zero multiple of the exponent of Z— , we can e¬ciently factor n. In

n

particular, this will show that we can e¬ciently factor Carmichael numbers.

Before stating the algorithm in its full generality, we can convey the main

idea by considering the special case where n = pq, where p and q are distinct

primes, with p ≡ q ≡ 3 (mod 4). Suppose we are given such an n, along

with f = 0 that is a common multiple of p ’ 1 and q ’ 1. The algorithm

works as follows: let f = 2h m, where m is odd; choose a random, non-zero

element ± of Zn ; test if either gcd(rep(±), n) or gcd(rep(±m ) + 1, n) splits n

(recall that rep(±) denotes the canonical representative of ±).

The assumption that p ≡ 3 (mod 4) means that (p’1)/2 is an odd integer,

and since f is a multiple of p ’ 1, it follows that gcd(m, p ’ 1) = (p ’ 1)/2,

and hence the image of Z— under the m-power map is the subgroup of Z— of

p p

— under the m-power map

order 2, which is {±1}. Likewise, the image of Zq

is {±1}. Let θ : Zp — Zq ’ Zn be the ring isomorphism from the Chinese

remainder theorem. Now, if ± in the above algorithm does not lie in Z— , n

then certainly gcd(rep(±), n) splits n. Otherwise, condition on the event

that ± ∈ Z— . In this conditional probability distribution, ± is uniformly

n

distributed over Z— , and β := ±m is uniformly distributed over θ(±1, ±1).

n

Let us consider each of these four possibilities:

• β = θ(1, 1) implies β + 1 = θ(2, 2), and so gcd(rep(β) + 1, n) = 1;

• β = θ(’1, ’1) implies β + 1 = θ(0, 0), and so gcd(rep(β) + 1, n) = n;

264 Probabilistic primality testing

• β = θ(’1, 1) implies β + 1 = θ(0, 2), and so gcd(rep(β) + 1, n) = p;

• β = θ(1, ’1) implies β + 1 = θ(2, 0), and so gcd(rep(β) + 1, n) = q.

Thus, if β = θ(’1, 1) or β = θ(1, ’1), which happens with probability 1/2,

then gcd(rep(β) + 1, n) splits n. Therefore, the overall probability that we

split n is at least 1/2.

We now present the algorithm in its full generality. We ¬rst introduce

some notation; namely, let »(n) denote the exponent of Z— . If the prime

n

factorization of n is as in (10.5), then by the Chinese remainder theorem,

we have

»(n) = lcm(»(pe1 ), . . . , »(per )).

r

1

Moreover, for any prime power pe , by Theorem 10.1, we have

pe’1 (p ’ 1) if p = 2 or e ¤ 2,

e

»(p ) =

2e’2 if p = 2 and e ≥ 3.

In particular, if m | n, then »(m) | »(n).

Now, returning to our factorization problem, we are given n and a non-

zero multiple f of »(n), and want to factor n. We may as well assume that

n is odd; otherwise, we can pull out all the factors of 2, obtaining n such

that n = 2e n , where n is odd and f is a multiple of »(n ), thus, reducing

to the odd case.

So now, assume n is odd and f is a multiple of »(n). Assume that f is

of the form f = 2h m, where m is odd. Our factoring algorithm, which we

describe recursively, runs as follows.

if n is a prime power pe then

output e copies of p and return

generate a random, non-zero element ± of Zn

d1 ← gcd(rep(±), n)

if d1 = 1, then recursively factor d1 and n/d1 (using the same f ),

and return

± ← ±m

for j ← 0 to h ’ 1 do

d2 ← gcd(rep(±) + 1, n)

if d2 ∈ {1, n}, then recursively factor d2 and n/d2

/

(using the same f ), and return

± ← ±2

recursively factor n (using the same f )

It is clear that when the algorithm terminates, its output consists of the

10.6 Factoring and computing Euler™s phi function 265

list of all primes (including duplicates) dividing n, assuming the primality

test does not make a mistake.

To analyze the running time of the algorithm, assume that the prime

factorization of n is as in (10.5). By the Chinese remainder theorem, we

have a ring isomorphism

θ : Zpe1 — · · · — Zper ’ Zn .

r

1

Let »(pei ) = mi 2hi , where mi is odd, for i = 1, . . . , r, and let :=

i

max{h1 , . . . , hr }. Note that since »(n) | f , we have ¤ h.

Consider one execution of the body of the recursive algorithm. If n is

a prime power, this will be detected immediately, and the algorithm will

return. Here, even if we are using probabilistic primality test, such as the

Miller“Rabin test, that always says that a prime is a prime, the algorithm

will certainly halt. So assume that n is not a prime power, which means

that r ≥ 2. If the chosen value of ± is not in Z— , then d1 will be a non-

n

trivial divisor of n. Otherwise, conditioning on the event that ± ∈ Z— , the n

— . Consider the value β := ±m2 ’1 .

distribution of ± is uniform over Zn

We claim that with probability at least 1/2, gcd(rep(β) + 1, n) is a non-

trivial divisor of n. To prove this claim, let us write

β = θ(β1 , . . . , βr ),

where βi ∈ Z—ei for i = 1, . . . , r. Note that for those i with hi < , the m2 ’1 -

pi

power map kills the group Z—ei , while for those i with hi = , the image of

pi

Z—ei ’1 -power map is {±1}. Without loss of generality, assume

under the m2

pi

that the indices i such that hi = are numbered 1, . . . , r , where 1 ¤ r ¤ r.

The values βi for i = 1, . . . , r are uniformly and independently distributed

over {±1}, while for all i > r , βi = 1. Thus, the value of gcd(rep(β) + 1, n)

is the product of all prime powers pei , with βi = ’1, which will be non-

i

trivial unless either (1) all the βi are 1, or (2) r = r and all the βi are ’1.