Computing Individual Discrete Logarithms

The challenge, provided by M. Shannon of Sun Microsystems, was to find m such that:

$$3^m \equiv z \bmod p$$ (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 $0 \leq m \leq p-2$. These two solutions are

 

m = 871373321106180104114279941663066214856051438571369779697 (14)

and $m + \frac{p-1}{2}$. 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 ``medium-sized primes,'' the numbers $z \cdot g^k$ (reduced modulo p) for $k=0,1,\ldots{}$ were each expressed as

$$z \cdot g^k \equiv \frac{x}{y} \bmod p$$ (15)

with x and y close to $\sqrt{p}$. (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¹⁰, the corresponding values of y were factored, until a value of y was found such that all of its prime factors were < 10¹⁰. This occurred for k = 73, and the factorizations were:

  

$$-19 \cdot 41 \cdot 127 \cdot 9257 \cdot 62473 \cdot 653693 \cdot r_1,$$ x = (16)

$$2 \cdot 89 \cdot 785737 \cdot r_2 \cdot r_3 \cdot r_4,$$ y = (17)

where

r₁ = 20261929, (18)

r₂ = 435600073, (19)

r₃ = 124325687, (20)

r₄ = 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

$$cV - dT \equiv 0 \bmod r.$$ (22)

Candidate values of (c,d) were obtained by finding two pairs (c₁,d₁) and (c₂,d₂) that were quite small and satisfied Equation 22, and then considering linear combinations

$$(c,d) = \alpha(c_1,d_1) + \beta(c_2,d_2)$$

for small integers $\alpha$ and $\beta$. The pairs (c₁,d₁) and (c₂,d₂) were obtained from the continued fraction of $\sigma/r$, where $\sigma \equiv T/V \bmod r$. For example, for r = r₁, (-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² + 2d² and so is small, this happened a large fraction of the time. When it did happen, (cV-dT)/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₁, (c,d) = (-15355,78668)was a good pair, and gave the relation

$$r_1 \equiv -\frac{V(1+S)(3-S)(15+23S)(545+21S)}{59 \cdot 2699 \cdot 64781 \cdot 186581 \cdot 253787 \cdot 256079} \bmod p.$$ (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₁.

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 multiple-polynomial 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 $\rho$-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.