Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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 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
Email: bach@cs.wisc.edu

DOI: http://dx.doi.org/10.1090/S0025-5718-97-00890-9
PII: S 0025-5718(97)00890-9
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