Comments on search procedures for primitive roots

Bach, Eric

doi:10.1090/S0025-5718-97-00890-9

Comments on search procedures for primitive roots
HTML articles powered by AMS MathViewer

by Eric Bach PDF

Math. Comp. 66 (1997), 1719-1727

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

C. J. Everett Jr., Annihilator ideals and representation iteration for abstract rings, Duke Math. J. 5 (1939), 623–627. MR 13
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.
Eric Bach, Analytic methods in the analysis and design of number-theoretic algorithms, ACM Distinguished Dissertations, MIT Press, Cambridge, MA, 1985. MR 807772
Eric Bach and Lorenz Huelsbergen, Statistical evidence for small generating sets, Math. Comp. 61 (1993), no. 203, 69–82. MR 1195432, DOI 10.1090/S0025-5718-1993-1195432-5
Eric Bach, Improved approximations for Euler products, Number theory (Halifax, NS, 1994) CMS Conf. Proc., vol. 15, Amer. Math. Soc., Providence, RI, 1995, pp. 13–28. MR 1353917, DOI 10.1016/0009-2614(95)01161-4
Daniel L. Wenger, Canonical root vectors of $\textrm {SU}_{n}$, J. Mathematical Phys. 8 (1967), 131–135. MR 206149, DOI 10.1063/1.1705090
A. Cunningham, Solution to problem 14327, Math. Questions Educ. Times 73 (1900), 45–47.
A. E. Ingham, The distribution of prime numbers, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1990. Reprint of the 1932 original; With a foreword by R. C. Vaughan. MR 1074573
T. Itoh, How to recognize a primitive root modulo a prime, unpublished manuscript, 1989.
E. Landau, Über den Verlauf der zahlentheoretischen Funktion $\varphi (x)$, Arch. Math. Phys. 5 (1903), 92–103.
Hugh L. Montgomery, Topics in multiplicative number theory, Lecture Notes in Mathematics, Vol. 227, Springer-Verlag, Berlin-New York, 1971. MR 0337847, DOI 10.1007/BFb0060851
Leo Murata, On the magnitude of the least prime primitive root, J. Number Theory 37 (1991), no. 1, 47–66. MR 1089789, DOI 10.1016/S0022-314X(05)80024-1
Carl Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, Discrete algorithms and complexity (Kyoto, 1986) Perspect. Comput., vol. 15, Academic Press, Boston, MA, 1987, pp. 119–143. MR 910929
Guy 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 premiers de $n$, Acta Arith. 42 (1983), no. 4, 367–389 (French). MR 736719, DOI 10.4064/aa-42-4-367-389
Jeffrey Shallit, On the worst case of three algorithms for computing the Jacobi symbol, J. Symbolic Comput. 10 (1990), no. 6, 593–610. MR 1087981, DOI 10.1016/S0747-7171(08)80160-5
Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385
Victor Shoup, Searching for primitive roots in finite fields, Math. Comp. 58 (1992), no. 197, 369–380. MR 1106981, DOI 10.1090/S0025-5718-1992-1106981-9
Igor Shparlinski, On finding primitive roots in finite fields, Theoret. Comput. Sci. 157 (1996), no. 2, 273–275. MR 1389773, DOI 10.1016/0304-3975(95)00164-6
Yuan Wang, On the least primitive root of a prime, Acta Math. Sinica 9 (1959), 432–441 (Chinese). MR 113827
A. E. Western and J. C. P. Miller, Tables of indices and primitive roots, Royal Society Mathematical Tables, Vol. 9, Published for the Royal Society at the Cambridge University Press, London 1968. MR 0246488