AMS :: Mathematics of Computation
Leonard M
Advancing research. Creating connections.
https://www.ams.org/images/Logo-Favicon.png
American Mathematical Society
A subexponential algorithm for discrete logarithms over all finite fields

HTML articles powered by AMS MathViewer

by Leonard M. Adleman and Jonathan DeMarrais PDF

Math. Comp. 61 (1993), 1-15 Request permission

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

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. â, Factoring numbers using singular integers, Proc. 23rd Annual ACM Symposium on Theory of Computing, Assoc. Comput. Mach., New York, 1991, pp. 64-71.

Leonard M. Adleman and Ming-Deh A. Huang, Primality testing and abelian varieties over finite fields, Lecture Notes in Mathematics, vol. 1512, Springer-Verlag, Berlin, 1992. MR 1176511, DOI 10.1007/BFb0090185

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.

E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713â735. MR 276200, DOI 10.1090/S0025-5718-1970-0276200-X

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.

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

Don Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory 30 (1984), no.Â 4, 587â594. MR 755785, DOI 10.1109/TIT.1984.1056941

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

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

Harold M. Edwards, Fermatâs last theorem, Graduate Texts in Mathematics, vol. 50, Springer-Verlag, New York-Berlin, 1977. A genetic introduction to algebraic number theory. MR 616635

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

Taher ElGamal, A subexponential-time algorithm for computing discrete logarithms over $\textrm {GF}(p^2)$, IEEE Trans. Inform. Theory 31 (1985), no.Â 4, 473â481. MR 798553, DOI 10.1109/TIT.1985.1057075

Carl Friedrich Gauss, Disquisitiones arithmeticae, Yale University Press, New Haven, Conn.-London, 1966. Translated into English by Arthur A. Clarke, S. J. MR 0197380

D. M. Gordon, Discrete logarithms in ${\text {GF}}(p)$ using the number field sieve, manuscript, April 4, 1990. â, Discrete logarithms in ${\text {GF}}({p^n})$ using the number field sieve, preliminary version, manuscript, November 29, 1990. 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.

H. W. Lenstra Jr., Finding isomorphisms between finite fields, Math. Comp. 56 (1991), no.Â 193, 329â347. MR 1052099, DOI 10.1090/S0025-5718-1991-1052099-2

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

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. R. Lovorn, Rigorous, subexponential algorithms for discrete logarithms over finite fields, Ph.D. Thesis, University of Georgia, May 1992.

Morris Newman, Bounds for class numbers, Proc. Sympos. Pure Math., Vol. VIII, Amer. Math. Soc., Providence, R.I., 1965, pp.Â 70â77. MR 0180544

A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Advances in cryptology (Paris, 1984) Lecture Notes in Comput. Sci., vol. 209, Springer, Berlin, 1985, pp.Â 224â314. MR 825593, DOI 10.1007/3-540-39757-4_{2}0

Carl Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, Discrete algorithms and complexity (Kyoto, 1986) Perspect. Comput., vol. 15, Academic Press, Boston, MA, 1987, pp.Â 119â143. MR 910929

Michael O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), no.Â 2, 273â280. MR 568814, DOI 10.1137/0209024

R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no.Â 1, 84â85. MR 429721, DOI 10.1137/0206006

Lawrence C. Washington, Introduction to cyclotomic fields, Graduate Texts in Mathematics, vol. 83, Springer-Verlag, New York, 1982. MR 718674, DOI 10.1007/978-1-4684-0133-2

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

A. E. Western and J. C. P. Miller, Tables of indices and primitive roots, Royal Society Mathematical Tables, Vol. 9, Published for the Royal Society at the Cambridge University Press, London 1968. MR 0246488

Similar Articles

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

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

Additional Information

© Copyright 1993 American Mathematical Society

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