Discrete logarithms and local units
Oliver Schirokauer · Philosophical Transactions of the Royal Society of London Series A Physical and Engineering Sciences · 1993
Abstract Let K be a number field and (9K its ring of integers. Let l be a prime number and e a positive integer. We give a method to construct leth powers in (9K using smooth algebraic integers. This method makes use of approximations of the l-adic logarithm to identify leth powers. One version we give is successful if the class number of K is not divisible by l and if the units in CK which are congruent to 1 modulo le+1 are leth powers. A second version only depends on Leopoldt’s conjecture. We use the technique of constructing leth powers to find discrete logarithms in a finite field of prime order. Our method for computing discrete logarithms is closely modelled after Gordon’s adaptation of the number field sieve to this problem. We conjecture th at the expected running time of our algorithm is Lp[1/3; (64/9)1/3 + o(1)] for p-> oo, where Lp[s; c] = exp (c (log q)s (log log q)1-8). This is the same running time as is conjectured for the number field sieve factoring algorithm.