Generators and irreducible polynomials over finite fields

Author:
Daqing Wan

Journal:
Math. Comp. **66** (1997), 1195-1212

MSC (1991):
Primary 11T24, 11T55

MathSciNet review:
1401947

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Weil's character sum estimate is used to study the problem of constructing generators for the multiplicative group of a finite field. An application to the distribution of irreducible polynomials is given, which confirms an asymptotic version of a conjecture of Hansen-Mullen.

**[BDS]**Eric Bach, James Driscoll, and Jeffrey Shallit,*Factor refinement*, J. Algorithms**15**(1993), no. 2, 199–222. MR**1231441**, 10.1006/jagm.1993.1038**[Ch]**F. R. K. Chung,*Diameters and eigenvalues*, J. Amer. Math. Soc.**2**(1989), no. 2, 187–196. MR**965008**, 10.1090/S0894-0347-1989-0965008-X**[Co]**Stephen D. Cohen,*Primitive elements and polynomials with arbitrary trace*, Discrete Math.**83**(1990), no. 1, 1–7. MR**1065680**, 10.1016/0012-365X(90)90215-4**[EH]**Gove W. Effinger and David R. Hayes,*Additive number theory of polynomials over a finite field*, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1991. Oxford Science Publications. MR**1143282****[Ha1]**W. B. Han,*Some Applications of Character Sums in Finite Fields and Coding Theory*, Ph.D. Dissertation, Sichuan University, 1994.**[Ha2]**Wen Bao Han,*The coefficients of primitive polynomials over finite fields*, Math. Comp.**65**(1996), no. 213, 331–340. MR**1320895**, 10.1090/S0025-5718-96-00663-1**[HM]**Tom Hansen and Gary L. Mullen,*Primitive polynomials over finite fields*, Math. Comp.**59**(1992), no. 200, 639–643, S47–S50. MR**1134730**, 10.1090/S0025-5718-1992-1134730-7**[Ka]**Nicholas M. Katz,*An estimate for character sums*, J. Amer. Math. Soc.**2**(1989), no. 2, 197–200. MR**965007**, 10.1090/S0894-0347-1989-0965007-8**[Le1]**H. W. Lenstra Jr.,*Finding isomorphisms between finite fields*, Math. Comp.**56**(1991), no. 193, 329–347. MR**1052099**, 10.1090/S0025-5718-1991-1052099-2**[Le2]**H. W. Lenstra Jr.,*Multiplicative groups generated by linear expressions*, unpublished notes.**[LS]**H. W. Lenstra Jr. and R. J. Schoof,*Primitive normal bases for finite fields*, Math. Comp.**48**(1987), no. 177, 217–231. MR**866111**, 10.1090/S0025-5718-1987-0866111-3**[Li]**Wen-Ch’ing Winnie Li,*Character sums and abelian Ramanujan graphs*, J. Number Theory**41**(1992), no. 2, 199–217. With an appendix by Ke Qin Feng and the author. MR**1164798**, 10.1016/0022-314X(92)90120-E**[Sh]**Victor Shoup,*Searching for primitive roots in finite fields*, Math. Comp.**58**(1992), no. 197, 369–380. MR**1106981**, 10.1090/S0025-5718-1992-1106981-9**[Shp]**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****[Wa]**Da Qing Wan,*A 𝑝-adic lifting lemma and its applications to permutation polynomials*, 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. 209–216. MR**1199834****[We]**André Weil,*Basic number theory*, 3rd ed., Springer-Verlag, New York-Berlin, 1974. Die Grundlehren der Mathematischen Wissenschaften, Band 144. MR**0427267**

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
with MSC (1991):
11T24,
11T55

Retrieve articles in all journals with MSC (1991): 11T24, 11T55

Additional Information

**Daqing Wan**

Affiliation:
Department of Mathematics, The Pennsylvania State University, University Park, Pennsylvania 16802

Email:
wan@math.psu.edu

DOI:
https://doi.org/10.1090/S0025-5718-97-00835-1

Received by editor(s):
December 8, 1995

Received by editor(s) in revised form:
May 8, 1996

Additional Notes:
This research was partially supported by NSF

Article copyright:
© Copyright 1997
American Mathematical Society