MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $p$ be prime. Consider $\Bbb Z_{p}$, the cyclic multiplicative group.

Is it possible to choose a generator $c$ as small as $O(\log(p))$? (wiki shows $c$ as small as $O(\log^{6}(p))$ is possible under GRH

share|cite|improve this question
I don't understand: The wikipedia article you cite seems to give the state of the art on this question (and seems to indicate that there is a good chance that the answer to the question is "no". – Igor Rivin Jul 13 '13 at 14:04
Hi Igor: It seems there are improvements.… – Turbo Jul 13 '13 at 15:15
Note that Bach does NOT look at the smallest residue, so this is not an improvement as far as your question is concerned. – Igor Rivin Jul 13 '13 at 15:25
But he seems to have a conjectureon page 1725 relating to $\exp(\gamma)$? Plus in the last few lines he seems to suggest $O(\log{p}\log\log{p})$ may be possible? Is this unrelated? – Turbo Jul 13 '13 at 15:30
The results mentioned in the Wikipedia article suggest that the question on $O(\log p)$ bounds has been asked a long time ago, and the negative results are to show that you certainly can't do better (after all, why not $O(\sqrt(\log p))$? A priori, no reason). Notice that the best (conditional) estimates on quadratic non-residues are $O(\log^2 p),$ so this is a lower bound on how well you can do with current technology. – Igor Rivin Jul 13 '13 at 15:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.