Searching for primitive roots in finite fields
HTML articles powered by AMS MathViewer
 by Victor Shoup PDF
 Math. Comp. 58 (1992), 369380 Request permission
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

L. M. Adleman and H. W. Lenstra, Jr., Finding irreducible polynomials over finite fields, 18th Annual ACM Sympos. on Theory of Computing, 1986, pp. 350355.
 N. C. Ankeny, The least quadratic non residue, Ann. of Math. (2) 55 (1952), 65–72. MR 45159, DOI 10.2307/1969420 E. Bach and J. von zur Gathen, Deterministic factorization of polynomials over special finite fields, Technical Report 799, Department of Computer Science, University of WisconsinMadison, 1988.
 A. I. Borevich and I. R. Shafarevich, Number theory, Pure and Applied Mathematics, Vol. 20, Academic Press, New YorkLondon, 1966. Translated from the Russian by Newcomb Greenleaf. MR 0195803
 D. A. Burgess, Character sums and primitive roots in finite fields, Proc. London Math. Soc. (3) 17 (1967), 11–25. MR 219516, DOI 10.1112/plms/s317.1.11
 L. Carlitz, Distribution of primitive roots in a finite field, Quart. J. Math. Oxford Ser. (2) 4 (1953), 4–10. MR 56028, DOI 10.1093/qmath/4.1.4
 J. W. S. Cassels and A. Fröhlich (eds.), Algebraic number theory, Academic Press, London; Thompson Book Co., Inc., Washington, D.C., 1967. MR 0215665 A. L. Chistov, Polynomial time construction of a finite field, Abstracts of Lectures at 7th AllUnion Conference in Mathematical Logic, Novosibirsk, 1984, p. 196. (Russian) H. Davenport, On primitive roots in finite fields, Quart. J. Math. (Oxford) 8 (1937), 308312.
 H. Davenport and D. J. Lewis, Character sums and primitive roots in finite fields, Rend. Circ. Mat. Palermo (2) 12 (1963), 129–136. MR 167482, DOI 10.1007/BF02843959
 S. A. Evdokimov, Factorization of a solvable polynomial over finite fields and the generalized Riemann hypothesis, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 176 (1989), no. Teor. Slozhn. Vychisl. 4, 104–117, 153 (Russian, with English summary); English transl., J. Soviet Math. 59 (1992), no. 3, 842–849. MR 1023599, DOI 10.1007/BF01104107
 John B. Friedlander, A note on primitive roots in finite fields, Mathematika 19 (1972), 112–114. MR 316360, DOI 10.1112/S0025579300005027 G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., Oxford Univ. Press, 1984.
 Jürgen G. Hinz, Character sums and primitive roots in algebraic number fields, Monatsh. Math. 95 (1983), no. 4, 275–286. MR 718064, DOI 10.1007/BF01547799 M. A. Huang, Riemann hypothesis and finding roots over finite fields, 17th Annual ACM Symp. on Theory of Computing, 1985, pp. 121130.
 H. Iwaniec, On the error term in the linear sieve, Acta Arith. 19 (1971), 1–30. MR 296043, DOI 10.4064/aa191130
 Henryk Iwaniec, On the problem of Jacobsthal, Demonstratio Math. 11 (1978), no. 1, 225–231. MR 499895 A. A. Karacuba, Character sums and primitive roots in finite fields, Soviet. Math. Dokl. 9 (1968), 755757.
 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), no. 3, 271–296. MR 553223, DOI 10.1007/BF01390234
 H. W. Lenstra Jr., Finding isomorphisms between finite fields, Math. Comp. 56 (1991), no. 193, 329–347. MR 1052099, DOI 10.1090/S00255718199110520992
 Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, AddisonWesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
 Hugh L. Montgomery, Topics in multiplicative number theory, Lecture Notes in Mathematics, Vol. 227, SpringerVerlag, BerlinNew York, 1971. MR 0337847
 Lajos Rónyai, Factoring polynomials over finite fields, J. Algorithms 9 (1988), no. 3, 391–400. MR 955147, DOI 10.1016/01966774(88)900296
 L. Rónyai, Factoring polynomials modulo special primes, Combinatorica 9 (1989), no. 2, 199–206. MR 1030373, DOI 10.1007/BF02124680 —, Galois groups and factoring polynomials over finite fields, 30th Annual Symp. on Foundations of Computer Science, 1989, pp. 99104.
 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. USSRSb. 63 (1989), no. 2, 507–519. MR 942137, DOI 10.1070/SM1989v063n02ABEH003288
 Victor Shoup, Smoothness and factoring polynomials over finite fields, Inform. Process. Lett. 38 (1991), no. 1, 39–42. MR 1103697, DOI 10.1016/00200190(91)90212Z
 Victor Shoup, New algorithms for finding irreducible polynomials over finite fields, Math. Comp. 54 (1990), no. 189, 435–447. MR 993933, DOI 10.1090/S00255718199009939330
 Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), no. 5, 261–267. MR 1049276, DOI 10.1016/00200190(90)901954
 I. E. Shparlinskiĭ, On primitive elements in finite fields and on elliptic curves, Mat. Sb. 181 (1990), no. 9, 1196–1206 (Russian); English transl., Math. USSRSb. 71 (1992), no. 1, 41–50. MR 1085150, DOI 10.1070/SM1992v071n01ABEH001389
 Joachim von zur Gathen, Factoring polynomials and primitive elements for special primes, Theoret. Comput. Sci. 52 (1987), no. 12, 77–89. MR 918114, DOI 10.1016/03043975(87)900818
 Yuan Wang, On the least primitive root of a prime, Sci. Sinica 10 (1961), 1–14. MR 130848
 André Weil, Basic number theory, 3rd ed., Die Grundlehren der mathematischen Wissenschaften, Band 144, SpringerVerlag, New YorkBerlin, 1974. MR 0427267
Additional Information
 © Copyright 1992 American Mathematical Society
 Journal: Math. Comp. 58 (1992), 369380
 MSC: Primary 11T06; Secondary 11Y16
 DOI: https://doi.org/10.1090/S00255718199211069819
 MathSciNet review: 1106981