Evaluating logarithms in GF(2n)

ABSTRACT

We present a method for determining logarithms in GF(2n). Its asymptotic running time is O( exp (cn1/3log2/3n)) for a small constant c, while, by comparison, Adleman's scheme runs in time O( exp (c'n1/2log1/2n)). The ideas give a dramatic improvement even for moderate-sized fields such as GF(2127), and make (barely) possible computations in fields of size around 2400. The method is not applicable to GF(q) for a large prime q.

REFERENCES

• 1: L. Adleman, "A Subexponential Algorithm for the Discrete Logarithm Problem with Applications to Cryptography," Proc. IEEE 20th Annual Symposium on Foundations of Computer Science, 55-60 (1979).
• 2: E.R. Berlekamp, "Factoring polynomials over finite fields," Bell System Tech. J. 46(1967), pp. 1853-1859.
• 3: I.F. Blake, R. Fuji-Hara, R.C. Mullin and S.A. Vanstone, "Computing Logarithms in Finite Fields of Characteristic Two." Submitted to SIAM Journal on Algebraic and Discrete Methods.
• 4: D. Coppersmith, "Fast Evaluation of Logarithms in Fields of Characteristic Two," Research Report No. RC 10187, IBM T. J. Watson Research Center, Yorktown Heights, N. Y., 10598, October 3, 1983; to appear, IEEE Transactions on Information Theory.
• 5: W. Diffie and M.E. Hellman, "New Directions in Cryptography," IEEE Trans. Information Theory, vol. IT-22, pp.644-654 (1976).
• 6: M.E. Hellman, "On the Difficulty of Computing Logarithms Over GF(QM)," Proceedings of the 1980 Symposium on Security and Privacy, Oakland, CA, April 14-16, 1980, 83(1980).
• 7: M.E. Hellman and J.M. Reyneri, "Fast computation of discrete logarithms in GF(q)", Advances in Cryptography: Proceedings of CRYPTO '82, D. Chaum, R. Rivest, and A. Sherman, eds., pp. 3-13, Plenum Press, 1983.
• 8: Richard D. Jenks , Barry M. Trager, A language for computational algebra, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.6-13, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806363]
• 9: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 10: J.L. Massey, "Logarithms in finite cyclic groups—cryptographic issues," 4-th Symp. on Info. Th. in BENELUX, Haasrode, Belgium, May 26-27, 1983; preprint.
• 11: M. Morrison and J. Brillhart, "A Method of Factoring and the Factorization of F7'" Math. Comp., v. 29, 129, pp. 183-205.
• 12: A.M. Odlyzko, "Discrete logarithms in finite fields and their cryptographic significance," Bell Laboratories Internal Technical Memorandum, September 27, 1983.
• 13: N. Zierler, "A conversion algorithm for logarithms on GF(2n)", Journal of Pure and Applied Algebra 4 (1974), pp. 353-356.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms, Security, Theory