Exercise 16.4 has implications in cryptography. A popular way of im-

plementing a public-key primitive known as a “digital signature” works as

follows: to digitally sign a message M (which may be an arbitrarily long

bit string), ¬rst apply a “hash function” or “message digest” H to M , ob-

taining an integer a in some ¬xed range {1, . . . , x}, and then compute the

signature of M as the eth root b of a modulo n. Anyone can verify that such

a signature b is correct by checking that be ≡ H(M ) (mod n); however, it

would appear to be di¬cult to “forge” a signature without knowing the fac-

torization of n. Indeed, one can prove the security of this signature scheme

by assuming that it is hard to compute the eth root of a random number

modulo n, and by making the heuristic assumption that H is a random

function (see §16.5). However, for this proof to work, the value of x must

be close to n; otherwise, if x is signi¬cantly smaller than n, as the result of

this exercise, one can break the signature scheme at a cost that is roughly

the same as the cost of factoring numbers around the size of x, rather than

the size of n.

16.3 An algorithm for factoring integers

We now present a probabilistic, subexponential-time algorithm for factor-

ing integers. The algorithm uses techniques very similar to those used in

Algorithm SEDL in §16.2.

Let n > 1 be the integer we want to factor. We make a few simplifying

assumptions. First, we assume that n is odd”this is not a real restriction,

since we can always pull out any factors of 2 in a pre-processing step. Second,

we assume that n is not a perfect power, that is, not of the form ab for

integers a > 1 and b > 1 ” this is also not a real restriction, since we can

always partially factor n using the algorithm in §10.5 if n is a perfect power.

Third, we assume that n is not prime ” this may be e¬ciently checked

using, say, the Miller“Rabin test (see §10.3). Fourth, we assume that n is

not divisible by any primes up to a “smoothness parameter” y ” we can

ensure this using trial division, and it will be clear that the running time of

this pre-computation is dominated by that of the algorithm itself.

16.3 An algorithm for factoring integers 345

With these assumptions, the prime factorization of n is of the form

f f

n = q11 · · · qww ,

where the qi are distinct, odd primes, all greater than y, the fi are positive

integers, and w > 1.

The main goal of our factoring algorithm is to ¬nd a random square root

of 1 in Zn . Let

θ : Zqf1 — · · · — Zqfw ’ Zn

w

1

be the ring isomorphism of the Chinese remainder theorem. The square

roots of 1 in Zn are precisely those elements of the form θ(±1, . . . , ±1), and

if β is a random square root of 1, then with probability 1 ’ 2’w+1 ≥ 1/2, it

will be of the form β = θ(β1 , . . . , βw ), where the βi are neither all 1 nor all

’1 (i.e., β = ±1). If this happens, then β ’ 1 = θ(β1 ’ 1, . . . , βw ’ 1), and

so we see that some, but not all, of the values βi ’ 1 will be zero. The value

f

of gcd(rep(β ’ 1), n) is precisely the product of the prime powers qi i such

that βi ’ 1 = 0, and hence this gcd will yield a non-trivial factorization of

n, unless β = ±1.

Let p1 , . . . , pk be the primes up to the smoothness parameter y mentioned

above. Let πi := [pi ]n ∈ Z— for i = 1, . . . , k.

n

We ¬rst describe a simpli¬ed version of the algorithm, after which we

modify the algorithm slightly to deal with a technical problem. Like Algo-

rithm SEDL, this algorithm proceeds in two stages. In the ¬rst stage, we

¬nd relations of the form

e

e

2

±i = π1i1 · · · πkik , (16.6)

for ±i ∈ Z— , and i = 1, . . . , k + 1.

n

We can obtain such a relation by randomized search, as follows: we select

±i ∈ Z— at random, square it, and try to factor mi := rep(±i ) by trial 2

n

division, trying all the primes p1 , . . . , pk up to y. If we are lucky, we obtain

a factorization

mi = pei1 · · · peik ,

1 k

for some exponents ei1 , . . . , eik , yielding the relation (16.6); if not, we just

keep trying.

For i = 1, . . . , k + 1, let vi := (ei1 , . . . , eik ) ∈ Z—k , and let vi denote the

¯

image of vi in Z—k (i.e., vi := ([ei1 ]2 , . . . , [eik ]2 )). Since Z—k is a vector space

¯

2 2

over the ¬eld Z2 of dimension k, the vectors v1 , . . . , vk+1 must be linearly

¯ ¯

dependent. The second stage of the algorithm uses Gaussian elimination

346 Subexponential-time discrete logarithms and factoring

over Z2 to ¬nd a linear dependence among the vectors v1 , . . . , vk+1 , that is,

¯ ¯

to ¬nd integers c1 , . . . , ck+1 ∈ {0, 1}, not all zero, such that

(e1 , . . . , ek ) := c1 v1 + · · · ck+1 vk+1 ∈ 2Z—k .

Raising each equation (16.6) to the power ci , and multiplying them all to-

gether, we obtain

e

e

±2 = π11 · · · πkk ,

where

k+1

c

±i i .

± :=

i=1

Since each ei is even, we can compute

e /2 e /2

· · · πkk ±’1 ,

β := π11

and we see that β is a square root of 1 in Zn . A more careful analysis (see

below) shows that in fact, β is uniformly distributed over all square roots of

1, and hence, with probability at least 1/2, if we compute gcd(rep(β ’ 1), n),

we get a non-trivial factor of n.

That is the basic idea of the algorithm. There is, however, a technical

problem. Namely, in the method outlined above for generating a relation,

2

we attempt to factor mi := rep(±i ). Thus, the running time of the algorithm

will depend in a crucial way on the probability that a random square modulo

n is y-smooth. Unfortunately for us, Theorem 16.1 does not say anything

about this situation ” it only applies to the situation where a number is

chosen at random from an interval [1, x]. There are (at least) three di¬erent

ways to address this problem:

1. Ignore it, and just assume that the bounds in Theorem 16.1 apply to

random squares modulo n (taking x := n in the theorem).

2. Prove a version of Theorem 16.1 that applies to random squares mod-

ulo n.

3. Modify the factoring algorithm, so that Theorem 16.1 applies.

The ¬rst choice, while not completely unreasonable, is not very satisfying

mathematically. It turns out that the second choice is a indeed a viable

option (i.e., the theorem is true and is not so di¬cult to prove), but we opt

for the third choice, as it is somewhat easier to carry out, and illustrates a

probabilistic technique that is more generally useful.

16.3 An algorithm for factoring integers 347

So here is how we modify the basic algorithm. Instead of generating

relations of the form (16.6), we generate relations of the form

e

e

2

±i δ = π1i1 · · · πkik , (16.7)

for δ ∈ Z— , ±i ∈ Z— , and i = 1, . . . , k + 2. Note that the value δ is the same

n n

in all relations.

We generate these relations as follows. For the very ¬rst relation (i.e.,

i = 1), we repeatedly choose ±1 and δ in Z— at random, until rep(±1 δ) is 2

n

y-smooth. Then, after having found the ¬rst relation, we ¬nd subsequent

relations (i.e., for i > 1) by repeatedly choosing ±i in Z— at random until

n