Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

A subexponential algorithm for discrete logarithms over all finite fields


Authors: Leonard M. Adleman and Jonathan DeMarrais
Journal: Math. Comp. 61 (1993), 1-15
MSC: Primary 11Y16; Secondary 11T71
DOI: https://doi.org/10.1090/S0025-5718-1993-1225541-3
MathSciNet review: 1225541
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: There are numerous subexponential algorithms for computing discrete logarithms over certain classes of finite fields. However, there appears to be no published subexponential algorithm for computing discrete logarithms over all finite fields. We present such an algorithm and a heuristic argument that there exists a $ c \in {\Re _{ > 0}}$ such that for all sufficiently large prime powers $ {p^n}$, the algorithm computes discrete logarithms over $ {\text{GF}}({p^n})$ within expected time: $ {e^{c{{(\log ({p^n})\log \log ({p^n}))}^{1/2}}}}$.


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

  • [1] L. M. Adleman, A subexponential algorithm for discrete logarithms with applications to cryptography, Proc. 20th IEEE Found. Comp. Sci. Symp., IEEE Computer Society, Long Beach, CA, 1979, pp. 55-60.
  • [2] -, Factoring numbers using singular integers, Proc. 23rd Annual ACM Symposium on Theory of Computing, Assoc. Comput. Mach., New York, 1991, pp. 64-71.
  • [3] L. M. Adleman and M.-D. A. Huang, Primality testing and Abelian varieties over finite fields, Lecture Notes in Math., vol. 1512, Springer-Verlag, Berlin, 1992. MR 1176511 (93g:11128)
  • [4] L. M. Adleman and H. W. Lenstra, Jr., Finding irreducible polynomials over finite fields, Proc. 18th Annual ACM Symposium on Theory of Computing, Assoc. Comput. Mach., New York, 1986, pp. 350-355.
  • [5] E. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713-735. MR 0276200 (43:1948)
  • [6] E. Bach and J. Shallit, Factoring with cyclotomic polynomials, Proc. 26th IEEE Found. Comp. Sci. Symp., IEEE Computer Society, Los Angeles, CA, 1985, pp. 443-450.
  • [7] E. R. Canfield, P. Erdös, and C. Pomerance, On a problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 1-28. MR 712964 (85j:11012)
  • [8] D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory IT-30 (1984), 587-594. MR 755785 (85h:65041)
  • [9] D. Coppersmith, A. M. Odlyzko, and R. Schroeppel, Discrete logarithms in $ {\text{GF}}(p)$, Algorithmica, 1 (1986), 1-15. MR 833115 (87g:11167)
  • [10] W. Diffe and M. E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory IT-22 (1976), 644-654. MR 0437208 (55:10141)
  • [11] H. M. Edwards, Fermat's Last Theorem, Graduate Texts in Math., vol. 50, Springer-Verlag, New York, 1977. MR 616635 (83b:12001a)
  • [12] T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory IT-31 (1985), 469-472. MR 798552 (86j:94045)
  • [13] -, A subexponential-time algorithm for computing discrete logarithms over $ {\text{GF}}({p^2})$, IEEE Trans. Inform. Theory IT-31 (1985), 473-481. MR 798553 (86j:11130)
  • [14] K. F. Gauss, Disquisitiones arithmeticae, translation A. A. Clarke, Yale Univ. Press, New Haven, CT, 1966. MR 0197380 (33:5545)
  • [15] D. M. Gordon, Discrete logarithms in $ {\text{GF}}(p)$ using the number field sieve, manuscript, April 4, 1990.
  • [16] -, Discrete logarithms in $ {\text{GF}}({p^n})$ using the number field sieve, preliminary version, manuscript, November 29, 1990.
  • [17] M. E. Hellman and J. M. Reyneri, Fast computation of discrete logarithms in $ {\text{GF}}(q)$, Advances in Cryptography: Proceedings of CRYPTO '82 (D. Chaum, R. Rivest, A. Sherman, eds.), Plenum Press, New York, 1983, pp. 3-13.
  • [18] H. W. Lenstra, Jr., Finding isomorphisms between finite fields, Math. Comp. 56 (1991), 329-347. MR 1052099 (91d:11151)
  • [19] -, Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649-673. MR 916721 (89g:11125)
  • [20] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The number field sieve, Proc. 22nd STOC, Assoc. Comput. Mach., New York, 1990, pp. 564-572.
  • [21] R. Lovorn, Rigorous, subexponential algorithms for discrete logarithms over finite fields, Ph.D. Thesis, University of Georgia, May 1992.
  • [22] M. Newman, Bounds for class numbers, Proc. Sympos. Pure Math., vol. 8, Amer. Math. Soc., Providence, RI, 1965, pp. 70-77. MR 0180544 (31:4778)
  • [23] A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Proceedings of Eurocrypt '84 (T. Beth, N. Cot, and I. Ingemarsson, eds.), Lecture Notes in Comput. Sci., vol. 209, Springer-Verlag, Berlin, 1985, pp. 224-314. MR 825593 (87g:11022)
  • [24] C. Pomerance, Fast, rigorous factorization and discrete logarithms, Discrete Algorithms and Complexity (D. S. Johnson, T. Nishizeki, A. Nozaki, and H. S. Wilf, eds.), Academic Press, Orlando, FL, 1987, pp. 119-144. MR 910929 (88m:11109)
  • [25] M. O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), 273-280. MR 568814 (81g:12002)
  • [26] R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), 84-85. MR 0429721 (55:2732)
  • [27] L. C. Washington, Introduction to cyclotomic fields, Graduate Texts in Math., vol. 83, Springer-Verlag, New York, 1982. MR 718674 (85g:11001)
  • [28] D. Wiederman, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory. IT-32 (1986), 54-62. MR 831560 (87g:11166)
  • [29] A. E. Western and J. C. P. Miller, Tables of indices and primitive roots, Royal Society Mathematical Tables, vol. 9, Cambridge Univ. Press, 1968. MR 0246488 (39:7792)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y16, 11T71

Retrieve articles in all journals with MSC: 11Y16, 11T71


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1993-1225541-3
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society