Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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

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.


References [Enhancements On Off] (What's this?)

  • [1] G. B. Agnew, T. Beth, R. C. Mullin, and S. A. Vanstone, Arithmetic operations in $ GF({2^m})$, J. Cryptology 6 (1993), 3-13. MR 1215353 (93m:94018)
  • [2] S. Akbik, Normal generators over finite fields, J. Number Theory 41 (1992), 146-149. MR 1164792 (93d:11128)
  • [3] J. T. Beard and K. I. West, Some primitive polynomials of the third kind, Math. Comp. 28 (1974), 1166-1167. MR 0366879 (51:3125)
  • [4] L. Carlitz, Primitive roots in a finite field, Trans. Amer. Math. Soc. 73 (1952), 373-382. MR 0051869 (14:539a)
  • [5] S. D. Cohen, Primitive elements and polynomials with arbitrary trace, Discrete Math. 83 (1990), 1-7. MR 1065680 (91h:11143)
  • [6] S. D. Cohen, Primitive elements and polynomials: existence results, 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, pp. 43-55. MR 1199821 (93k:11113)
  • [7] H. Davenport, Bases for finite fields, J. London Math. Soc. 43 (1968), 21-39; Addendum, ibid. 44 (1969), 378. MR 0227144 (37:2729)
  • [8] S. Gao and H. W. Lenstra, Jr., Optimal normal bases, Des. Codes Cryptog. 2 (1992), 315-323. MR 1194773 (93j:12003)
  • [9] J. von zur Gathen and M. Giesbrecht, Constructing normal bases in finite fields, J. Symbolic Comput. 10 (1990), 547-570. MR 1087979 (92e:11142)
  • [10] T. A. Gulliver, M. Serra, and V. K. Bhargava, The generation of primitive polynomials in $ 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), 559-576. MR 1130978 (92i:11127)
  • [11] D. Hachenberger, On primitive and free roots in a finite field, Appl. Alg. Eng., Comm. Computing 3 (1992), 139-150. MR 1325752 (96e:11162)
  • [12] T. Hansen and G. L. Mullen, Primitive polynomials over finite fields, Math. Comp. 59 (1992), 639-643; Supplement: 59 (1992), S47-S50. MR 1134730 (93a:11101)
  • [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] D. Jungnickel, Finite fields, Bibliographisches Institut, Mannheim, Germany, 1993. MR 1238714 (94g:11109)
  • [15] H. W. Lenstra and R. J. Schoof, Primitive normal bases over finite fields, Math. Comp. 48 (1987), 217-231. MR 866111 (88c:11076)
  • [16] R. Lidl, Computational problems in the theory of finite fields, Appl. Alg. Eng., Comm. Computing 2 (1991), 81-89. MR 1325520 (95m:11134)
  • [17] R. Lidl and H. Niederreiter, Finite fields, Encyclopedia Math. Appl., Vol. 20, Addison-Wesley, Reading, MA, 1983. (Now distributed by Cambridge Univ. Press.) MR 1429394 (97i:11115)
  • [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 $ GF({p^n})$, Discrete Appl. Math. 22 (1988/89), 149-161. MR 978054 (90c:11092)
  • [20] H. Niederreiter, Factoring polynomials over finite fields using differential equations and normal bases, Math. Comp. 62 (1994), 819-830. MR 1216262 (94g:11113)
  • [21] S. Schwarz, Irreducible polynomials over finite fields with linearly independent roots, Math. Slovaca 38 (1988), 147-158. MR 945368 (89e:11079)
  • [22] -, Construction of normal bases in cyclic extensions of a field, Czechoslovak Math. J. 38 (1988), 291-312. MR 946299 (89h:12010)
  • [23] I. A. Semaev, Construction of polynomials irreducible over a finite field with linearly independent roots, Math. USSR-Sb. 63 (1989), 507-519. MR 942137 (89i:11135)
  • [24] V. Shoup, Searching for primitive roots in finite fields, Math. Comp. 58 (1992), 369-380. MR 1106981 (92e:11140)
  • [25] I. E. Shparlinski, Computational and algorithmic problems in finite fields, Math. Appl., Kluwer, Dordrecht, 1992. MR 1249064 (94j:11122)
  • [26] S. A. Stepanov and I. E. Shparlinski, On construction of a primitive normal basis of a finite field, Mat. Sbornik 180 (1989), 1067-1072; English transl. in Math. USSR-Sb. 67 (1990), 527-533. MR 1019481 (90j:12003)
  • [27] -, On the construction of primitive elements and primitive normal bases in a finite field, Computational Number Theory (Proc. Colloq. on Comput. Number Theory, Hungary), de Gruyter, Berlin, 1991, pp. 1-14. MR 1151849 (93a:11102)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11T06, 11T30

Retrieve articles in all journals with MSC: 11T06, 11T30


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1994-1257578-3
Keywords: Finite field, primitive normal basis
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society