Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Comments on search procedures
for primitive roots

Author: Eric Bach
Journal: Math. Comp. 66 (1997), 1719-1727
MSC (1991): Primary 11Y16; Secondary 11A07, 11M26
MathSciNet review: 1433261
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $p$ be an odd prime. Assuming the Extended Riemann Hypothesis, we show how to construct $O( {(\log p)^{4} (\log \log p)^{-3} } )$ residues modulo $p$, one of which must be a primitive root, in deterministic polynomial time. Granting some well-known character sum bounds, the proof is elementary, leading to an explicit algorithm.

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

  • 1. N. C. Ankeny, The least quadratic non residue, Ann. Math. 55 (1952), 65-72. MR 13:538c
  • 2. E. Bach, Fast algorithms under the extended Riemann hypothesis: a concrete estimate, Proc. 14th Ann. ACM Symp. Theor. Comput., ACM, New York, 1982, pp. 290-295.
  • 3. E. Bach, Analytic Methods in the Analysis and Design of Number-theoretic Algorithms, MIT Press, Cambridge, 1985. MR 87i:11185
  • 4. E. Bach and L. Huelsbergen, Statistical evidence for small generating sets, Math. Comp. 61 (1993), 69-82. MR 93k:11089
  • 5. E. Bach, Improved approximations for Euler products, in Number Theory: Fourth Conference of the Canadian Number Theory Association (K. Dichler, ed.), AMS, 1995, pp. 13-28. MR 96i:11124
  • 6. M. B. Barban, A. I. Vinogradov, and B. V. Levin, Limit laws for functions of the class $H$ of I. P. Kubilius which are defined on a set of ``shifted'' primes, Litovskii Mat. Sb. 5 (1965), 5-8. (Russian) MR 34:5974
  • 7. A. Cunningham, Solution to problem 14327, Math. Questions Educ. Times 73 (1900), 45-47.
  • 8. A. E. Ingham, The Distribution of Prime Numbers, Cambridge Univ. Press, 1932. MR 91f:11064
  • 9. T. Itoh, How to recognize a primitive root modulo a prime, unpublished manuscript, 1989.
  • 10. E. Landau, Über den Verlauf der zahlentheoretischen Funktion $\varphi (x)$, Arch. Math. Phys. 5 (1903), 92-103.
  • 11. H. L. Montgomery, Topics in Multiplicative Number Theory, Springer-Verlag, New York, 1971. MR 49:2616
  • 12. L. Murata, On the magnitude of the least primitive root, J. Number Theory 37 (1991), 47-66. MR 91j:11082
  • 13. C. Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, in Discrete Algorithms and Complexity (D. S. Johnson, et al., eds.), Academic Press, 1987, pp. 119-143. MR 88m:11109
  • 14. G. Robin, Estimation de la fonction de Tchebychef $\Theta $ sur le $k$-ième nombre premier et grandes valeurs de la fonction $\omega (n)$, nombre de diviseurs de $n$, Acta Arith 42 (1983), 367-389. MR 85j:11109
  • 15. J. O. Shallit, On the worst case of three algorithms for computing the Jacobi symbol, J. Symbol. Comput. 10 (1990), 593-610. MR 91m:11112
  • 16. D. Shanks, Class number, a theory of factorization, and genera., Proc. Symposia Pure Math. 20 (1971), 415-440. MR 47:4932
  • 17. V. Shoup, Searching for primitive roots in finite fields, Math. Comp. 58 (1992), 369-380. MR 92e:11140
  • 18. I. Shparlinski, On finding primitive roots in finite fields, Theoret. Comput. Sci. 157 (1996), 273-275. MR 97a:11203
  • 19. Y. Wang, On the least primitive root of a prime, Acta Math. Sinica 9 (1959), 432-441 (Chinese), English translation in Sci. Sinica 10 (1961), 1-14. MR 22:4659; MR 24:A702
  • 20. A. E. Western and J. C. P. Miller, Tables of Indices and Primitive Roots, Cambridge University Press, 1968 (Royal Society Math. Tables vol. 9). MR 39:7792

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11Y16, 11A07, 11M26

Retrieve articles in all journals with MSC (1991): 11Y16, 11A07, 11M26

Additional Information

Eric Bach
Affiliation: Computer Sciences Department, University of Wisconsin, 1210 W. Dayton St., Madison, Wisconsin 53706

Keywords: Primes, generators, extended Riemann hypothesis
Received by editor(s): April 13, 1994
Received by editor(s) in revised form: September 13, 1994, and July 12, 1996
Article copyright: © Copyright 1997 by the author

American Mathematical Society