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)

 

A subexponential algorithm for discrete logarithms over all finite fields


Authors: Leonard M. Adleman and Jonathan DeMarrais
Journal: Math. Comp. 61 (1993), 1-15
MSC: Primary 11Y16; Secondary 11T71
MathSciNet review: 1225541
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: There are numerous subexponential algorithms for computing discrete logarithms over certain classes of finite fields. However, there appears to be no published subexponential algorithm for computing discrete logarithms over all finite fields. We present such an algorithm and a heuristic argument that there exists a $ c \in {\Re _{ > 0}}$ such that for all sufficiently large prime powers $ {p^n}$, the algorithm computes discrete logarithms over $ {\text{GF}}({p^n})$ within expected time: $ {e^{c{{(\log ({p^n})\log \log ({p^n}))}^{1/2}}}}$.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y16, 11T71

Retrieve articles in all journals with MSC: 11Y16, 11T71


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1993-1225541-3
PII: S 0025-5718(1993)1225541-3
Article copyright: © Copyright 1993 American Mathematical Society