Remote Access Mathematics of Computation
Green Open Access

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

Article copyright: © Copyright 1993 American Mathematical Society