Primitive normal polynomials over finite fields
Authors:
Ilene H. Morgan and Gary L. Mullen
Journal:
Math. Comp. 63 (1994), 759-765
MSC:
Primary 11T06; Secondary 11T30
DOI:
https://doi.org/10.1090/S0025-5718-1994-1257578-3
MathSciNet review:
1257578
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: In this note we significantly extend the range of published tables of primitive normal polynomials over finite fields. For each ${p^n} < {10^{50}}$ with $p \leq 97$, we provide a primitive normal polynomial of degree n over ${F_p}$. Moreover, each polynomial has the minimal number of nonzero coefficients among all primitive normal polynomials of degree n over ${F_p}$. The roots of such a polynomial generate a primitive normal basis of ${F_{{p^n}}}$ over ${F_p}$, and so are of importance in many computational problems. We also raise several conjectures concerning the distribution of such primitive normal polynomials, including a refinement of the primitive normal basis theorem.
- G. B. Agnew, T. Beth, R. C. Mullin, and S. A. Vanstone, Arithmetic operations in ${\rm GF}(2^m)$, J. Cryptology 6 (1993), no. 1, 3–13. MR 1215353, DOI https://doi.org/10.1007/BF02620228
- Safwan Akbik, Normal generators of finite fields, J. Number Theory 41 (1992), no. 2, 146–149. MR 1164792, DOI https://doi.org/10.1016/0022-314X%2892%2990114-5
- Jacob T. B. Beard Jr. and Karen I. West, Some primitive polynomials of the third kind, Math. Comp. 28 (1974). MR 366879, DOI https://doi.org/10.1090/S0025-5718-1974-0366879-X
- L. Carlitz, Primitive roots in a finite field, Trans. Amer. Math. Soc. 73 (1952), 373–382. MR 51869, DOI https://doi.org/10.1090/S0002-9947-1952-0051869-9
- Stephen D. Cohen, Primitive elements and polynomials with arbitrary trace, Discrete Math. 83 (1990), no. 1, 1–7. MR 1065680, DOI https://doi.org/10.1016/0012-365X%2890%2990215-4
- Stephen D. Cohen, Primitive elements and polynomials: existence results, Finite fields, coding theory, and advances in communications and computing (Las Vegas, NV, 1991) Lecture Notes in Pure and Appl. Math., vol. 141, Dekker, New York, 1993, pp. 43–55. MR 1199821
- H. Davenport, Bases for finite fields, J. London Math. Soc. 43 (1968), 21–39. MR 227144, DOI https://doi.org/10.1112/jlms/s1-43.1.21
- Shuhong Gao and Hendrik W. Lenstra Jr., Optimal normal bases, Des. Codes Cryptogr. 2 (1992), no. 4, 315–323. MR 1194773, DOI https://doi.org/10.1007/BF00125200
- Joachim von zur Gathen and Mark Giesbrecht, Constructing normal bases in finite fields, J. Symbolic Comput. 10 (1990), no. 6, 547–570. MR 1087979, DOI https://doi.org/10.1016/S0747-7171%2808%2980158-7
- T. Aaron Gulliver, Micaela Serra, and Vijay K. Bhargava, The generation of primitive polynomials in ${\rm GF}(q)$ with independent roots and their applications for power residue codes, VLSI testing and finite field multipliers using normal basis, Internat. J. Electron. 71 (1991), no. 4, 559–576. MR 1130978, DOI https://doi.org/10.1080/00207219108925501
- Dirk Hachenberger, On primitive and free roots in a finite field, Appl. Algebra Engrg. Comm. Comput. 3 (1992), no. 2, 139–150. MR 1325752, DOI https://doi.org/10.1007/BF01387196
- Tom Hansen and Gary L. Mullen, Primitive polynomials over finite fields, Math. Comp. 59 (1992), no. 200, 639–643, S47–S50. MR 1134730, DOI https://doi.org/10.1090/S0025-5718-1992-1134730-7 ---, Primitive polynomials of low weight, Finite Fields, Coding Theory, and Advances in Communications and Computing (G. L. Mullen and P. J.-S. Shiue, eds.), Lecture Notes in Pure and Appl. Math., vol. 141, Marcel Dekker, New York, 1993, p. 434.
- Dieter Jungnickel, Finite fields, Bibliographisches Institut, Mannheim, 1993. Structure and arithmetics. MR 1238714
- H. W. Lenstra Jr. and R. J. Schoof, Primitive normal bases for finite fields, Math. Comp. 48 (1987), no. 177, 217–231. MR 866111, DOI https://doi.org/10.1090/S0025-5718-1987-0866111-3
- Rudolf Lidl, Computational problems in the theory of finite fields, Appl. Algebra Engrg. Comm. Comput. 2 (1991), no. 2, 81–89. MR 1325520, DOI https://doi.org/10.1007/BF01810569
- Rudolf Lidl and Harald Niederreiter, Finite fields, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge, 1997. With a foreword by P. M. Cohn. MR 1429394 A. J. Menezes, ed., Applications of finite fields, Kluwer, Dordrecht, 1993.
- R. C. Mullin, I. M. Onyszchuk, S. A. Vanstone, and R. M. Wilson, Optimal normal bases in ${\rm GF}(p^n)$, Discrete Appl. Math. 22 (1988/89), no. 2, 149–161. MR 978054, DOI https://doi.org/10.1016/0166-218X%2888%2990090-X
- Harald Niederreiter, Factoring polynomials over finite fields using differential equations and normal bases, Math. Comp. 62 (1994), no. 206, 819–830. MR 1216262, DOI https://doi.org/10.1090/S0025-5718-1994-1216262-2
- Štefan Schwarz, Irreducible polynomials over finite fields with linearly independent roots, Math. Slovaca 38 (1988), no. 2, 147–158 (English, with Russian summary). MR 945368
- Štefan Schwarz, Construction of normal bases in cyclic extensions of a field, Czechoslovak Math. J. 38(113) (1988), no. 2, 291–312. MR 946299
- I. A. Semaev, Construction of polynomials, irreducible over a finite field, with linearly independent roots, Mat. Sb. (N.S.) 135(177) (1988), no. 4, 520–532, 560 (Russian); English transl., Math. USSR-Sb. 63 (1989), no. 2, 507–519. MR 942137, DOI https://doi.org/10.1070/SM1989v063n02ABEH003288
- Victor Shoup, Searching for primitive roots in finite fields, Math. Comp. 58 (1992), no. 197, 369–380. MR 1106981, DOI https://doi.org/10.1090/S0025-5718-1992-1106981-9
- Igor E. Shparlinski, Computational and algorithmic problems in finite fields, Mathematics and its Applications (Soviet Series), vol. 88, Kluwer Academic Publishers Group, Dordrecht, 1992. MR 1249064
- S. A. Stepanov and I. E. Shparlinskiĭ, On the construction of a primitive normal basis of a finite field, Mat. Sb. 180 (1989), no. 8, 1067–1072, 1151 (Russian); English transl., Math. USSR-Sb. 67 (1990), no. 2, 527–533. MR 1019481, DOI https://doi.org/10.1070/SM1990v067n02ABEH001369
- S. A. Stepanov and I. E. Shparlinskiy, On the construction of primitive elements and primitive normal bases in a finite field, Computational number theory (Debrecen, 1989) de Gruyter, Berlin, 1991, pp. 1–14. MR 1151849
Retrieve articles in Mathematics of Computation with MSC: 11T06, 11T30
Retrieve articles in all journals with MSC: 11T06, 11T30
Additional Information
Keywords:
Finite field,
primitive normal basis
Article copyright:
© Copyright 1994
American Mathematical Society