Example for Cyclic Groups and Selecting a generator

A better example (because the log problem is hard, which is not the case for the additive groups): the multiplicative group of $\mathbb{Z}_{p} = \{ 1,2,\ldots,p-1\}$ under multiplication. Say for $p=11$, we have $G = \{1,2,\ldots,10\}$, and not all elements are generators, e.g. $1$ is not. Let's try 2: $$2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 16 = 5, 2^5 = 10 = -1, $$ $$ 2^6 = -2 = 9, 2^7 = -4 = 7, 2^8 = -8 = 3, 2^9 = 6, 2^{10} = 12 = 1$$ again. So 2 is a generator, and the discrete log for 3 equals 8, as $2^8 = 3 \mod 11$ etc. For large primes, this gets harder and harder (we cannot make a table like this anymore). In general, you need to work a bit to find a generator, but they always exist. E.g. see the wikipedia page on this, e.g if we choose $p = 2q+1$, where $q$ is also prime (a "safe prime" in cryptography) then $g$ is a multiplicative primitive in $\mathbb{Z}_p$ iff $g^{\frac{p-1}{2}} = -1 \mod p$, and this is easy to test (fast modular exponentiation algorithms exist). As there are $\phi(\phi(n)) = \phi(2q) = q-1$ many primitive elements, a picking a few random numbers and testing them will give a primitive element. In practice, a set of fixed primes, and corresponding generators, have already been fixed by a committee, like in the TLS/SSL standard, so that a user need not generate them himself, but can just say "use group x from that standard"; but like I said, it's not that hard for a PC to find primitive elements.

In fact if you take the group $(\mathbb{Z}_{p},+)$ for a prime number $p$, then every element is a generator.

• Take $G= \{a^{q}=e, a ,a^{2}, \cdots, a^{q-1}\}$. Now $|G|=q$ and $G = <a>$, which means that $G$ is generated by $a$.