# Verify that $x$ is a primitive root modulo $n$

I have a question.

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

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?

• $\mathbb{Z}/(n\mathbb{Z})^*$ is not always a cyclic group, so what does your question really mean? – Jack D'Aurizio Mar 20 '17 at 21:31
• $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$. – Jack D'Aurizio Mar 20 '17 at 21:32
• 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. – Jack D'Aurizio Mar 20 '17 at 21:33
• There is no faster way? – Aurelio Mar 20 '17 at 21:35
• And you have to perform a test for every prime divisor, not every divisor. – Jack D'Aurizio Mar 20 '17 at 21:43