Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Searching for primitive roots in finite fields


Author: Victor Shoup
Journal: Math. Comp. 58 (1992), 369-380
MSC: Primary 11T06; Secondary 11Y16
DOI: https://doi.org/10.1090/S0025-5718-1992-1106981-9
MathSciNet review: 1106981
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ {\text{GF}}({p^n})$ be the finite field with $ {p^n}$ elements, where p is prime. We consider the problem of how to deterministically generate in polynomial time a subset of $ {\text{GF}}({p^n})$ that contains a primitive root, i.e., an element that generates the multiplicative group of nonzero elements in $ {\text{GF}}({p^n})$. We present three results. First, we present a solution to this problem for the case where p is small, i.e., $ p = {n^{O(1)}}$ . Second, we present a solution to this problem under the assumption of the Extended Riemann Hypothesis (ERH) for the case where p is large and $ n = 2$ . Third, we give a quantitative improvement of a theorem of Wang on the least primitive root for $ {\text{GF}}(p)$, assuming the ERH.


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

  • [1] L. M. Adleman and H. W. Lenstra, Jr., Finding irreducible polynomials over finite fields, 18th Annual ACM Sympos. on Theory of Computing, 1986, pp. 350-355.
  • [2] N. C. Ankeny, The least quadratic nonresidue, Ann. of Math. (2) 55 (1952), 65-72. MR 0045159 (13:538c)
  • [3] E. Bach and J. von zur Gathen, Deterministic factorization of polynomials over special finite fields, Technical Report 799, Department of Computer Science, University of Wisconsin-Madison, 1988.
  • [4] Z. I. Borevich and I. R. Shafarevich, Number theory, Academic Press, 1966. MR 0195803 (33:4001)
  • [5] D. A. Burgess, Character sums and primitive roots in finite fields, Proc. London Math. Soc. (3) 17 (1967), 11-25. MR 0219516 (36:2597)
  • [6] L. Carlitz, Distribution of primitive roots in a finite field, Quart. J. Math. 4 (1953), 4-10. MR 0056028 (15:13g)
  • [7] J. W. S. Cassels and A. Fröhlich, eds., Algebraic number theory, Academic Press, 1967. MR 0215665 (35:6500)
  • [8] A. L. Chistov, Polynomial time construction of a finite field, Abstracts of Lectures at 7th All-Union Conference in Mathematical Logic, Novosibirsk, 1984, p. 196. (Russian)
  • [9] H. Davenport, On primitive roots in finite fields, Quart. J. Math. (Oxford) 8 (1937), 308-312.
  • [10] H. Davenport and D. J. Lewis, Character sums and primitive roots in finite fields, Rend. Circ. Mat. Palermo 12 (1963), 129-136. MR 0167482 (29:4755)
  • [11] S. A. Evdokimov, Factoring a solvable polynomial over a finite field and generalized Riemann hypothesis, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 176 (1989), 104-117. (Russian) MR 1023599 (91a:11063)
  • [12] J. B. Friedlander, A note on primitive roots in finite fields, Mathematika 19 (1972), 112-114. MR 0316360 (47:4907)
  • [13] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., Oxford Univ. Press, 1984.
  • [14] J. G. Hinz, Character sums and primitive roots in algebraic number fields, Monatsh. Math. 95 (1983), 275-286. MR 718064 (85e:11058)
  • [15] M. A. Huang, Riemann hypothesis and finding roots over finite fields, 17th Annual ACM Symp. on Theory of Computing, 1985, pp. 121-130.
  • [16] H. Iwaniec, On the error term in the linear sieve, Acta Arith. 19 (1971), 1-30. MR 0296043 (45:5104)
  • [17] -, On the problem of Jacobsthal, Demonstratio Math. 11 (1978), 225-231. MR 499895 (80h:10053)
  • [18] A. A. Karacuba, Character sums and primitive roots in finite fields, Soviet. Math. Dokl. 9 (1968), 755-757.
  • [19] J. C. Lagarias, H. L. Montgomery, and A. M. Odlyzko, A bound for the least prime ideal in the Chebotarev density theorem, Invent. Math. 54 (1979), 271-296. MR 553223 (81b:12013)
  • [20] H. W. Lenstra, Finding isomorphisms between finite fields, Math. Comp. 56 (1991), 329-347. MR 1052099 (91d:11151)
  • [21] R. Lidl and H. Niederreiter, Finite fields, Addison-Wesley, 1983. MR 746963 (86c:11106)
  • [22] H. L. Montgomery, Topics in multiplicative number theory, Lecture Notes in Math., vol. 227, Springer-Verlag, 1971. MR 0337847 (49:2616)
  • [23] L. Rónyai, Factoring polynomials over finite fields, J. Algorithms 9 (1988), 391-400. MR 955147 (89k:11124)
  • [24] -, Factoring polynomials modulo special primes, Combinatorica (2) 9 (1989), 199-206. MR 1030373 (90k:11161)
  • [25] -, Galois groups and factoring polynomials over finite fields, 30th Annual Symp. on Foundations of Computer Science, 1989, pp. 99-104.
  • [26] I. A. Semaev, Construction of irreducible polynomials over finite fields with linearly independent roots, Mat. Sb. 135 (1988), 520-532; English transl., Math. USSR-Sb. 63 (1989), no. 2, 507-519. MR 942137 (89i:11135)
  • [27] V. Shoup, Smoothness and factoring polynomials over finite fields, Inform. Process. Lett. 38 (1991), 39-42. MR 1103697 (92f:11178)
  • [28] -, New algorithms for finding irreducible polynomials over finite fields, Math. Comp. 54 (1990), 435-447. MR 993933 (90j:11135)
  • [29] -, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), 261-267. MR 1049276 (91f:11088)
  • [30] I. E. Shparlinsky, On primitive elements in finite fields and on elliptic curves, Mat. Sb. 181 (1990), 1196-1206. (Russian) MR 1085150 (91m:11108)
  • [31] J. von zur Gathen, Factoring polynomials and primitive elements for special primes, Theoret. Comput. Sci. 52 (1987), 77-89. MR 918114 (89a:11126)
  • [32] Y. Wang, On the least primitive root of a prime, Scientia Sinica 10 (1961), 1-14. MR 0130848 (24:A702)
  • [33] A. Weil, Basic number theory, 3rd ed., Springer-Verlag, 1974. MR 0427267 (55:302)

Similar Articles

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

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


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1992-1106981-9
Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society