Mathematics of Computation

Author(s): Eric Bach.
Journal: Math. Comp. 66 (1997), 1719-1727.
MSC (1991): Primary 11Y16; Secondary 11A07, 11M26
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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.

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 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 -ième nombre premier et grandes valeurs de la fonction $\omega (n)$ , nombre de diviseurs de , 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

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

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS