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 Free Access

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?)

Similar Articles

Retrieve articles in Mathematics of Computation 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