Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Normal bases via general Gauss periods
HTML articles powered by AMS MathViewer

by Sandra Feisel, Joachim von zur Gathen and M. Amin Shokrollahi PDF
Math. Comp. 68 (1999), 271-290 Request permission

Abstract:

Gauss periods have been used successfully as a tool for constructing normal bases in finite fields. Starting from a primitive $r$th root of unity, one obtains under certain conditions a normal basis for $\mathbb {F}_{q^n}$ over $\mathbb {F}_q$, where $r$ is a prime and $nk=r-1$ for some integer $k$. We generalize this construction by allowing arbitrary integers $r$ with $nk=\varphi (r)$, and find in many cases smaller values of $k$ than is possible with the previously known approach.
References
  • David W. Ash, Ian F. Blake, and Scott A. Vanstone, Low complexity normal bases, Discrete Appl. Math. 25 (1989), no. 3, 191–210. MR 1026332, DOI 10.1016/0166-218X(89)90001-2
  • Shuhong Gao, Gauss periods, groups, and normal bases, preprint, 1997.
  • Shuhong Gao, Joachim von zur Gathen, and Daniel Panario, Gauss periods and fast exponentiation in finite fields, Proc. Latin ’95, Valparaiso, Chile, Springer Lecture Notes in Computer Science 911, 1995, pp. 311–322.
  • S. Gao, J. von zur Gathen, and D. Panario, Gauss periods: orders and cryptographical applications, Math. Comp. 67 (1998), 343–352.
  • 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
  • Serge Lang, Algebraic number theory, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. MR 0282947
  • Alfred J. Menezes, Ian F. Blake, XuHong Gao, Ronald C. Mullin, Scott A. Vanstone, and Tomik Yaghoobian, Applications of finite fields, Kluwer Academic Publishers, Norwell MA, 1993.
  • 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
  • Emmy Noether, Normalbasis bei Körpern ohne höhere Verzweigung, Journal für die reine und angewandte Mathematik 167 (1932), 147–152.
  • Alfred Wassermann, Zur Arithmetik in endlichen Körpern, Bayreuth. Math. Schr. 44 (1993), 147–251 (German). Dissertation, Universität Bayreuth, Bayreuth, 1992. MR 1224776
Similar Articles
Additional Information
  • Sandra Feisel
  • Affiliation: Fachbereich 17 Mathematik-Informatik, Universität-GH Paderborn, D-33095 Paderborn, Germany
  • Email: feisel@uni-paderborn.de
  • Joachim von zur Gathen
  • Email: gathen@uni-paderborn.de
  • M. Amin Shokrollahi
  • Affiliation: International Computer Science Institute, 1947 Center Street, Berkeley, CA 94704-1198, USA
  • Email: amin@icsi.berkeley.edu
  • Received by editor(s): October 7, 1996
  • © Copyright 1999 American Mathematical Society
  • Journal: Math. Comp. 68 (1999), 271-290
  • MSC (1991): Primary 11T22; Secondary 11R18, 12E20, 12F10, 68Q40
  • DOI: https://doi.org/10.1090/S0025-5718-99-00988-6
  • MathSciNet review: 1484903