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
HTML articles powered by AMS MathViewer

by Ilene H. Morgan and Gary L. Mullen PDF

Math. Comp. 63 (1994), 759-765 Request permission

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.

References

G. B. Agnew, T. Beth, R. C. Mullin, and S. A. Vanstone, Arithmetic operations in $\textrm {GF}(2^m)$, J. Cryptology 6 (1993), no. 1, 3–13. MR 1215353, DOI 10.1007/BF02620228
Safwan Akbik, Normal generators of finite fields, J. Number Theory 41 (1992), no. 2, 146–149. MR 1164792, DOI 10.1016/0022-314X(92)90114-5
Jacob T. B. Beard Jr. and Karen I. West, Some primitive polynomials of the third kind, Math. Comp. 28 (1974). MR 366879, DOI 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 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 10.1016/0012-365X(90)90215-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 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 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 10.1016/S0747-7171(08)80158-7
T. Aaron Gulliver, Micaela Serra, and Vijay K. Bhargava, The generation of primitive polynomials in $\textrm {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 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 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 10.1090/S0025-5718-1992-1134730-7

Primitive polynomials of low weight

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 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 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

Applications of finite fields

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
Harald Niederreiter, Factoring polynomials over finite fields using differential equations and normal bases, Math. Comp. 62 (1994), no. 206, 819–830. MR 1216262, DOI 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 10.1070/SM1989v063n02ABEH003288
Victor Shoup, Searching for primitive roots in finite fields, Math. Comp. 58 (1992), no. 197, 369–380. MR 1106981, DOI 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, DOI 10.1007/978-94-011-1806-4
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 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