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, S19
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.

[1] G. B. Agnew, T. Beth, R. C. Mullin, and S. A. Vanstone, Arithmetic operations in 𝐺𝐹(2^{𝑚}), J. Cryptology 6 (1993), no. 1, 3–13. MR 1215353, https://doi.org/10.1007/BF02620228
[2] Safwan Akbik, Normal generators of finite fields, J. Number Theory 41 (1992), no. 2, 146–149. MR 1164792, https://doi.org/10.1016/0022-314X(92)90114-5
[3] Jacob T. B. Beard Jr. and Karen I. West, Some primitive polynomials of the third kind, Math. Comp. 28 (1974). MR 366879, https://doi.org/10.1090/S0025-5718-1974-0366879-X
[4] L. Carlitz, Primitive roots in a finite field, Trans. Amer. Math. Soc. 73 (1952), 373–382. MR 51869, https://doi.org/10.1090/S0002-9947-1952-0051869-9
[5] Stephen D. Cohen, Primitive elements and polynomials with arbitrary trace, Discrete Math. 83 (1990), no. 1, 1–7. MR 1065680, https://doi.org/10.1016/0012-365X(90)90215-4
[6] 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
[7] H. Davenport, Bases for finite fields, J. London Math. Soc. 43 (1968), 21–39. MR 227144, https://doi.org/10.1112/jlms/s1-43.1.21
[8] Shuhong Gao and Hendrik W. Lenstra Jr., Optimal normal bases, Des. Codes Cryptogr. 2 (1992), no. 4, 315–323. MR 1194773, https://doi.org/10.1007/BF00125200
[9] Joachim von zur Gathen and Mark Giesbrecht, Constructing normal bases in finite fields, J. Symbolic Comput. 10 (1990), no. 6, 547–570. MR 1087979, https://doi.org/10.1016/S0747-7171(08)80158-7
[10] T. Aaron Gulliver, Micaela Serra, and Vijay K. Bhargava, The generation of primitive polynomials in 𝐺𝐹(𝑞) 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, https://doi.org/10.1080/00207219108925501
[11] Dirk Hachenberger, On primitive and free roots in a finite field, Appl. Algebra Engrg. Comm. Comput. 3 (1992), no. 2, 139–150. MR 1325752, https://doi.org/10.1007/BF01387196
[12] Tom Hansen and Gary L. Mullen, Primitive polynomials over finite fields, Math. Comp. 59 (1992), no. 200, 639–643, S47–S50. MR 1134730, https://doi.org/10.1090/S0025-5718-1992-1134730-7
[13] -, 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.
[14] Dieter Jungnickel, Finite fields, Bibliographisches Institut, Mannheim, 1993. Structure and arithmetics. MR 1238714
[15] H. W. Lenstra Jr. and R. J. Schoof, Primitive normal bases for finite fields, Math. Comp. 48 (1987), no. 177, 217–231. MR 866111, https://doi.org/10.1090/S0025-5718-1987-0866111-3
[16] Rudolf Lidl, Computational problems in the theory of finite fields, Appl. Algebra Engrg. Comm. Comput. 2 (1991), no. 2, 81–89. MR 1325520, https://doi.org/10.1007/BF01810569
[17] 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
[18] A. J. Menezes, ed., Applications of finite fields, Kluwer, Dordrecht, 1993.
[19] R. C. Mullin, I. M. Onyszchuk, S. A. Vanstone, and R. M. Wilson, Optimal normal bases in 𝐺𝐹(𝑝ⁿ), Discrete Appl. Math. 22 (1988/89), no. 2, 149–161. MR 978054, https://doi.org/10.1016/0166-218X(88)90090-X
[20] Harald Niederreiter, Factoring polynomials over finite fields using differential equations and normal bases, Math. Comp. 62 (1994), no. 206, 819–830. MR 1216262, https://doi.org/10.1090/S0025-5718-1994-1216262-2
[21] Š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
[22] Štefan Schwarz, Construction of normal bases in cyclic extensions of a field, Czechoslovak Math. J. 38(113) (1988), no. 2, 291–312. MR 946299
[23] 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, https://doi.org/10.1070/SM1989v063n02ABEH003288
[24] Victor Shoup, Searching for primitive roots in finite fields, Math. Comp. 58 (1992), no. 197, 369–380. MR 1106981, https://doi.org/10.1090/S0025-5718-1992-1106981-9
[25] 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
[26] 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, https://doi.org/10.1070/SM1990v067n02ABEH001369
[27] 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