Conclusions and recommendations

The basic conclusion to be drawn from this paper is that computing discrete logs in prime fields GF (p) with the Gaussian integer method is not much harder than factoring composite integers n with $n \approx p$ with the multiple polynomial quadratic sieve. Right now roughly 110 decimal digit integers are being factored in several months of elapsed time using idle time on hundreds of workstations all over the world. Since workstations are becoming dramatically faster and more numerous, and much more widely connected to networks, it seems prudent to allow for at least a 100-fold increase in the available computing power over the next few years, which would allow factoring of integers in the 130-140 decimal digit range. Furthermore, since many discrete log cryptographic schemes have the feature that they use a fixed prime which cannot easily be changed, one has to allow for attacks that consume not just a couple of months, but even a couple of years of computing time. Therefore even 512-bit primes appear to offer only marginal security, even against the Gaussian integer scheme.