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.