##
**Searching for primitive roots in finite fields.**
*(English)*
Zbl 0747.11060

An earlier version of this paper appeared in the 22nd Annual ACM Symposium on Theory of Computing, 1990, pp. 546-554.

In a finite field \(GF(p^ n)\) (with \(p\) prime and \(n\geq 1\)) a nonzero element is called a primitive root if it generates the multiplicative group of units. It is well known that the density of primitive roots in \(GF(p^ n)\) is great enough so that the simple method of choosig a small number of elements in \(GF(p^ n)\) at random is a probabilistic polynomial-time search procedure for primitive roots. In the present paper the author considers the problem of how to deterministically generate in polynomial-time a subset of \(GF(p^ n)\) that contains a primitive root. Three results are presented. First, the author solves this problem in the case that \(p=n^{O(1)}\). Second, he shows under the assumption of the Extended Riemann Hypothesis (ERH) that there is a deterministic polynomial-time search procedure for primitive roots in \(GF(p^ 2)\). Third, he gives a quantitative improvement of a theorem of Wang on the least primitive root for \(GF(p)\), assuming ERH.

In a finite field \(GF(p^ n)\) (with \(p\) prime and \(n\geq 1\)) a nonzero element is called a primitive root if it generates the multiplicative group of units. It is well known that the density of primitive roots in \(GF(p^ n)\) is great enough so that the simple method of choosig a small number of elements in \(GF(p^ n)\) at random is a probabilistic polynomial-time search procedure for primitive roots. In the present paper the author considers the problem of how to deterministically generate in polynomial-time a subset of \(GF(p^ n)\) that contains a primitive root. Three results are presented. First, the author solves this problem in the case that \(p=n^{O(1)}\). Second, he shows under the assumption of the Extended Riemann Hypothesis (ERH) that there is a deterministic polynomial-time search procedure for primitive roots in \(GF(p^ 2)\). Third, he gives a quantitative improvement of a theorem of Wang on the least primitive root for \(GF(p)\), assuming ERH.

Reviewer: J.Hinz (Marburg)

### MSC:

11T30 | Structure theory for finite fields and commutative rings (number-theoretic aspects) |

11Y40 | Algebraic number theory computations |

11Y16 | Number-theoretic algorithms; complexity |

68Q25 | Analysis of algorithms and problem complexity |

### Keywords:

finite field; primitive root; multiplicative group of units; Extended Riemann Hypothesis; deterministic polynomial-time search procedure; theorem of Wang; least primitive root
Full Text:
DOI

### References:

[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 non residue, Ann. of Math. (2) 55 (1952), 65 – 72. · Zbl 0046.04006 |

[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] | A. I. Borevich and I. R. Shafarevich, Number theory, Translated from the Russian by Newcomb Greenleaf. Pure and Applied Mathematics, Vol. 20, Academic Press, New York-London, 1966. · Zbl 0145.04902 |

[5] | D. A. Burgess, Character sums and primitive roots in finite fields, Proc. London Math. Soc. (3) 17 (1967), 11 – 25. · Zbl 0166.05105 |

[6] | L. Carlitz, Distribution of primitive roots in a finite field, Quart. J. Math., Oxford Ser. (2) 4 (1953), 4 – 10. · Zbl 0052.03803 |

[7] | Algebraic number theory, Proceedings of an instructional conference organized by the London Mathematical Society (a NATO Advanced Study Institute) with the support of the International Mathematical Union. Edited by J. W. S. Cassels and A. Fröhlich, Academic Press, London; Thompson Book Co., Inc., Washington, D.C., 1967. |

[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) · Zbl 0561.12010 |

[9] | H. Davenport, On primitive roots in finite fields, Quart. J. Math. (Oxford) 8 (1937), 308-312. · Zbl 0018.10901 |

[10] | H. Davenport and D. J. Lewis, Character sums and primitive roots in finite fields, Rend. Circ. Mat. Palermo (2) 12 (1963), 129 – 136. · Zbl 0119.04302 |

[11] | 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. · Zbl 0779.11060 |

[12] | John B. Friedlander, A note on primitive roots in finite fields, Mathematika 19 (1972), 112 – 114. · Zbl 0246.10004 |

[13] | G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., Oxford Univ. Press, 1984. · Zbl 0020.29201 |

[14] | Jürgen G. Hinz, Character sums and primitive roots in algebraic number fields, Monatsh. Math. 95 (1983), no. 4, 275 – 286. · Zbl 0508.10025 |

[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. · Zbl 0222.10050 |

[17] | Henryk Iwaniec, On the problem of Jacobsthal, Demonstratio Math. 11 (1978), no. 1, 225 – 231. · Zbl 0378.10029 |

[18] | A. A. Karacuba, Character sums and primitive roots in finite fields, Soviet. Math. Dokl. 9 (1968), 755-757. · Zbl 0182.37501 |

[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), no. 3, 271 – 296. · Zbl 0401.12014 |

[20] | H. W. Lenstra Jr., Finding isomorphisms between finite fields, Math. Comp. 56 (1991), no. 193, 329 – 347. · Zbl 0709.11072 |

[21] | Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. · Zbl 0864.11063 |

[22] | Hugh L. Montgomery, Topics in multiplicative number theory, Lecture Notes in Mathematics, Vol. 227, Springer-Verlag, Berlin-New York, 1971. · Zbl 0216.03501 |

[23] | Lajos Rónyai, Factoring polynomials over finite fields, J. Algorithms 9 (1988), no. 3, 391 – 400. · Zbl 0651.12013 |

[24] | L. Rónyai, Factoring polynomials modulo special primes, Combinatorica 9 (1989), no. 2, 199 – 206. · Zbl 0694.68039 |

[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 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. |

[27] | Victor Shoup, Smoothness and factoring polynomials over finite fields, Inform. Process. Lett. 38 (1991), no. 1, 39 – 42. · Zbl 0744.11068 |

[28] | Victor Shoup, New algorithms for finding irreducible polynomials over finite fields, Math. Comp. 54 (1990), no. 189, 435 – 447. · Zbl 0712.11077 |

[29] | Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), no. 5, 261 – 267. · Zbl 0696.68072 |

[30] | 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. USSR-Sb. 71 (1992), no. 1, 41 – 50. · Zbl 0719.11085 |

[31] | Joachim von zur Gathen, Factoring polynomials and primitive elements for special primes, Theoret. Comput. Sci. 52 (1987), no. 1-2, 77 – 89. · Zbl 0633.12009 |

[32] | Yuan Wang, On the least primitive root of a prime, Sci. Sinica 10 (1961), 1 – 14. · Zbl 0103.02801 |

[33] | André Weil, Basic number theory, 3rd ed., Springer-Verlag, New York-Berlin, 1974. Die Grundlehren der Mathematischen Wissenschaften, Band 144. · Zbl 0326.12001 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.