Using number fields to compute logarithms in finite fields
Open Access
- 24 May 1999
- journal article
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 69 (231) , 1267-1284
- https://doi.org/10.1090/s0025-5718-99-01137-0
Abstract
We describe an adaptation of the number field sieve to the problem of computing logarithms in a finite field. We conjecture that the running time of the algorithm, when restricted to finite fields of an arbitrary but fixed degree, is where is the cardinality of the field, and the is for . The number field sieve factoring algorithm is conjectured to factor a number the size of in the same amount of time.Keywords
This publication has 18 references indexed in Scilit:
- Constructing nonresidues in finite fields and the extended Riemann hypothesisMathematics of Computation, 1996
- Discrete logarithms and local unitsPhilosophical Transactions A, 1993
- Reducing elliptic curve logarithms to logarithms in a finite fieldIEEE Transactions on Information Theory, 1993
- A Subexponential Algorithm for Discrete Logarithms Over all Finite FieldsMathematics of Computation, 1993
- Algorithms in Algebraic Number TheoryBulletin of the American Mathematical Society, 1992
- Searching for Primitive Roots in Finite FieldsMathematics of Computation, 1992
- Factoring with Cyclotomic PolynomialsMathematics of Computation, 1989
- Solving sparse linear equations over finite fieldsIEEE Transactions on Information Theory, 1986
- A subexponential-time algorithm for computing discrete logarithms overGF(p^2)IEEE Transactions on Information Theory, 1985
- On a problem of Oppenheim concerning “factorisatio numerorum”Journal of Number Theory, 1983