## Special prime numbers and discrete logs in finite prime fields

HTML articles powered by AMS MathViewer

- by Igor A. Semaev;
- Math. Comp.
**71**(2002), 363-377 - DOI: https://doi.org/10.1090/S0025-5718-00-01308-9
- Published electronically: October 17, 2000
- PDF | Request permission

## Abstract:

A set $A$ of primes $p$ involving numbers such as $ab^t+c$, where $|a|,|b|,|c|=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[\frac 13;(\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[\frac 13;(\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

- 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 - Taher ElGamal,
*A public key cryptosystem and a signature scheme based on discrete logarithms*, IEEE Trans. Inform. Theory**31**(1985), no. 4, 469–472. MR**798552**, DOI 10.1109/TIT.1985.1057074 - Oliver Schirokauer,
*Discrete logarithms and local units*, Philos. Trans. Roy. Soc. London Ser. A**345**(1993), no. 1676, 409–423. MR**1253502**, DOI 10.1098/rsta.1993.0139 - Don Coppersmith, Andrew M. Odlzyko, and Richard Schroeppel,
*Discrete logarithms in $\textrm {GF}(p)$*, Algorithmica**1**(1986), no. 1, 1–15. MR**833115**, DOI 10.1007/BF01840433 - Daniel M. Gordon,
*Discrete logarithms in $\textrm {GF}(p)$ using the number field sieve*, SIAM J. Discrete Math.**6**(1993), no. 1, 124–138. MR**1201995**, DOI 10.1137/0406010 - Kevin S. McCurley,
*The discrete logarithm problem*, Cryptology and computational number theory (Boulder, CO, 1989) Proc. Sympos. Appl. Math., vol. 42, Amer. Math. Soc., Providence, RI, 1990, pp. 49–74. MR**1095551**, DOI 10.1090/psapm/042/1095551 - Damian Weber and Thomas Denny,
*The solution of McCurley’s discrete log challenge*, Advances in cryptology—CRYPTO ’98 (Santa Barbara, CA, 1998) Lecture Notes in Comput. Sci., vol. 1462, Springer, Berlin, 1998, pp. 458–471. MR**1670968**, DOI 10.1007/BFb0055747 - B. L. van der Waerden,
*Algebra. Teil I*, Heidelberger Taschenbücher [Heidelberg Paperbacks], Band 12, Springer-Verlag, Berlin-New York, 1966 (German). Siebte Auflage. MR**263581** - I. A. Semaev,
*A generalization of the number field sieve*, Probabilistic methods in discrete mathematics (Petrozavodsk, 1996) VSP, Utrecht, 1997, pp. 45–63. MR**1651131** - 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. - 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. - E. R. Canfield, Paul Erdős, and Carl Pomerance,
*On a problem of Oppenheim concerning “factorisatio numerorum”*, J. Number Theory**17**(1983), no. 1, 1–28. MR**712964**, DOI 10.1016/0022-314X(83)90002-1 - Douglas H. Wiedemann,
*Solving sparse linear equations over finite fields*, IEEE Trans. Inform. Theory**32**(1986), no. 1, 54–62. MR**831560**, DOI 10.1109/TIT.1986.1057137 - H. W. Lenstra Jr.,
*Factoring integers with elliptic curves*, Ann. of Math. (2)**126**(1987), no. 3, 649–673. MR**916721**, DOI 10.2307/1971363 - Victor Shoup,
*Searching for primitive roots in finite fields*, Math. Comp.**58**(1992), no. 197, 369–380. MR**1106981**, DOI 10.1090/S0025-5718-1992-1106981-9

## Bibliographic Information

**Igor A. Semaev**- Affiliation: Profsoyuznaya ul. 43, korp. 2, kv. 723, 117420 Moscow, Russia
- Email: semaev@box.ru
- Received by editor(s): July 16, 1998
- Received by editor(s) in revised form: April 3, 2000
- Published electronically: October 17, 2000
- © Copyright 2000 American Mathematical Society
- Journal: Math. Comp.
**71**(2002), 363-377 - MSC (2000): Primary 11Y16, 94A60
- DOI: https://doi.org/10.1090/S0025-5718-00-01308-9
- MathSciNet review: 1863007