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
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