Primitive normal polynomials over finite fields

Morgan, Ilene H.; Mullen, Gary L.

doi:10.1090/S0025-5718-1994-1257578-3

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