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, 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 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 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 $\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
Additional Information
- © Copyright 1994 American Mathematical Society
- 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