Computation of discrete logarithms in prime fields (Q1179517)

Let \(p\) be a prime and \(g\), \(x\) integers. The computation of \(y\) such that \(y\equiv g^ x(\mod p)\), \(0\leq y\leq p-1\), is referred to as discrete exponentiation. Given \(p\), \(g\) and \(y\) the computation of \(x\) is referred to as the discrete logarithm problem. Using the best published algorithms the problem has a running time on the order of \[ \exp((1+o(1))(\log p)^{1/2}(\log \log p)^{1/2})\text{ as } p\to\infty, \] which is on the same order as the time required to factor an integer of the same magnitude. This paper describes an attack on the Sun Microsystems Inc. secure identification system which uses discrete exponentiation modulo a prime of 192 bits, giving the first experimental evidence of discrete logarithms modulo a prime. The precomputation stage that constructs a database of logarithms for small primes used the method of Gaussian integers to generate equations. For the Sun prime of interest the database required a few days of computation on moderately sized machines to compute the database of less than one megabyte and a few minutes to then compute a particular logarithm. It is noted that the more recent number field sieve for factoring integers is likely to improve the running time for discrete logarithms.