Verifying generators of a cyclic group

Question

Is there is a faster way to verify that a number is a generator of $Z_n^{*}$ other than taking the power of the number multiple times?

For example, I want to know if 11 is a generator of $Z_{23}^{*}$, is there a more efficient approach?

Answer 1

An element $u \in \mathbb{Z}_n^{\times}$ is a generator if and only if $\varphi(n)$ is the smallest positive integer $k$ such that $u^k = 1$. To verify this condition it suffices to verify that $u^{\frac{\varphi(n)}{p}} \neq 1$ for all prime divisors $p$ of $\varphi(n)$, and you can do this using binary exponentiation. The fewer prime divisors $\varphi(n)$ has, the more time this saves.

When $n = 23$ we have $\varphi(n) = 22$, so it suffices to verify that

$$11^2 \not \equiv 1 \bmod 23, 11^{11} \not \equiv 1 \bmod 23.$$

The first inequality is easy to verify and the second can be done using binary exponentiation as follows.

$$11^2 \equiv 121 \equiv 6 \bmod 23$$ $$11^4 \equiv 6^2 \equiv 36 \equiv 13 \bmod 23$$ $$11^8 \equiv 13^2 \equiv 169 \equiv 8 \bmod 23$$ $$11^{11} \equiv 11^{8+2+1} \equiv 8 \cdot 6 \cdot 11 \equiv 528 \equiv 68 \equiv -1 \bmod 23.$$

So $11$ is a generator.

Edit: Note that $11^{11}$ must have been equivalent to either $1$ or $-1$ depending on whether or not $11$ is a quadratic residue or not $\bmod 23$ - this is Euler's criterion - so you could also have done this second computation using quadratic reciprocity, which is faster:

$$11^{\frac{23-1}{2}} \equiv \left( \frac{11}{23} \right) \equiv - \left( \frac{23}{11} \right) \equiv - \left( \frac{1}{11} \right) \equiv -1 \bmod 23.$$