Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Computing special powers in finite fields


Authors: Joachim von zur Gathen and Michael Nöcker
Journal: Math. Comp. 73 (2004), 1499-1523
MSC (2000): Primary 68Q40; Secondary 11Y16
DOI: https://doi.org/10.1090/S0025-5718-03-01599-0
Published electronically: September 26, 2003
MathSciNet review: 2047098
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. Y. ASANO, T. ITOH & S. TSUJII (1989)
    Generalised fast algorithm for computing multiplicative inverses in $GF(2^m)$.
    Electronics Letters 25(10), 664-665.
  • 2. ALBERT H. BEILER (1964)
    Recreations in the Theory of Numbers: The Queen of Mathematics Entertains.
    Dover Publications, Inc., New York.
  • 3. F. BERGERON, J. BERSTEL & S. BRLEK (1994)
    Efficient computation of addition chains.
    Journal de Theorie des Nombres de Bordeaux 6, 21-38. MR 95m:11144
  • 4. F. BERGERON, J. BERSTEL, S. BRLEK & C. DUBOC (1989)
    Addition Chains Using Continued Fractions.
    Journal of Algorithms 10, 403-412. MR 90i:68044
  • 5. 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.
  • 6. A. BRAUER (1939)
    On addition chains.
    Bulletin of the American Mathematical Society 45, 736-739. MR 1:40a
  • 7. 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.
  • 8. ERNEST F. BRICKELL, DANIEL M. GORDON, KEVIN S. MCCURLEY & DAVID B. WILSON (1992)
    Fast Exponentiation with Precomputation.
    In Advances in Cryptology: Proceedings of EUROCRYPT 1992, Balatonfüred, Hungary, R. RUEPPEL, editor, number 658 in Lecture Notes in Computer Science, 200-207. Springer-Verlag, Berlin.
    ISSN 0302-9743. MR 94e:94002
  • 9. JOHN BRILLHART, D. H. LEHMER, J. L. SELFRIDGE, BRYANT TUCKERMAN & S. S. WAGSTAFF, JR. (2001)
    Factorizations of $b^n\pm 1$, $b=2,3,5,6,7,10,11,12$ up to High Powers.
    Number 22 in Contemporary Mathematics. American Mathematical Society, Providence RI, third edition. MR 90d:11009
  • 10. DAVID G. CANTOR (1989)
    On Arithmetical Algorithms over Finite Fields.
    Journal of Combinatorial Theory, Series A 50, 285-300.MR 90f:11100
  • 11. DAVID G. CANTOR & HANS ZASSENHAUS (1981)
    A New Algorithm for Factoring Polynomials Over Finite Fields.
    Mathematics of Computation 36(154), 587-592. MR 82e:12020
  • 12. WHITFIELD DIFFIE & MARTIN E. HELLMAN (1976)
    New directions in cryptography IT-22(6), 644-654. MR 55:10141
  • 13. PETER DOWNEY, BENTON LEONG & RAVI SETHI (1981)
    Computing Sequences with Addition Chains.
    SIAM Journal on Computing 10(3), 638-646. MR 82h:68064
  • 14. T. ELGAMAL (1985)
    A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms IT-31(4), 469-472. MR 86j:94045
  • 15. SANDRA FEISEL, JOACHIM VON ZUR GATHEN & M. AMIN SHOKROLLAHI (1999)
    Normal bases via general Gauß periods.
    Mathematics of Computation 68(225), 271-290.
    http://www.ams.org/journal-getitem?pii=S0025-5718-99-00988-6. MR 99c:11148
  • 16. S. GAO & H. W. LENSTRA, JR. (1992)
    Optimal normal bases.
    Designs, Codes, and Cryptography 2, 315-323. MR 93j:12003
  • 17. SHUHONG GAO, JOACHIM VON ZUR GATHEN, DANIEL PANARIO & VICTOR SHOUP (2000)
    Algorithms for Exponentiation in Finite Fields.
    Journal of Symbolic Computation 29(6), 879-889.
    http://www.idealibrary.com/links/doi/10.1006/jsco.1999.0309. MR 2002e:68152a
  • 18. JOACHIM VON ZUR GATHEN (1991)
    Efficient and optimal exponentiation in finite fields.
    Computational Complexity 1, 360-394. MR 94a:68061
  • 19. 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.
  • 20. JOACHIM VON ZUR GATHEN & JÜRGEN GERHARD (1999)
    Modern Computer Algebra.
    Cambridge University Press, Cambridge, UK, 1st edition.
    ISBN 0-521-64176-4.
    http://www-math.upb.de/$\sim$aggathen/mca/.
    Second edition 2003. MR 2000j:68205
  • 21. JOACHIM VON ZUR GATHEN & JÜRGEN GERHARD (2002)
    Polynomial factorization over $\mathbb{F} _2$.
    Mathematics of Computation 71(240), 1677-1698.
  • 22. 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.
  • 23. JOACHIM VON ZUR GATHEN & MICHAEL NÖCKER (1997)
    Exponentiation in Finite Fields: Theory and Practice.
    In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: AAECC-12, Toulouse, France, TEO MORA & HAROLD MATTSON, editors, number 1255 in Lecture Notes in Computer Science, 88-113. Springer-Verlag.
    ISSN 0302-9743. MR 99c:68123
  • 24. JOACHIM VON ZUR GATHEN & MICHAEL NÖCKER (1999)
    Computing Special Powers in Finite Fields: Extended Abstract.
    In Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation ISSAC '99, Vancouver, Canada, SAM DOOLEY, editor, 83-90. ACM Press.
    http://doi.acm.org/10.1145/309831.309869. MR 2002a:00022
  • 25. JOACHIM VON ZUR GATHEN & MICHAEL NÖCKER (2003)
    Polynomial and normal bases for finite fields.
    Journal of Cryptology. To appear.
  • 26. JOACHIM VON ZUR GATHEN & MICHAEL NÖCKER (2003) Fast arithmetic with general Gaußperiods. Theoretical Computer Science. To appear.
  • 27. JOACHIM VON ZUR GATHEN & DANIEL PANARIO (2001)
    Factoring Polynomials Over Finite Fields: A Survey.
    Journal of Symbolic Computation 31(1-2), 3-17. http:// www.idealibrary.com/links/doi/10.1006/jsco.1999.1002. MR 2001k:11253
  • 28. JOACHIM VON ZUR GATHEN & FRANCESCO PAPPALARDI (2001)
    Density Estimates Related to Gauß periods.
    Progress in Computer Science and Applied Logic 20, 33-41.
  • 29. JOACHIM VON ZUR GATHEN & VICTOR SHOUP (1992)
    Computing Frobenius maps and factoring polynomials.
    Computational Complexity 2, 187-224. MR 94d:12011
  • 30. CARL FRIEDRICH GAUSS (1801)
    Disquisitiones Arithmeticae.
    Gerh. Fleischer Iun., Leipzig.
    English translation by ARTHUR A. CLARKE, Springer-Verlag, New York, 1986.MR 87f:01105
  • 31. KURT GIRSTMAIR (1995)
    Periodische Dezimalbrüche - was nicht jeder darüber weiß.
    In Jahrbuch Überblicke Mathematik 1995, A. BEUTELSPACHER, editor, 163-179. Vieweg.
  • 32. DANIEL M. GORDON (1998)
    A Survey of Fast Exponentiation Methods.
    Journal of Algorithms 27, 129-146. MR 99g:94014
  • 33. G. H. HARDY & E. M. WRIGHT (1962)
    An introduction to the theory of numbers.
    Clarendon Press, Oxford.
    1st edition 1938.
  • 34. T. ITOH & S. TSUJII (1988a)
    Effective recursive algorithm for computing multiplicative inverses in $GF(2^m)$.
    Electronics Letters 24(6), 334-335.
  • 35. T. ITOH & S. TSUJII (1988b)
    A Fast Algorithm for Computing Multiplicative Inverses in $GF(2^m)$ Using Normal Bases.
    Information and Computation 78, 171-177. MR 89j:11121
  • 36. D. JUNGNICKEL (1993)
    Finite Fields: Structure and Arithmetics.
    BI Wissenschaftsverlag, Mannheim. MR 94g:11109
  • 37. A. KARATSUBA & YU. OFMAN (1962)
    Umnozhenie mnogoznachnykh chisel na avtomatakh.
    Doklady Akademi{\u{\i}}\kern.15emNauk SSSR 145, 293-294.
    Multiplication of multidigit numbers on automata, Soviet Physics-Doklady 7 (1963), 595-596.
  • 38. DONALD E. KNUTH (1962)
    Evaluation of Polynomials By Computer.
    Communications of the ACM 5(1), 595-599. MR 27:970
  • 39. DONALD E. KNUTH (1998)
    The Art of Computer Programming, vol. 2, Seminumerical Algorithms.
    Addison-Wesley, Reading MA, 3rd edition.
    First edition 1969. MR 44:3531
  • 40. D. H. LEHMER (1938)
    Euclid's algorithm for large numbers.
    The American Mathematical Monthly 45, 227-233.
  • 41. 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.
  • 42. R. C. MULLIN, I. M. ONYSZCHUK, S. A. VANSTONE & R. M. WILSON (1989)
    Optimal normal bases in $\mbox{GF}(p^n)$.
    Discrete Applied Mathematics 22, 149-161. MR 90c:11092
  • 43. NICHOLAS PIPPENGER (1980)
    On the evaluation of powers and monomials.
    SIAM Journal on Computing 9(2), 230-250. MR 82c:10064
  • 44. MICHAEL O. RABIN (1980)
    Probabilistic algorithms in finite fields.
    SIAM Journal on Computing 9(2), 273-280. MR 81g:12002
  • 45. A. SCHOLZ (1937)
    Aufgabe 253.
    Jahresberichte der DMV 47, 41-42.
  • 46. A. SCHÖNHAGE (1971)
    Schnelle Berechnung von Kettenbruchentwicklungen.
    Acta Informatica 1, 139-144.
  • 47. A. SCHÖNHAGE (1975)
    A lower bound for the length of addition chains.
    Theoretical Computer Science 1, 1-12. MR 57:18229
  • 48. A. SCHÖNHAGE (1977)
    Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2.
    Acta Informatica 7, 395-398. MR 55:9604
  • 49. ARNOLD SCHÖNHAGE & VOLKER STRASSEN (1971)
    Schnelle Multiplikation großer Zahlen.
    Computing 7, 281-292. MR 45:1431
  • 50. D. R. STINSON (1990)
    Some Observations on Parallel Algorithms for Fast Exponentiation in ${GF}(2^n)$.
    SIAM Journal on Computing 19(4), 711-717. MR 91k:68097
  • 51. VOLKER STRASSEN (1983)
    The computational complexity of continued fractions.
    SIAM Journal on Computing 12(1), 1-27. MR 84b:12004
  • 52. 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.
  • 53. ALFRED WASSERMANN (1993)
    Zur Arithmetik in endlichen Körpern.
    Bayreuther Math. Schriften 44, 147-251. MR 94g:11114
  • 54. 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.
  • 55. ANDREW CHI-CHIH YAO (1976)
    On the Evaluation of Powers.
    SIAM Journal on Computing 5(1), 100-103. MR 52:16128

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 68Q40, 11Y16

Retrieve articles in all journals with MSC (2000): 68Q40, 11Y16


Additional Information

Joachim von zur Gathen
Affiliation: Fakultät für Elektrotechnik, Informatik, Mathematik, Universität Paderborn, D-33095 Paderborn, Germany
Email: gathen@upb.de

Michael Nöcker
Affiliation: Bückeburger Str. 12, D-59174 Kamen, Germany
Email: noecker@upb.de

DOI: https://doi.org/10.1090/S0025-5718-03-01599-0
Received by editor(s): July 28, 2002
Received by editor(s) in revised form: December 9, 2002
Published electronically: September 26, 2003
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society