Royal Society Publishing

Discrete Logarithms and Local Units

Oliver Schirokauer

Abstract

Let K be a number field and $\scr{O}_{K}$ its ring of integers. Let l be a prime number and e a positive integer. We give a method to construct l$^{e}$th powers in $\scr{O}_{K}$ using smooth algebraic integers. This method makes use of approximations of the l-adic logarithm to identify l$^{e}$th powers. One version we give is successful if the class number of K is not divisible by l and if the units in $\scr{O}_{K}$ which are congruent to 1 modulo l$^{e+1}$ are l$^{e}$th powers. A second version only depends on Leopoldt's conjecture. We use the technique of constructing l$^{e}$th 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 that the expected running time of our algorithm is L$_{p}$[1/3; (64/9)$^{1/3}$ + o(1)] for p $\rightarrow \infty $, where L$_{p}$[s;c] = exp (c (log q)$^{s}$ (log log q)$^{1-s}$). This is the same running time as is conjectured for the number field sieve factoring algorithm.

Royal Society Login

Log in through your institution