Discrete logarithms and local units
Author:
- 15 November 1993
- journal article
- Published by The Royal Society in Philosophical Transactions A
- Vol. 345 (1676) , 409-423
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.Keywords
This publication has 11 references indexed in Scilit:
- Discrete Logarithms in $GF ( P )$ Using the Number Field SieveSIAM Journal on Discrete Mathematics, 1993
- The development of the number field sieve1993
- The discrete logarithm problem1991
- Cyclotomic Fields I and II1990
- Algorithms in Number Theory1990
- Factoring Integers with Elliptic CurvesAnnals of Mathematics, 1987
- Discrete logarithms inGF(p)Algorithmica, 1986
- Heuristics on class groups of number fields1984
- On a problem of Oppenheim concerning “factorisatio numerorum”Journal of Number Theory, 1983
- Factoring polynomials with rational coefficientsMathematische Annalen, 1982