Computing special powers in finite fields

von zur Gathen, Joachim; Nöcker, Michael

doi:10.1090/S0025-5718-03-01599-0

Computing special powers in finite fields
HTML articles powered by AMS MathViewer

by Joachim von zur Gathen and Michael Nöcker PDF

Math. Comp. 73 (2004), 1499-1523 Request permission

Abstract:

We study exponentiation in nonprime finite fields with very special exponents such as they occur, for example, in inversion, primitivity tests, and polynomial factorization. Our algorithmic approach improves the corresponding exponentiation problem from about quadratic to about linear time.

References

Y. Asano, T. Itoh & S. Tsujii (1989) Generalised fast algorithm for computing multiplicative inverses in $GF(2^m)$. Electronics Letters 25(10), 664–665.
Albert H. Beiler (1964) Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. Dover Publications, Inc., New York.
F. Bergeron, J. Berstel, and S. Brlek, Efficient computation of addition chains, J. Théor. Nombres Bordeaux 6 (1994), no. 1, 21–38. MR 1305286
F. Bergeron, J. Berstel, S. Brlek, and C. Duboc, Addition chains using continued fractions, J. Algorithms 10 (1989), no. 3, 403–412. MR 1006993, DOI 10.1016/0196-6774(89)90036-9
Olaf Bonorden, Joachim von zur Gathen, Jürgen Gerhard, Olaf Müller & Michael Nöcker (2001). Factoring a binary polynomial of degree over one million. ACM SIGSAM Bulletin 35(1), 16–18. http://www-math.upb.de/$\sim$aggathen/Publications/bongat01.ps.gz.
T. Venkatarayudu, The $7$-$15$ problem, Proc. Indian Acad. Sci., Sect. A. 9 (1939), 531. MR 0000001, DOI 10.1090/gsm/058
Richard P. Brent, Samuli Larvala & Paul Zimmermann (2002) A fast algorithm for testing reducibility of trinomials mod 2 and some new primitive trinomials of degree 3021377. Mathematics of Computation To appear.
R. A. Rueppel (ed.), Advances in cryptology—EUROCRYPT ’92, Lecture Notes in Computer Science, vol. 658, Springer-Verlag, Berlin, 1993. MR 1243657, DOI 10.1007/3-540-47555-9
John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $b^n \pm 1$, 2nd ed., Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, RI, 1988. $b=2,3,5,6,7,10,11,12$ up to high powers. MR 996414, DOI 10.1090/conm/022
David G. Cantor, On arithmetical algorithms over finite fields, J. Combin. Theory Ser. A 50 (1989), no. 2, 285–300. MR 989199, DOI 10.1016/0097-3165(89)90020-4
David G. Cantor and Hans Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), no. 154, 587–592. MR 606517, DOI 10.1090/S0025-5718-1981-0606517-5
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
Peter Downey, Benton Leong, and Ravi Sethi, Computing sequences with addition chains, SIAM J. Comput. 10 (1981), no. 3, 638–646. MR 623072, DOI 10.1137/0210047
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
Sandra Feisel, Joachim von zur Gathen, and M. Amin Shokrollahi, Normal bases via general Gauss periods, Math. Comp. 68 (1999), no. 225, 271–290. MR 1484903, DOI 10.1090/S0025-5718-99-00988-6
Shuhong Gao and Hendrik W. Lenstra Jr., Optimal normal bases, Des. Codes Cryptogr. 2 (1992), no. 4, 315–323. MR 1194773, DOI 10.1007/BF00125200
Shuhong Gao, Joachim Von Zur Gathen, Daniel Panario, and Victor Shoup, Algorithms for exponentiation in finite fields, J. Symbolic Comput. 29 (2000), no. 6, 879–889. MR 1765928, DOI 10.1006/jsco.1999.0309
Joachim von zur Gathen, Efficient and optimal exponentiation in finite fields, Comput. Complexity 1 (1991), no. 4, 360–394. MR 1172675, DOI 10.1007/BF01212964
Joachim von zur Gathen & Jürgen Gerhard (1996) Arithmetic and factorization of polynomials over $\mathbb {Z}_2$. Technical Report tr-rsfb-96-018, University of Paderborn, Germany. 43 pages.
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
Joachim von zur Gathen & Jürgen Gerhard (2002) Polynomial factorization over $\mathbb {F}_2$. Mathematics of Computation 71(240), 1677–1698.
Joachim von zur Gathen, Arnold Knopfmacher, Florian Luca, Lutz Lucht & Igor Shparlinski (2003) Average order in cyclic groups. Journal de Théorie des Nombres de Bordeaux. To appear.
Joachim von zur Gathen and Michael Nöcker, Exponentiation in finite fields: theory and practice, Applied algebra, algebraic algorithms and error-correcting codes (Toulouse, 1997) Lecture Notes in Comput. Sci., vol. 1255, Springer, Berlin, 1997, pp. 88–113. MR 1634108, DOI 10.1007/3-540-63163-1_{8}
Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, Association for Computing Machinery (ACM), New York, 1999. Held in Vancouver, BC, July 28–31, 1999. MR 1802059
Joachim von zur Gathen & Michael Nöcker (2003) Polynomial and normal bases for finite fields. Journal of Cryptology. To appear.
Joachim von zur Gathen & Michael Nöcker (2003) Fast arithmetic with general Gauß periods. Theoretical Computer Science. To appear.
Joachim von zur Gathen and Daniel Panario, Factoring polynomials over finite fields: a survey, J. Symbolic Comput. 31 (2001), no. 1-2, 3–17. Computational algebra and number theory (Milwaukee, WI, 1996). MR 1806203, DOI 10.1006/jsco.1999.1002
Joachim von zur Gathen & Francesco Pappalardi (2001) Density Estimates Related to Gauß periods. Progress in Computer Science and Applied Logic 20, 33–41.
Joachim von zur Gathen and Victor Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), no. 3, 187–224. MR 1220071, DOI 10.1007/BF01272074
Carl Friedrich Gauss, Disquisitiones arithmeticae, Springer-Verlag, New York, 1986. Translated and with a preface by Arthur A. Clarke; Revised by William C. Waterhouse, Cornelius Greither and A. W. Grootendorst and with a preface by Waterhouse. MR 837656
Kurt Girstmair (1995) Periodische Dezimalbrüche - was nicht jeder darüber weiß. In Jahrbuch Überblicke Mathematik 1995, A. Beutelspacher, editor, 163–179. Vieweg.
Daniel M. Gordon, A survey of fast exponentiation methods, J. Algorithms 27 (1998), no. 1, 129–146. MR 1613189, DOI 10.1006/jagm.1997.0913
G. H. Hardy & E. M. Wright (1962) An introduction to the theory of numbers. Clarendon Press, Oxford. 1st edition 1938.
T. Itoh & S. Tsujii (1988a) Effective recursive algorithm for computing multiplicative inverses in $GF(2^m)$. Electronics Letters 24(6), 334–335.
Toshiya Itoh and Shigeo Tsujii, A fast algorithm for computing multiplicative inverses in $\textrm {GF}(2^m)$ using normal bases, Inform. and Comput. 78 (1988), no. 3, 171–177. MR 959807, DOI 10.1016/0890-5401(88)90024-7
Dieter Jungnickel, Finite fields, Bibliographisches Institut, Mannheim, 1993. Structure and arithmetics. MR 1238714
A. Karatsuba & Yu. Ofman (1962) Umnozhenie mnogoznachnykh chisel na avtomatakh. Doklady Akademiĭ Nauk SSSR 145, 293–294. Multiplication of multidigit numbers on automata, Soviet Physics–Doklady 7 (1963), 595–596.
Donald E. Knuth, Evaluation of polynomials by computer, Comm. ACM 5 (1962), 595–599. MR 0150984, DOI 10.1145/355580.369074
Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0286318
D. H. Lehmer (1938) Euclid’s algorithm for large numbers. The American Mathematical Monthly 45, 227–233.
Alfred J. Menezes, Ian F. Blake, XuHong Gao, Ronald C. Mullin, Scott A. Vanstone & Tomik Yaghoobian (1993) Applications of finite fields. Kluwer Academic Publishers, Norwell MA.
R. C. Mullin, I. M. Onyszchuk, S. A. Vanstone, and R. M. Wilson, Optimal normal bases in $\textrm {GF}(p^n)$, Discrete Appl. Math. 22 (1988/89), no. 2, 149–161. MR 978054, DOI 10.1016/0166-218X(88)90090-X
Nicholas Pippenger, On the evaluation of powers and monomials, SIAM J. Comput. 9 (1980), no. 2, 230–250. MR 568812, DOI 10.1137/0209022
Michael O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), no. 2, 273–280. MR 568814, DOI 10.1137/0209024
A. Scholz (1937) Aufgabe 253. Jahresberichte der DMV 47, 41–42.
A. Schönhage (1971) Schnelle Berechnung von Kettenbruchentwicklungen. Acta Informatica 1, 139–144.
Arnold Schönhage, A lower bound for the length of addition chains, Theoret. Comput. Sci. 1 (1975), no. 1, 1–12. MR 478756, DOI 10.1016/0304-3975(75)90008-0
A. Schönhage, Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2, Acta Informat. 7 (1976/77), no. 4, 395–398. MR 0436663, DOI 10.1007/bf00289470
A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
D. R. Stinson, Some observations on parallel algorithms for fast exponentiation in $\textrm {GF}(2^n)$, SIAM J. Comput. 19 (1990), no. 4, 711–717. MR 1053938, DOI 10.1137/0219049
V. Strassen, The computational complexity of continued fractions, SIAM J. Comput. 12 (1983), no. 1, 1–27. MR 687799, DOI 10.1137/0212001
Charles C. Wang, T. K. Truong, Howard M. Shao, Lesslie J. Deutsch, Jim K. Omura & Ivring S. Reed (1985) VLSI Architectures for Computing Multiplications and Inverses in ${GF}(2^m)$ C-34, 709–717.
Alfred Wassermann, Zur Arithmetik in endlichen Körpern, Bayreuth. Math. Schr. 44 (1993), 147–251 (German). Dissertation, Universität Bayreuth, Bayreuth, 1992. MR 1224776
Dazhuan Xu (1990) A fast algorithm for multiplicative inverses based on the normal basis representation. Journal of Nanjing Aeronautical Institute (English edition) 7(1), 121–124.
Andrew Chi Chih Yao, On the evaluation of powers, SIAM J. Comput. 5 (1976), no. 1, 100–103. MR 395331, DOI 10.1137/0205008