Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

An algorithm for evaluation of discrete logarithms in some nonprime finite fields
HTML articles powered by AMS MathViewer

by Igor A. Semaev PDF
Math. Comp. 67 (1998), 1679-1689 Request permission

Abstract:

In this paper we propose an algorithm for evaluation of logarithms in the finite fields $F_{p^n}$, where the number $p^n-1$ has a small primitive factor $r$. The heuristic estimate of the complexity of the algorithm is equal to $\exp ((c+o(1))(\log p r\log ^2r)^{1/3})$, where $n$ grows to $\infty$, and $p$ is limited by a polynomial in $n$. The evaluation of logarithms is founded on a new congruence of the kind of D. Coppersmith, $C(x)^k\equiv D(x)$, which has a great deal of solutions—pairs of polynomials $C(x),D(x)$ of small degrees.
References
  • Whitfield Diffie and Martin E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory IT-22 (1976), no. 6, 644–654. MR 437208, DOI 10.1109/tit.1976.1055638
  • Stephen C. Pohlig and Martin E. Hellman, An improved algorithm for computing logarithms over $\textrm {GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory IT-24 (1978), no. 1, 106–110. MR 484737, DOI 10.1109/tit.1978.1055817
  • 20th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, New York, 1979. Held in San Juan, Puerto Rico, October 29–31, 1979. MR 598097
  • A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Advances in cryptology (Paris, 1984) Lecture Notes in Comput. Sci., vol. 209, Springer, Berlin, 1985, pp. 224–314. MR 825593, DOI 10.1007/3-540-39757-4_{2}0
  • Don Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory 30 (1984), no. 4, 587–594. MR 755785, DOI 10.1109/TIT.1984.1056941
  • I. A. Semaev, On the number of small solutions of a linear homogeneous congruence, Mat. Zametki 50 (1991), no. 4, 102–107, 159 (Russian); English transl., Math. Notes 50 (1991), no. 3-4, 1055–1058 (1992). MR 1162918, DOI 10.1007/BF01137738
  • O. Schirokauer, D. Weber and T. Denny, Discrete logarithms: the effectiveness of the index calculus method, Algorithmic number theory, Lecture notes in computer science; vol. 1122, Springer, Berlin and New York, 1996, pp. 337–361.
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (1991): 11T71, 11Y16, 94A60
  • Retrieve articles in all journals with MSC (1991): 11T71, 11Y16, 94A60
Additional Information
  • Igor A. Semaev
  • Affiliation: 43-2 Profsoyuznaya Street, Apartment #723, 117420 Moscow, Russia
  • Received by editor(s): March 30, 1993
  • Received by editor(s) in revised form: August 30, 1995
  • © Copyright 1998 American Mathematical Society
  • Journal: Math. Comp. 67 (1998), 1679-1689
  • MSC (1991): Primary 11T71, 11Y16, 94A60
  • DOI: https://doi.org/10.1090/S0025-5718-98-00969-7
  • MathSciNet review: 1474656