Abstract
Gauss periods can be used to implement finite field arithmetic efficiently. For a small prime p and infinitely many integers n, exponentiation of an arbitrary element in F p n can be done with O(n 2 loglog n) operations in F p , and exponentiation of a Gauss period with O(n 2) operations in F p . Comparing to the previous estimate O(n 2 log nloglog n), using polynomial bases, this shows that normal bases generated by Gauss periods offer some asymptotic computational advantage. Experimental results indicate that Gauss periods are often primitive elements in finite fields.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L.M. Adleman and H.W. Lenstra, Jr., “Finding irreducible polynomials over finite fields”, Proc. 18th Annual ACM Symp. on Theory of Computing (1986), 350–355.
G.B. Agnew, R.C. Mullin, I.M. Onyszchuk and S.A. Vanstone, “An implementation for a fast public key cryptosystem”, J. of Cryptology3 (1991), 63–79.
G.B. Agnew, R.C. Mullin and S.A. Vanstone, “An implementation of elliptic curve cryptosystems over F2155”, IEEE J. on Selected Areas in Communications11 (1993), 804–813.
E. Artin, Collected Papers, Addison-Wesley, 1965.
D.W. Ash, I.F. Blake and S.A. Vanstone, “Low complexity normal bases”, Discrete Applied Math.25 (1989), 191–210.
E. Bach and J. Shallit, “Factoring with cyclotomic polynomials”, Math. Comp.52 (1989), 201–219.
E.R. Berlekamp, “Bit-serial Reed-Solomon encoders”, IEEE Trans. Info. Th.28 (1982), 869–874.
I.F. Blake, S. Gao and R.C. Mullin, “Specific irreducible polynomials with linearly independent roots over finite fields”, submitted to Linear Algebra and Its Applications, 1993.
E.F. Brickell, D.M. Gordon, K.S. McCurley and D.B. Wilson, “Fast exponentiation with precomputation”, in Proc. Eurocrypt'92, Balatonfured, Hungary, 1992.
J. Brillhart, D.H. Lehmer, J.L. Selfridge, B. Tuckerman and S.S. Wagstaff, “Factorizations of b n±1, b=2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers”, Vol. 22 of Contemporary Mathematics, AMS, 1988, 2nd edition.
D.G. Cantor and E. Kaltofen, “On fast multiplication of polynomials over arbitrary algebras”, Acta Inform. 28 (1991), 693–701.
L. Carlitz, “Primitive roots in finite fields”, J. London Math. Soc.43 (1952), 373–382.
H. Davenport, “Bases for finite fields”, J. London Math. Soc.43 (1968), 21–39.
S. Gao and H.W. Lenstra, Jr., “Optimal normal bases”, Designs, Codes and Cryptography2 (1992), 315–323.
S. Gao and S.A. Vanstone, “On orders of optimal normal basis generators”, 1994, to appear in Mathematics of Computation.
J. von zur Gathen, “Efficient and optimal exponentiation in finite fields”, computational complexity1 (1991), 360–394.
J. von zur Gathen and M. Giesbrecht, “Constructing normal bases in finite fields”, J. Symb. Comp.10 (1990), 547–570.
C.F. Gauss, Disquisitiones Arithmeticae, Braunschweig, 1801. English Edition, Springer-Verlag, 1986.
W. Geiselmann and D. Gollmann, “Symmetry and duality in normal basis multiplication”, AAECC-6, Lecture Notes in Computer Science 357 (1989), Springer-Verlag, 230–238.
C. Hooley, “On Artin's conjecture”, J. reine angew. Math.226 (1967), 209–220.
D. Jungnickel, Finite Fields: Structure and Arithmetics, Bibliographisches Institut, Mannheim, 1993.
H.W. Lenstra, Jr. and R.J. Schoof, “Primitive normal bases for finite fields”, Math. Comp.48 (1987), 217–231.
A.J. Menezes, I.F. Blake, X. Gao, R.C. Mullin, S.A. Vanstone and T. Yaghoobian, Applications of Finite Fields, Kluwer Academic Publishers, Boston-Dordrecht-Lancaster, 1993.
R.C. Mullin, I.M. Onyszchuk, S.A. Vanstone and R.M. Wilson, “Optimal normal bases in GF(pn)”, Discrete Applied Math.22 (1988/1989), 149–161.
M. Pohst and H. Zassenhaus, Algorithmic Algebraic Number Theory, Cambridge University Press, 1989.
A. Schönhage, “Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2”, Acta Inf.7 (1977), 395–398.
A. Schönhage and V. Strassen, “Schnelle Multiplikation großer Zahlen”, Computing7 (1971), 281–292.
V. Shoup, “Exponentiation in GF(2n) using fewer polynomial multiplications”, preprint, 1994.
S.A. Stepanov and I.E. Shparlinskiy, “On construction of primitive elements and primitive normal bases in a finite field”, in Computational Number Theory, ed. A. Pethő, M.E. Pohst, H.C. Williams and H.G. Zimmer, 1991. (Proc. Colloq. Comp. Number Theory, Hungary, 1990).
D.H. Stinson, “Some observations on parallel algorithms for fast exponentiation in GF(2n)”, SIAM J. Computing19 (1990), 711–717.
T. Storer, Cyclotomy and Difference Sets, Markham, Chicago, 1967.
V. Strassen, “Gaussian elimination is not optimal”, Numer. Mathematik13 (1969), 354–356.
C.C. Wang, “An algorithm to design finite field multipliers using a self-dual normal basis”, IEEE Trans. Comput.38 (1989), 1457–1460.
L.C. Washington, Introduction to Cyclotomic Fields, Springer-Verlag, New York, 1982.
A. Wassermann, “Konstruktion von Normalbasen”, Bayreuther Mathematische Schriften31 (1990), 155–164.
A. Wassermann, “Zur Arithmetik in endlichen Körpern”, Bayreuther Mathematische Schriften44 (1993), 147–251.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gao, S., von zur Gathen, J., Panario, D. (1995). Gauss periods and fast exponentiation in finite fields. In: Baeza-Yates, R., Goles, E., Poblete, P.V. (eds) LATIN '95: Theoretical Informatics. LATIN 1995. Lecture Notes in Computer Science, vol 911. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-59175-3_98
Download citation
DOI: https://doi.org/10.1007/3-540-59175-3_98
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-59175-7
Online ISBN: 978-3-540-49220-7
eBook Packages: Springer Book Archive