Primitive root calculator

How it works

A primitive root modulo $n$ is a number $g$ whose powers produce every residue coprime to $n$; its order is $\varphi(n)$ and $\mathbb Z_n^*$ is cyclic. Gauss proved that primitive roots exist exactly for $n = 1, 2, 4$, $p^k$ and $2p^k$ with $p$ an odd prime. For other $n$, such as $8$ or $15$, the largest order is $\lambda(n) < \varphi(n)$.

To test a candidate $g$ one does not compute all its powers. If the order of $g$ were a proper divisor of $\varphi(n)$, it would divide $\varphi(n)/q$ for some prime $q \mid \varphi(n)$. So $g$ is a primitive root exactly when $g^{\varphi(n)/q} \not\equiv 1$ for every such $q$. Primitive roots are common (there are $\varphi(\varphi(n))$ of them), so trying $2, 3, 5, \dots$ succeeds quickly; the hard part is factoring $\varphi(n)$.

Diffie and Hellman’s original key exchange uses a primitive root $g$ modulo a large prime $p$. Once one generator $g$ is known, all others are the powers $g^k$ with $\gcd(k, \varphi(n)) = 1$.