An algorithm for evaluation

of discrete logarithms in some

nonprime finite fields

Author:
Igor A. Semaev

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

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we propose an algorithm for evaluation of logarithms in the finite fields , where the number has a small primitive factor . The heuristic estimate of the complexity of the algorithm is equal to

, where grows to , and is limited by a polynomial in . The evaluation of logarithms is founded on a new congruence of the kind of D. Coppersmith, , which has a great deal of solutions-pairs of polynomials of small degrees.

**1.**W. Diffie and M. Hellman,*New directions in cryptography*, IEEE Trans. Inform. Theory,**IT-22**(1976), 644-654. MR**55:10141****2.**S. Pohlig and M. Hellman,*An improved algorithm for computing logarithms over and its cryptographic significance*, IEEE Trans. Inform. Theory**IT-24**(1978) 106-110. MR**58:4617****3.**L. Adleman,*A subexponential algorithm for the discrete logarithm problem with applications to cryptography*, 20th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, New York, 1979, pp. 55-60. MR**82a:68004****4.**A. Odlyzko,*Discrete logarithms in finite fields and their cryptographic significance*, Advances in Cryptology, Springer, Berlin and New York, 1985, pp. 224-314. MR**87g:11022****5.**D. Coppersmith,*Fast evaluation of logarithms in fields of characteristic two*, IEEE Trans. Inform. Theory**IT-30**(1984), 587-594. MR**85h:65041****6.**I. A. Semaev,*The number of small solutions of a linear homogeneous congruence*, Mat. Zametki**50**(1991), 102-197; English transl. in Math. Notes,**50**(1991). MR**93c:11001****7.**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.

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
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

DOI:
https://doi.org/10.1090/S0025-5718-98-00969-7

Keywords:
Cryptography,
discrete logarithms,
finite fields

Received by editor(s):
March 30, 1993

Received by editor(s) in revised form:
August 30, 1995

Article copyright:
© Copyright 1998
American Mathematical Society