Let \(\langle \mathbb{Z}^\star_p, \ast \rangle\) be a cyclic group where \(p\) is a prime number. Recall that a prime number is any number which is only divisible by \(1\) and itself,
\[ 1|p \wedge p|p \,,\]and a cyclic group is a tuple containing a finite set, \(S\), and a binary operation, \(\ast\), written as \(\langle S, \ast \rangle\) which together satisfy the following properties:
If \(\alpha, \beta \in S\), then \(\alpha \ast \beta \in S\).
If \(\alpha, \beta, \gamma \in S\) then \(\alpha \ast (\beta \ast \gamma = (\alpha \ast \beta) \ast \gamma\).
If \(\alpha \in S\), then \(1 \ast \alpha = \alpha\).
If \(\alpha \in S\), then there is \(\beta \in S\) such that \(\alpha \ast \beta = 1\).
Furthermore, the set \(\mathbb{Z}^\star_p\) is defined as,
\[ \mathbb{Z}^\star_p = \{ k \in \mathbb{Z}_p | \gcd(k, p) = 1 \} \,.\]Recall as well as that for any \(a\) and \(b\) where \(\gcd(a, b) = 1\), \(a\) and \(b\) are co-prime (or relatively prime) meaning that there is no common factor other than \(1\).
The set \(\mathbb{Z}^\star_p\) can be formed using an element, \(\alpha\), which we call a generator.
To find the generator, we use the following approach. Since \(p\) is prime, we know that \(p^\prime = p-1\) will be composite.
We start off by factoring \(p^\prime\). By the Fundamental Theorem of Arithmetic, every composite number can be written as a unique product of powers of primes,
\[ p^\prime = \prod_{i=1}^N q_i^{\mu_i}\,, \]where \(q\) are primes and \(\mu \in \mathbb{Z}^+\).
We can skip \(1\) since \(1\) will never be a generator, but for every other element in \(\mathbb{Z}^\star_p\), the numbers from \(2\) to \(p^\prime\), we check to see that,
\[ \alpha^{\frac{p^\prime}{q_i}} \not\equiv 1 \pmod{p} \,.\]If \((4)\) is true for all \(q_i\), then \(\alpha\) is a generator.