stage 1 of σ ’1 k 2 · len(n)O(1) . Stage 2 is dominated by the cost of Gaussian

elimination, which takes time k 3 · len(n)O(1) . Thus, if T is the total running

time of the algorithm, we have

E[T ] ¤ (σ ’1 k 2 + k 3 ) · len(n)O(1) .

By our assumption that n is not divisible by any primes up to y, all y-

smooth integers up to n ’ 1 are in fact relatively prime to n. Therefore, the

number of y-smooth elements of Z— is equal to Ψ(y, n ’ 1), and since n itself

n

is not y-smooth, this is equal to Ψ(y, n). From this, it follows that

σ = Ψ(y, n)/|Z— | ≥ Ψ(y, n)/n.

n

The rest of the running time analysis is essentially the same as in the anal-

ysis of Algorithm SEDL; that is, assuming y = exp[(log n)»+o(1) ] for some

constant 0 < » < 1, we obtain

E[T ] ¤ exp[(1 + o(1)) max{(log n/ log y) log log n + 2 log y, 3 log y}]. (16.8)

√

Setting y = exp[(1/ 2)(log n log log n)1/2 ], we obtain

√

E[T ] ¤ exp[(2 2 + o(1))(log n log log n)1/2 ].

That basically takes care of the ¬rst two questions. As for the third, we

have:

Lemma 16.5. The probability that the algorithm outputs “failure” is

2’w+1 ¤ 1/2.

Proof. Let ρ be the squaring map on Z— . By part (b) of Exercise 8.22, if

n

2 2

we condition on any ¬xed values of δ, ±1 , . . . , ±k+2 , as determined at the

end of stage 1 of the algorithm, then in the resulting conditional probability

distribution, the values ±1 , . . . , ±k+2 are mutually independent, with each

±i uniformly distributed over ρ’1 ({±i }). Moreover, these ¬xed values of

2

2 2

δ, ±1 , . . . , ±k+2 completely determine the behavior of the algorithm, and in

particular, the values of c1 , . . . , ck+2 , ±2 , and e1 , . . . , ek+1 . By part (d) of

Exercise 8.22, it follows that ± is uniformly distributed over ρ’1 ({±2 }), and

also that β is uniformly distributed over ρ’1 ({1}). Thus, in this conditional

probability distribution, β is a random square root of 1, and so β = ±1 with

probability 2’w+1 . Since this holds conditioned on all relevant choices of

2 2

δ, ±1 , . . . , ±k+2 , it also holds unconditionally. Finally, since we are assuming

that w > 1, we have 2’w+1 ¤ 1/2. 2

Let us summarize the above discussion in the following theorem.

16.3 An algorithm for factoring integers 351

Theorem 16.6. With the smoothness parameter set as

√

y := exp[(1/ 2)(log n log log n)1/2 ],

the expected running time of Algorithm SEF is

√

exp[(2 2 + o(1))(log n log log n)1/2 ].

The probability that Algorithm SEF outputs “failure” is at most 1/2.

Exercise 16.5. It is perhaps a bit depressing that after all that work, Al-

gorithm SEF only succeeds (in the worst case) with probability 1/2. Of

course, to reduce the failure probability, we can simply repeat the entire

computation ”with repetitions, the failure probability drops to 2’ . How-

ever, there is a better way to reduce the failure probability. Suppose that in

stage 1, instead of collecting k + 2 relations, we collect k + 1 + relations,

where ≥ 1 is an integer parameter.

(a) Show that in stage 2, we can use Gaussian elimination over Z2 to ¬nd

integer vectors

(j) (j)

c(j) = (c1 , . . . , ck+1+ ) ∈ {0, 1}—(k+1+ )

(j = 1, . . . , )

such that

“ over the ¬eld Z2 , the images of the vectors c(1) , . . . , c( ) in

—(k+1+ )

are linearly independent, and

Z2

“ for j = 1, . . . , , we have

(j) (j)

c1 v1 + · · · + ck+1+ vk+1+ ∈ 2Z—(k+2) .

(b) Show that given vectors c(1) , . . . , c( ) as in part (a), if for j = 1, . . . , ,

we set

(j) (j) (j) (j)

(e1 , . . . , ek+1 ) ← c1 v1 + · · · + ck+1+ vk+1+ ,

k+1+ (j)

c

(j)

← ±i i ,

±

i=1

and

(j)

(j)

ek /2 ’e(j) /2 (j) ’1

e1 /2

(j)

← · · · πk

β π1 δ k+1 (± ) ,

then the values β (1) , . . . , β ( ) are independent and uniformly dis-

tributed over the set of all square roots of 1 in Zn , and hence at

least one of gcd(rep(β (j) ’ 1), n) splits n with probability at least

1 ’ 2’ .

352 Subexponential-time discrete logarithms and factoring

So, for example, if we set = 20, then the failure probability is reduced to

less than one in a million, while the increase in running time over Algorithm

SEF will hardly be noticeable.

16.4 Practical improvements

Our presentation and analysis of algorithms for discrete logarithms and fac-

toring were geared towards simplicity and mathematical rigor. However, if

one really wants to compute discrete logarithms or factor numbers, then a

number of important practical improvements should be considered. In this

section, we brie¬‚y sketch some of these improvements, focusing our atten-

tion on algorithms for factoring numbers (although some of the techniques

apply to discrete logarithms as well).

16.4.1 Better smoothness density estimates

From an algorithmic point of view, the simplest way to improve the running

times of both Algorithms SEDL and SEF is to use a more accurate smooth-

ness density estimate, which dictates a di¬erent choice of the smoothness

bound y in those algorithms, speeding them up signi¬cantly. While our

Theorem 16.1 is a valid lower bound on the density of smooth numbers, it

is not “tight,” in the sense that the actual density of smooth numbers is

somewhat higher. We quote from the literature the following result:

Theorem 16.7. Let y be a function of x such that for some > 0, we have

log x

y = „¦((log x)1+ ) and u := ’∞

log y

as x ’ ∞. Then

Ψ(y, x) = x · exp[(’1 + o(1))u log u].

Proof. See §16.5. 2

Let us apply this result to the analysis of Algorithm SEF. Assume that

y = exp[(log n)1/2+o(1) ] ” our choice of y will in fact be of this form. With

this assumption, we have log log y = (1/2 + o(1)) log log n, and using Theo-

rem 16.7, we can improve the inequality (16.8), obtaining instead (verify)

E[T ] ¤ exp[(1 + o(1)) max{(1/2)(log n/ log y) log log n + 2 log y, 3 log y}].

From this, if we set

y := exp[(1/2)(log n log log n)1/2 )],

16.4 Practical improvements 353

we obtain

E[T ] ¤ exp[(2 + o(1))(log n log log n)1/2 ].

An analogous improvement can be obtained for Algorithm SEDL.

√

Although this improvement reduces the constant 2 2 ≈ 2.828 to 2, the