Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Using number fields
to compute logarithms in finite fields


Author: Oliver Schirokauer
Journal: Math. Comp. 69 (2000), 1267-1283
MSC (1991): Primary 11Y40, 11Y16; Secondary 11T71
Published electronically: May 24, 1999
MathSciNet review: 1653978
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 $L_{q}[1/3; (64/9)^{1/3}+o(1)],$ where $q$ is the cardinality of the field, $L_{q}[s;c]={\exp }(c(\log q)^{s}(\log \log q)^{1-s}),$ and the $o(1)$ is for $q\to \infty $. The number field sieve factoring algorithm is conjectured to factor a number the size of $q$ in the same amount of time.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11Y40, 11Y16, 11T71

Retrieve articles in all journals with MSC (1991): 11Y40, 11Y16, 11T71


Additional Information

Oliver Schirokauer
Affiliation: Department of Mathematics, Oberlin College, Oberlin, OH 44074
Email: oliver@occs.oberlin.edu

DOI: http://dx.doi.org/10.1090/S0025-5718-99-01137-0
PII: S 0025-5718(99)01137-0
Keywords: Finite field, discrete logarithm, number field sieve
Received by editor(s): July 24, 1997
Received by editor(s) in revised form: July 14, 1998
Published electronically: May 24, 1999
Article copyright: © Copyright 2000 American Mathematical Society