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

Remote Access
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

PII: S 0025-5718(1993)1225541-3
Article copyright: © Copyright 1993 American Mathematical Society

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia