Conjecture: There are constants $c,k$ such that every $(Z/nZ)^*$ is generated by its elements smaller than $k (\log n)^c$.

Where $(Z/nZ)^*$ is the multiplicative group of integers mod $n$. My main question is: How "strong" is this conjecture relative to other unsolved conjectures? How "hard" do experts think this is to prove (or disprove)? Any references, summary of what is currently known, and further reading would definitely be appreciated too.

I think this is interesting on its own, but my particular motivation comes from the Miller–Rabin probabilistic primality testing algorithm. If the above conjecture is true for any constant $c$, then we can "derandomize" Miller–Rabin into a deterministic, polynomial-time algorithm for primality testing (because if $n$ is composite, a set of generators for $(Z/nZ)^*$ must contain a "witness", so we need only check a polynomial-sized set to ensure a correct answer). This would not be a big breakthrough in that sense because we already have the AKS test, but would be interesting.

The Wikipedia page for Miller–Rabin notes that the Generalized Riemann Hypothesis implies the conjecture is true for $c=2,k=2$. But I'm curious if this conjecture seems e.g. as hard as the Riemann Hypothesis, or much weaker.

For those familiar with computational complexity, an interesting conjecture would be that $(Z/nZ)^*$ has a set of generators that is producible in time $poly(\log n)$ (thus also implying it has size $poly(\log n)$). Any generic pseudorandom generator used to prove BPP=P would seem to "almost" prove this—it would say that there exists a small set of generic deterministic inputs that are enough to run Miller–Rabin without all false positives—so if this conjecture is, say, equivalent to RH, then it makes the search for PRGs seem somewhat harder. Any thoughts on this would also be great.


1 Answer 1


This problem seems to lie quite deep. To illustrate this consider the problem of estimating the least quadratic non-residue $\pmod p$ for a prime $p$ -- obviously if the numbers up to some point generate $({\Bbb Z}/p{\Bbb Z})^*$ then they must contain a quadratic non-residue, so this problem should be ``easier." Vinogradov conjectured that the least quadratic non-residue is $\ll p^{\epsilon}$ for any $\epsilon >0$ but this remains unknown. The best known result is that the least quadratic non-residue is $\ll p^{1/(4\sqrt{e})}$, which follows from Burgess's bound on character sums plus a multiplicative trick of Vinogradov. So unconditionally, one should not expect a result better than $n^{1/(4\sqrt{e})+\epsilon}$ for generating all of $({\Bbb Z}/n{\Bbb Z})^*$. And a result of Harman shows that the numbers up to $n^{1/(4\sqrt{e})+\epsilon}$ do in fact generate all of $({\Bbb Z}/n{\Bbb Z})^*$; see Theorem 3 of his paper.

More remarks: To prove a bound of $(\log p)^{A}$ for the least quadratic non-residue seems to require some version of a quasi Riemann hypothesis: no zeros of Dirichlet $L$-functions to the right of $1-1/A$. A precise relation between zero-free regions and the least quadratic non-residue was established first by Rodosskii. One way of thinking about the group generated by the numbers below $y$ in $({\Bbb Z}/n{\Bbb Z})^*$ is to consider the distribution of $y$-smooth numbers below $x$ in arithmetic progressions $\pmod n$ -- this is the focus of Harman's paper referenced already, and for more work in this direction see Soundararajan and Harper. The ideas here would give more relations between zero-free regions and how big $y$ has to be to generate $({\Bbb Z}/n{\Bbb Z})^*$ (along the lines of Rodosskii's work, which you can find referenced there).

  • $\begingroup$ Is the considered conjecture somehow related to the best upper bound one can expect for the smallest $r$ such that both $n-r$ and $n+r$ are primes? $\endgroup$ May 11, 2014 at 12:28
  • $\begingroup$ Thanks very much! The answer is very nice. I'd like to wait to accept for a while longer to see if others have something to add. $\endgroup$
    – usul
    May 11, 2014 at 23:20
  • 1
    $\begingroup$ What do you mean when you saying proving a bound $O((\log p)^A)$ seems to require no zeros in some half-plane ${\rm Re}(s) > 1-1/A$? I looked in Rodosskii's paper at mi.mathnet.ru/eng/izv/v20/i3/p303 and I see no statement about the lack of zeros in ${\rm Re}(s) > 1-1/1A$ following from the least quadratic nonresidue mod $p$ being bounded by a constant multiple of $(\log p)^A$. Did Rodosskii or others prove that an upper bound on the least quadratic nonresidue mod $p$ by a power of $\log p$ implies an upper bound on the real part of nontrivial zeros, and if so then where is it? $\endgroup$
    – KConrad
    Jun 19, 2018 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.