rep(±i

relation. Now, Theorem 16.1 will apply directly to determine the success

probability of each attempt to generate the ¬rst relation. Having found

2

this relation, the value ±1 δ will be uniformly distributed over all y-smooth

elements of Z— (i.e., elements whose integer representations are y-smooth).

n

Consider the various cosets of (Z— )2 in Z— . Intuitively, it is much more

n n

likely that a random y-smooth element of Z— lies in a coset that contains

n

many y-smooth elements, rather than a coset with very few, and indeed,

it is reasonably likely that the fraction of y-smooth elements in the coset

containing δ is not much less than the overall fraction of y-smooth elements

in Z— . Therefore, for i > 1, each attempt to ¬nd a relation should succeed

n

with reasonably high probability. This intuitive argument will be made

rigorous in the analysis to follow.

The second stage is then modi¬ed as follows. For i = 1, . . . , k + 2, let

—(k+1)

vi := (ei1 , . . . , eik , 1) ∈ Z—(k+1) , and let vi denote the image of vi in Z2

¯ .

—(k+1)

Since Z2 is a vector space over the ¬eld Z2 of dimension k+1, the vectors

v1 , . . . , vk+2 must be linearly dependent. Therefore, we use Gaussian elimi-

¯ ¯

nation over Z2 to ¬nd a linear dependence among the vectors v1 , . . . , vk+2 ,

¯ ¯

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

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

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

gether, we obtain

e

e

±2 δ ek+1 = π11 · · · πkk ,

where

k+2

c

±i i .

± :=

i=1

348 Subexponential-time discrete logarithms and factoring

i←0

repeat

i←i+1

repeat

choose ±i ∈ Z— at random

n

if i = 1 then choose δ ∈ Z— at random

n

2 δ)

mi ← rep(±i

test if mi is y-smooth (trial division)

until mi = p1i1 · · · peik for some integers ei1 , . . . , eik

e

k

until i = k + 2

set vi ← (ei1 , . . . , eik , 1) ∈ Z—(k+1) for i = 1, . . . , k + 2

apply Gaussian elimination over Z2 to ¬nd integers c1 , . . . , ck+2 ∈

{0, 1}, not all zero, such that

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

e /2 e /2

k+2 ci

· · · πkk δ ’ek+1 /2 ±’1

β ← π1 1

±← i=1 ±i ,

if β = ±1 then

output “failure”

else

output gcd(rep(β ’ 1), n)

Fig. 16.2. Algorithm SEF

Since each ei is even, we can compute

e /2 e /2

· · · πkk δ ’ek+1 /2 ±’1 ,

β := π11

which is a square root of 1 in Zn .

The entire algorithm, called Algorithm SEF, is presented in Fig. 16.2.

Now the analysis. From the discussion above, it is clear that Algorithm

SEF either outputs “failure,” or outputs a non-trivial factor of n. So we have

the same three questions to answer as we did in the analysis of Algorithm

SEDL:

1. What is the expected running time of Algorithm SEF?

2. How should the smoothness parameter y be chosen so as to minimize

the expected running time?

3. What is the probability that Algorithm SEF outputs “failure”?

To answer the ¬rst question, let σ denote the probability that (the

16.3 An algorithm for factoring integers 349

canonical representative of) a random element of Z— is y-smooth. For

n

i = 1, . . . , k + 2, let Xi denote the number iterations of the inner loop

of stage 1 in the ith iteration of the main loop; that is, Xi is the number of

attempts made in ¬nding the ith relation.

Lemma 16.4. For i = 1, . . . , k + 2, we have E[Xi ] = σ ’1 .

Proof. We ¬rst compute E[X1 ]. As δ is chosen uniformly from Z— and n

2 δ is uniformly

independent of ±1 , at each attempt to ¬nd a relation, ±1

distributed over Z— , and hence the probability that the attempt succeeds is

n

precisely σ. This means E[X1 ] = σ ’1 .

We next compute E[Xi ] for i > 1. To this end, let us denote the cosets

of (Z— )2 by Z— as C1 , . . . , Ct . As it happens, t = 2w , but this fact plays no

n n

role in the analysis. For j = 1, . . . , t, let σj denote the probability that a

random element of Cj is y-smooth, and let „j denote the probability that

the ¬nal value of δ belongs to Cj .

We claim that for j = 1, . . . , t, we have „j = σj σ ’1 t’1 . To see this, note

that each coset Cj has the same number of elements, namely, |Z— |t’1 , and n

— |t’1 . Moreover,

so the number of y-smooth elements in Cj is equal to σj |Zn

2

the ¬nal value of ±1 δ is equally likely to be any one of the y-smooth numbers

in Z— , of which there are σ|Z— |, and hence

n n

σj |Z— |t’1

= σj σ ’1 t’1 ,

n

„j = —|

σ|Zn

which proves the claim.

Now, for a ¬xed value of δ and a random choice of ±i ∈ Z— , one sees

n

2 δ is uniformly distributed over the coset containing δ. Therefore, for

that ±i

j = 1, . . . , t, we have

’1

E[Xi | δ ∈ Cj ] = σj .

It follows that

t

E[Xi | δ ∈ Cj ] · P[δ ∈ Cj ]

E[Xi ] =

j=1

t t

’1 ’1

σj · σj σ ’1 t’1 = σ ’1 ,

· „j =

= σj

j=1 j=1

which proves the lemma. 2

So in stage 1, the expected number of attempts made in generating a

single relation is σ ’1 , each such attempt takes time k · len(n)O(1) , and we

have to generate k + 2 relations, leading to a total expected running time in