Into which three types can every finite group be sorted by cyclicity, and which types do Diffie-Hellman and elliptic curves rely on?
Every finite group falls into one of three types: (1) prime order — always cyclic; (2) non-prime order but still cyclic; (3) non-prime order and non-cyclic. DH is forced into type (2); elliptic curves can reach type (1).
* Every finite group is one of three types. Diffie-Hellman is stuck in type 2 (so it carves out a prime-order subgroup); elliptic curves can reach type 1 directly. *
| Type | Group order | Cyclic? | Example |
|---|---|---|---|
| (1) | prime | always cyclic | any group of order 29 |
| (2) | not prime | cyclic | $\langle \mathbb{Z}_p^*, \cdot \bmod p \rangle$ — order $p-1$ (even) |
| (3) | not prime | not cyclic | $\langle \mathbb{Z}_8^*, \cdot \bmod 8 \rangle$ — order 4 |
Why the split matters: DH and ECC need a cyclic group for the discrete-logarithm problem to have clean structure, so type (3) is unusable.
- Diffie-Hellman is stuck with type (2): its group $\mathbb{Z}_p^*$ has order $p - 1$, which is even (since $p > 2$) and therefore never prime — so DH must carve out a large prime-order subgroup to work in.
- Elliptic curves can be built with prime order directly (type 1), where every non-identity element is a generator and no subgroup selection is needed — one reason ECC is considered more elegant.
Tip: "Prime order ⇒ cyclic" is a one-way street — a cyclic group need not have prime order ($\mathbb{Z}_9^*$ has order 6 and is cyclic; $\langle \mathbb{Z}_8, + \rangle$ has order 8 and is cyclic).
Go deeper:
Cyclic group (Wikipedia) — when a group is (and isn't) cyclic.