I have a question.

How can we the quickest to test whether $x$ is a primitive root modulo $n$?

On the Wikipedia page I found information about a possible algorithm.

This algorithm, however, must know all the divisors.

I found the question: Here, but I did not understand much (I need test number $x$).

Can you think of something?

Can this be done in a polynomial time?

  • $\begingroup$ $\mathbb{Z}/(n\mathbb{Z})^*$ is not always a cyclic group, so what does your question really mean? $\endgroup$ – Jack D'Aurizio Mar 20 '17 at 21:31
  • 1
    $\begingroup$ $x\in\mathbb{Z}/(p\mathbb{Z})^*$ is a generator iff $$x^{\frac{p-1}{q}}\neq 1\pmod{p}$$ for every prime divisor $q$ of $p-1$. $\endgroup$ – Jack D'Aurizio Mar 20 '17 at 21:32
  • $\begingroup$ And assuming GRH, there is a generator for $\mathbb{Z}/(p\mathbb{Z})^*$ in the first $C\log^2(p)$ elements for any prime $p$ large enough. $\endgroup$ – Jack D'Aurizio Mar 20 '17 at 21:33
  • $\begingroup$ There is no faster way? $\endgroup$ – Aurelio Mar 20 '17 at 21:35
  • 1
    $\begingroup$ And you have to perform a test for every prime divisor, not every divisor. $\endgroup$ – Jack D'Aurizio Mar 20 '17 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.