COMMENTS ON SEARCH PROCEDURES FOR PRIMITIVE ROOTS

Let p be an odd prime. Assuming the Extended Riemann Hypothesis, we sh ow how to construct O((logp)(4)(loglogp)(-3)) residues module p, one o f which must be a primitive root, in deterministic polynomial time. Gr anting some well-known character sum bounds, the proof is elementary, leading to an explicit algorithm.