The impact of the number field sieve on the discrete logarithm problem in finite fields
Oliver Schirokauer ยท 2008
Let p be a prime number and n a positive integer, and let q = p n . Let ๐ฝ q be the field of q elements and denote by ๐ฝ * q the multiplicative subgroup of ๐ฝ * q . Assume t and u are elements in ๐ฝ * q with the property that u is in the subgroup generated by t . The discrete logarithm of u with respect to the base t , written log t u , is the least non-negative integer x such that t x = u . In this paper we describe two methods to compute discrete logarithms, both of which derive from the number field sieve (NFS) factoring algorithm described in [Stevenhagen 2008] and [Lenstra and Lenstra 1993].