Discrete Logarithms in Prime Fields

This section describes the algorithm used to compute discrete logarithms modulo p, where p is the prime used in the Sun NFS cryptosystem. A more detailed description is contained in [12].

All of the fast algorithms known for computing discrete logarithms are forms of the index-calculus algorithm [34]. In the index-calculus algorithm, an initial processing stage computes the discrete logarithms of a set Q of elements in the field. Once this table of logarithms has been computed, any other logarithm may be found relatively quickly utilizing the information in the table.

The basic idea behind the precomputation is to obtain a number of equations in the logarithms of elements of Q, and solve the resulting system modulo the prime factors of p-1. There are many techniques for obtaining the equations. We will discuss three of them: the linear sieve, the residue list sieve, and Gaussian integers. They were all shown in [12] to have the asymptotic running time given by Equation 2.

The first equation generating method is the linear sieve. Let $H = \lfloor \sqrt{p} \rfloor + 1, J = H^2 - p$. Let Q be the factor base, consisting of the ``small primes,'' -1, and the set of integers around H. We will search for pairs of integers (c₁,c₂) such that in

$$(H+c_1)(H+c_2) \equiv J + (c_1+c_2)H + c_1c_2 \bmod p$$

the right-hand side is smooth with respect to the factor base (i.e., all of the factors of J+(c₁+c₂)H+c₁c₂ are in the factor base). For any pair of integers (c₁,c₂) for which J + (c₁+c₂)H + c₁c₂ is smooth with respect to Q, we may write

$$(H+c_1)(H+c_2) \equiv q_{k_1}^{h_1}q_{k_2}^{h_2}\ldots{}q_{k_n}^{h_n} \ \ \bmod p,$$ (5)

where each of the $q_{k_i} \in Q$ (the terms (H+c₁) and (H+c₂) are also assumed to be in Q). Now, taking logs on both sides, we obtain:

$$\log_g (H+c_1) + \log_g (H+c_2) \equiv \sum_i h_i \log_g q_{k_i}\ \ \bmod (p-1),$$ (6)

which is an equation in the logs of elements of the factor base. Thus, by finding a system of such equations, we can solve the system modulo the factors of p-1 and obtain the logarithms of all the elements in the factor base Q.

We use a linear sieve to search for (c₁,c₂) pairs for which (H+c₁)(H+c₂) is smooth with respect to the small primes in Q. Fix c₁, and let C be an array whose indexes are c₂ values we wish to consider. For each prime power q^h with $q \in Q$ and hsufficiently small, compute

$$d \equiv (J+c_1H)(H+c_1)^{-1} \bmod q^h.$$ (7)

Notice that

$$(H+c_1)(H+d) \equiv 0 \bmod q^h$$ (8)

and that

$$(H+c_1)(H+c_2) \equiv 0 \bmod q^h\ \ \ \ \forall c_2 \equiv d \bmod q^h.$$ (9)

Then we may step through the array C of possible c₂ values and add $\log q$ to all locations C[c₂] for which c₂ satisfies Equation 9. The array stores the real logarithm of the ``smooth part'' of the residue. If after all the q^h have been sieved the value stored at C[c₂] is close to the real logarithm of the residue, then that c₂ value yields a Q-smooth residue. The (c₁,c₂) pair may then be used to derive an equation similar to Equation 5 above.

The linear sieve suffers from two main problem. First, the factor base Q is large, since it contains all the H+c_j in addition to the small primes q_i, and thus we must collect many equations so that the resulting system can be solved. In fact, as pointed out in [24], we would really like to have many more equations than unknowns in order to simplify the task of solving the system. The second problem concerns the computation of d in Equation 7. In a test implementation of the linear sieve, we found that the time it took to invert (H+c₁) and calculate d for each prime q^h was greater than the time it took to step through the entire array C! (Notice also that since d depends on c₁ and q^h, it is impossible to precompute d values.) These two problems make the linear sieve undesirable for large values of p. However, these deficiencies are not very serious, at least for $p \lesssim 10^{60}$, and the linear sieve would have been only slightly less efficient than the method that we did implement for attacking the Sun system. In general, the linear sieve has the advantage that it produces sparser equations than the scheme that we actually used.

The second method of equation generation mentioned in [12] is the residue list sieve. We did not even consider implementing it, since it has huge space requirements and is slow.

The third method of equation generation, and the one which was ultimately used, is the method of Gaussian integers [12], which was inspired by the work of ElGamal [16]. The idea here is to map the field GF(p) to a subset of ${\bf Z}^2$. Let r be a small negative integer which is also a quadratic residue modulo p, let S be an integer such that $S^2 \equiv r \bmod p$, and let srepresent the imaginary number $\sqrt{r}$. Choose two integers $T,V \lesssim \sqrt{p}$ such that $T^2 \equiv rV^2 \bmod p$. Let the factor base Q consist of small complex primes x+ys in Z[s], small real primes q (some of which will factor into two complex primes), and the integer V. Now, let p' = T+Vs, and choose g = e + fs to be a complex prime which generates (Z[s]/p')^*. This g is the new base for logarithms.

In order to generate logarithm equations, we search for pairs of integers (c₁,c₂) such that their residue c₁V-c₂T is smooth with respect to the real primes q in the factor base Q. Notice that we may write

$$\begin{eqnarray*}c_1V - c_2T & = & V(c_1+c_2s) - c_2(T+Vs) \\ & \equiv & V(c_1+c_2s) \bmod p'. \end{eqnarray*}$$

If c₁V-c₂T is smooth with respect to the real primes in Q, and (c₁+c₂s) is smooth with respect to the complex primes in Q, we may write a related equation in logarithms to base g. When we map complex numbers a+bs to a+bS and the base g = e+fs to e+fS, the logarithms are preserved.

We again use a sieve to find pairs of integers (c₁,c₂) whose residues c₁V-c₂T are smooth over the small real primes in Q. For a fixed value of c₁, we allocate an array C corresponding to possible values of c₂. For each real prime power q^h, compute

$$d \equiv c_1VT^{-1} \bmod q^h.$$

Every value $c_2 \equiv d \bmod q^h$ will yield a residue c₁V-c₂T with a factor of q^h. If we increment the contents of C[c₂] by the logarithm of q, we may inspect C after all primes have been sieved for c₂ values likely to yield Q-smooth residues c₁V-c₂T.

Notice that the Gaussian integer method avoids both of the major problems associated with the linear sieve. Our factor base is not unreasonably large, since it consists of only the small real and complex primes, plus the integer V. Also, while it is true that we need to calculate the value of $d \equiv c_1VT^{-1} \bmod q^h$ for every value of c₁ and q^h, we can precompute the values of $VT^{-1} \bmod q^h$. Then on every sieve we only need multiply the stored value by c₁modulo q^h. In addition, for our specific p, we were able to avoid performing any multiprecision arithmetic when calculating values of d by appropriately choosing Q and the range of possible c₂ values.