Next: The Number Field Sieve
Up: No Title
Previous: Linear Algebra
Computing Individual Discrete Logarithms
The challenge, provided by M. Shannon of Sun Microsystems, was to find
m such that:

(12) 
where
z = 3088993657925229173047110405354521151032325819440498983565

(13) 
Since z is a square of a primitive root modulo p, there are two
solutions for m in the range
.
These two solutions
are
m = 871373321106180104114279941663066214856051438571369779697

(14) 
and
.
Since the main computation obtained discrete
logarithms of small primes to base g = 1+s, the log of z to base g was
computed, and the value of m in Equation 14 was found by
simple base conversion.
To obtain the log of z to the base g, a modification of the strategy
outlined in [12] was employed. To express z in terms of
what [12] called ``mediumsized primes,'' the numbers
(reduced modulo p) for
were each expressed
as

(15) 
with x and y close to .
(For each k, several (x,y)pairs were tried.) The values of x and y were then factored, and
for those x which split into primes < 10^{10}, the corresponding
values of y were factored, until a value of y was found such that
all of its prime factors were < 10^{10}. This occurred for k = 73,
and the factorizations were:
x 
= 

(16) 
y 
= 

(17) 
where
r_{1} 
= 
20261929, 
(18) 
r_{2} 
= 
435600073, 
(19) 
r_{3} 
= 
124325687, 
(20) 
r_{4} 
= 
832003. 
(21) 
Except for the r_{i}, all the other primes appearing in the
factorizations of x and y were already in the factor base, so it was
only necessary to find the logs of the r_{i}.
If we let r denote one of the r_{i}, its logarithm was computed by
searching for pairs of relatively small integers c and d such that

(22) 
Candidate values of (c,d) were obtained by finding two pairs
(c_{1},d_{1}) and (c_{2},d_{2}) that were quite small and satisfied
Equation 22, and then considering linear combinations
for small integers
and .
The pairs (c_{1},d_{1}) and
(c_{2},d_{2}) were obtained from the continued fraction of ,
where
.
For example, for r = r_{1},
(6254,1691) and
(3683,2244) were used. Each pair (c,d) was tested
to see whether c+ds split into quadratic integers of small norm.
Since the norm of c+ds is
c^{2} + 2d^{2} and so is small, this happened
a large fraction of the time. When it did happen, (cVdT)/r was
tested to see whether it factored into small primes. When this
succeeded, the search was over, and the log of r could be obtained
from the database. For example, for r=r_{1},
(c,d) = (15355,78668)was a good pair, and gave the relation

(23) 
Since the logs of all the factors on the right side of
Equation 23 were in the factor base, this expression
gave the log of r_{1}.
The entire computation took several hours on a DEC VAX 8550
minicomputer. However, with appropriately written programs it should be
possible to carry out similar computations in several minutes. The main
reason for the long time that was required was that testing whether an
integer was smooth was done using a general purpose factoring package
that was available on the VAX. This package does some trial division,
and then applies the multiplepolynomial quadratic sieve. It is only
moderately efficient, and is meant to obtain complete factorizations.
In our approach to computing individual logs, it is only important to
check for smoothness with respect to some bound, and it is only
important to find some smooth numbers. Thus an algorithm utilizing some
combination of trial division, the Pollard method, the elliptic
curve method, and an early abort strategy (well known in integer
factorization) ought to be many times faster. Furthermore, it is
possible to optimize various choices that were made rather arbitrarily
in our implementation. Since even with all of the inefficiencies in our
program, the running time was expected to be (and was) quite moderate,
the optimization task was not undertaken.
Next: The Number Field Sieve
Up: No Title
Previous: Linear Algebra
Brian A. LaMacchia
19991030