Special prime numbers and discrete logs in finite prime fields

Author:
Igor A. Semaev

Journal:
Math. Comp. **71** (2002), 363-377

MSC (2000):
Primary 11Y16, 94A60

DOI:
https://doi.org/10.1090/S0025-5718-00-01308-9

Published electronically:
October 17, 2000

MathSciNet review:
1863007

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

A set of primes involving numbers such as , where and , is defined. An algorithm for computing discrete logs in the finite field of order with is suggested. Its heuristic expected running time is for , where as , , and . At present, the most efficient algorithm for computing discrete logs in the finite field of order for general is Schirokauer's adaptation of the Number Field Sieve. Its heuristic expected running time is for . Using rather than general does not enhance the performance of Schirokauer's algorithm. The definition of the set and the algorithm suggested in this paper are based on a more general congruence than that of the Number Field Sieve. The congruence is related to the resultant of integer polynomials. We also give a number of useful identities for resultants that allow us to specify this congruence for some .

**1.**W. Diffie and M. Hellman,*New directions in cryptography*, IEEE Transactions on Information Theory,**22**(1976), 644-654. MR**55:10141****2.**T. El Gamal,*A public key cryptosystem and a signature scheme based on discrete logarithms*, IEEE Transactions on Information Theory,**31**(1985), 469-472. MR**86j:94045****3.**O. Schirokauer,*Discrete logarithms and local units*, Philosophical Transactions of the Royal Society of London (A),**345**(1993), 409-423. MR**95c:11156****4.**D. Coppersmith, A. M. Odlyzko, and R. Schroeppel,*Discrete logarithms in*, Algorithmica,**1**(1986), 1-15. MR**87g:11167****5.**D. Gordon,*Discrete logarithms in using the number field sieve*, SIAM Journal of Discrete Mathematics,**6**(1993), 124-138. MR**94d:11104****6.**K. McCurley,*The discrete logarithm problem*, Cryptology and computational number theory (C. Pomerance, ed.), Proceedings of Symposia in Applied Mathematics, Amer. Math. Soc., Providence, RI, 1990, vol. 42, pp. 49-74. MR**92d:11133****7.**D. Weber and T. Denny,*The solution of McCurley's discrete log challenge*. Advances in cryptology-CRYPTO '98, Lecture Notes in Computer Science, vol. 1462, Springer-Verlag, Berlin, 1998, pp. 458-471. MR**99i:94057****8.**B. L. van der Waerden,*Algebra*1, Achte Auflage der Modern Algebra, Springer-Verlag, Berlin, 1971. MR**41:8186****9.**I. A. Semaev,*A generalization of the number field sieve*, Probabilistic methods in Discrete Mathematics (Petrozavodsk, 1996), VSP, Utrecht, 1997, pp. 45-63. MR**99j:11146****10.**M. Elkenbracht-Huising,*A multiple polynomial general number field sieve*, Algorithmic Number Theory, Proceedings of ANTS-2, Lecture Notes in Computer Science, vol. 1122, Springer-Verlag, New York, 1996, pp. 99-114.**11.**I. A. Semaev,*Evaluation of linear relations between vectors of a lattice in Euclidean space*, Algorithmic Number Theory, Proceedings of ANTS-3, Lecture Notes in Computer Science, vol. 1423, Springer-Verlag, New York, 1998, pp. 311-323.**12.**E. R. Canfield, P. Erdos, and C. Pomerance,*On a problem of Oppenheim concerning ``factorisatio numerorum''*, Journal of Number Theory,**17**(1983), 1-28. MR**85j:11012****13.**D. Wiedemann,*Solving sparse linear equations over finite fields*, IEEE Transactions on Information Theory,**32**(1986), 54-62. MR**87g:11166****14.**H. W. Lenstra, Jr.,*Factoring integers with elliptic curves*, Annals of Mathematics,**126**(1987), 649-673. MR**89g:11125****15.**V. Shoup,*Searching for primitive roots in finite fields*, Mathematics of Computation,**58**(1992), 369-380. MR**92e:11140**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
11Y16,
94A60

Retrieve articles in all journals with MSC (2000): 11Y16, 94A60

Additional Information

**Igor A. Semaev**

Affiliation:
Profsoyuznaya ul. 43, korp. 2, kv. 723, 117420 Moscow, Russia

Email:
semaev@box.ru

DOI:
https://doi.org/10.1090/S0025-5718-00-01308-9

Keywords:
Cryptography,
discrete logarithms,
Number Field Sieve

Received by editor(s):
July 16, 1998

Received by editor(s) in revised form:
April 3, 2000

Published electronically:
October 17, 2000

Article copyright:
© Copyright 2000
American Mathematical Society