The problem of solving a large system of linear equations over a finite field has always loomed as a potential bottleneck in factoring integers and computing discrete logarithms. In fact, the major goal of this project was to explore the extent to which large systems could be solved efficiently. That was also the motivation for working with a much larger factor base than was necessary to break the Sun cryptosystem, and for obtaining many more equations than were needed.
The various algorithms that are available for solving large sparse
linear systems over finite fields are surveyed in [24]. Here we
will only mention briefly how they performed on our problem. The system
of 288,017 equations in 96,321 unknowns was reduced by the structured
Gaussian elimination method to a smaller system of 7,262 equations in
6,006 unknowns. This operation took a couple of hours on the SGI
computer. The resulting smaller system was then solved modulo 2 in 1.9
hours using a conjugate gradient program, and modulo
in
about 44 hours using the Lanczos algorithm. (There was no real need to
solve the system modulo 2, since variables are 0 or 1 depending on
whether the corresponding prime is a quadratic residue modulo p or
not. This exercise was undertaken in order to estimate the efficiency
of the linear algebra algorithms in different settings.) With more
careful programming, that time could be decreased substantially.
One disadvantage of the Gaussian integer scheme that we implemented is that it produces relatively dense equations. Even without using the large prime variation, it gives equations with density comparable to that of the single large prime variation of the quadratic sieve. The linear sieve does not have this disadvantage.
The general conclusion that can be derived from the results of [24] is that linear algebra is likely to be a significant but not an insurmountable problem in computing discrete logarithms modulo large primes. The major difficulty is that, while significant computing resources may be applied to sieving, such power is not available for solving the linear algebra. Sieving may be performed efficiently in a distributed environment, and, as A. Lenstra and M. Manasse have demonstrated, huge amounts of computing power may be obtained from distributed systems of workstations. Solving large systems of linear equations, though, appears to require either a single fast processor or else a closely coupled set of processors. One cannot hope to devote nearly as much computing power to this portion of the algorithm. However, as is explained in [24], one can shift the load onto the sieving part by methods such as obtaining many excess equations or not using techniques that produce dense equations. These methods do decrease the efficiency of the sieving algorithm, but they make the linear algebra easier. In any case, the systems that are likely to arise in the near future appear to be tractable using known techniques.