What is a cyclic group, what is a generator (primitive element), and why are cyclic groups important for cryptography?
A cyclic group can be generated entirely by a single element (the generator/primitive element). Diffie-Hellman and ECC rely on cyclic groups.
* A generator's successive powers visit every element: 2 sweeps ℤ₉* as 2→4→8→7→5→1 before returning to the start, which is exactly what makes the group cyclic. *
Definition: A group $G$ is cyclic if there exists an element $g \in G$ such that every element of $G$ can be written as $g^k$ (or $k \cdot g$ for additive groups). Such $g$ is called a generator or primitive element.
Key property: If the group order $|G| = p$ is prime, then the group is ALWAYS cyclic.
Properties of cyclic groups with prime order $p$:
- The group is cyclic
- The group is Abelian (commutative)
- Up to isomorphism, there's only one such group
- Every element (except the neutral element) has order $p$
- Every element (except the neutral element) is a generator
- The number of generators is $\varphi(p) = p - 1$
For Diffie-Hellman: Uses the group $\langle \mathbb{Z}_p^*, \cdot \mod p \rangle$ with order $p - 1$ (even, so NOT prime). The group is still cyclic but not all elements are generators — you must choose a generator carefully.
For Elliptic Curves: Groups can be cyclic with prime order, non-prime order, or even non-cyclic — all three types occur. When the order is prime, every non-identity point is a generator.
Tip: The reason cyclic groups matter: the discrete logarithm problem ($g^x = h$, find $x$) is hard in large cyclic groups — this hardness IS the security of DH and ECC.
Go deeper:
Cyclic group (Wikipedia) — generators, structure and why crypto loves them.
Cyclic Groups (Socratica) — generators and cyclic structure, visually.