Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

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

Abstract:

A set $A$ of primes $p$ involving numbers such as $ab^t+c$, where $\vert a\vert,\vert b\vert,\vert c\vert=O(1)$ and $t\to\infty$, is defined. An algorithm for computing discrete logs in the finite field of order $p$ with $p\in A$ is suggested. Its heuristic expected running time is $L_p[\frac13;(\frac{32}{9})^{1/3}]$ for $(\frac{32}{9})^{1/3}=1.526\dotsb$, where $L_p[\alpha;\beta]=\exp((\beta+o(1))\ln^\alpha p(\ln\ln p)^{1-\alpha})$ as $p\to\infty$, $0<\alpha<1$, and $0<\beta$. At present, the most efficient algorithm for computing discrete logs in the finite field of order $p$ for general $p$ is Schirokauer's adaptation of the Number Field Sieve. Its heuristic expected running time is $L_p[\frac13;(\frac{64}{9})^{1/3}]$ for $(\frac{64}{9})^{1/3}=1.9229\dotsb$. Using $p\in A$ rather than general $p$does not enhance the performance of Schirokauer's algorithm. The definition of the set $A$ 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 $p$.


References [Enhancements On Off] (What's this?)

  • 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 $GF(p)$, Algorithmica, 1 (1986), 1-15. MR 87g:11167
  • 5. D. Gordon, Discrete logarithms in $GF(p)$ 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

Similar Articles

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

American Mathematical Society