1
$\begingroup$

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 http://en.wikipedia.org/wiki/Primitive_root_modulo_n#Upper_bounds)

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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". $\endgroup$
    – Igor Rivin
    Commented Jul 13, 2013 at 14:04
  • $\begingroup$ Hi Igor: It seems there are improvements. ams.org/journals/mcom/1997-66-220/S0025-5718-97-00890-9/… $\endgroup$
    – Turbo
    Commented Jul 13, 2013 at 15:15
  • 1
    $\begingroup$ Note that Bach does NOT look at the smallest residue, so this is not an improvement as far as your question is concerned. $\endgroup$
    – Igor Rivin
    Commented Jul 13, 2013 at 15:25
  • $\begingroup$ 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? $\endgroup$
    – Turbo
    Commented Jul 13, 2013 at 15:30
  • 1
    $\begingroup$ 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. $\endgroup$
    – Igor Rivin
    Commented Jul 13, 2013 at 15:33

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .