Mathematics of Computation

Author(s): Joachim von zur Gathen; Michael Nöcker.
Journal: Math. Comp. 73 (2004), 1499-1523.
MSC (2000): Primary 68Q40; Secondary 11Y16
Posted: September 26, 2003
Retrieve article in: PDF DVI PostScript

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.

1.: Y. ASANO, T. ITOH & S. TSUJII (1989)
Generalised fast algorithm for computing multiplicative inverses in .
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$ , 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 .
Electronics Letters 24(6), 334-335.
35.: T. ITOH & S. TSUJII (1988b)
A Fast Algorithm for Computing Multiplicative Inverses in 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.15em$ Nauk 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

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

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS