Basic number theory

Multiplicative inverses modulo $m$

The multiplicative group of integers modulo $m$ is defined as: $$\begin{array}{}\text{(1)}& {\mathbb{Z}}_m^{\ast }=\{a|gcd(a,m)=1\}\end{array}$$ But why? This is because Euler’s theorem says that: $$\begin{array}{}\text{(2)}& gcd(a,m)=1\Rightarrow a^{\varphi (m)}=1\end{array}$$ This in turn, implies that every element in ${\mathbb{Z}}_m^{\ast }$ has an inverse, since: $$\begin{array}{}\text{(3)}& a\cdot a^{\varphi (m)-1}& =1\end{array}$$ Thus, for a prime $p$, all elements in ${\mathbb{Z}}_p^{\ast }=\{1,2,\dots ,p-1\}$ have inverses. Specifically, the inverse of $a\in {\mathbb{Z}}_p^{\ast }$ is $a^{p-2}$.

Finding primitive roots mod $p$

Suppose you have ${\mathbb{Z}}_p^{\ast }=\{1,2,3,\dots ,p-2,p-1\}$: i.e., the group of integers mod $p$, where $p$ is a prime.

How do you find a generator $g$ for it? (a.k.a., primitive roots) $$\begin{array}{}\text{(4)}& ⟨g⟩\stackrel{\mathsf{def}}{=}\{g^0,g^1,g^2,\dots ,g^{p-2}\}={\mathbb{Z}}_p^{\ast }\end{array}$$

First, you factor its order $p-1$ as $$\begin{array}{}\text{(5)}& p-1=\prod _i{q}_i^{e_i},\text{where}{q}_i\text{are primes}\end{array}$$

Second, you simply brute-force: you pick a potential candidate generator $g$ and ensure: $$\begin{array}{}\text{(6)}& \mathrm{\forall }i,g^{\frac{p-1}{q_i}}\ne 1(\mathrm{mod}p)\end{array}$$ If all these checks pass, then $g$ is a generator.