Comments on search procedures for primitive roots
HTML articles powered by AMS MathViewer
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
Additional Information
- Eric Bach
- Affiliation: Computer Sciences Department, University of Wisconsin, 1210 W. Dayton St., Madison, Wisconsin 53706
- Email: bach@cs.wisc.edu
- Received by editor(s): April 13, 1994
- Received by editor(s) in revised form: September 13, 1994, and July 12, 1996
- © Copyright 1997 by the author
- Journal: Math. Comp. 66 (1997), 1719-1727
- MSC (1991): Primary 11Y16; Secondary 11A07, 11M26
- DOI: https://doi.org/10.1090/S0025-5718-97-00890-9
- MathSciNet review: 1433261