Engineering / Mathematics — Abelian Groups
Cyclic Groups
Cyclic groups, their generators, subgroup structure, and the criterion for the units modulo n to be cyclic.
Executive summary
A cyclic group is generated by a single element. Its structure is completely determined by its order, and its subgroup lattice mirrors the divisor lattice of that order.
The group of units modulo n is cyclic only for particular n, and knowing when is essential to discrete-log parameter selection.
Learning objectives
- Characterise the generators of a cyclic group.
- Describe the subgroup lattice of a cyclic group.
- State the criterion for Z_n* to be cyclic.
01Generators
Cyclic group
A group G with an element g such that G = ⟨g⟩. Such a g is a generator, or a primitive root in the modular setting.
Counting generators
A cyclic group of order n has exactly φ(n) generators. The element g^k generates if and only if gcd(k, n) = 1.
So generators are plentiful. In a cyclic group of order n, the proportion of elements that generate is φ(n)/n, which is bounded below by roughly 1/(6 ln ln n) — small but never negligible, so random search finds one quickly.
02Subgroup structure
Subgroups of a cyclic group
A cyclic group of order n has exactly one subgroup of order d for each divisor d of n, and no others. Each such subgroup is itself cyclic.
The subgroup of order d is generated by g^{n/d} and consists of exactly the elements whose order divides d — equivalently, the solutions of x^d = e.
| Group | Order | Subgroup orders |
|---|---|---|
| Z_7* | 6 | 1, 2, 3, 6 |
| Z_11* | 10 | 1, 2, 5, 10 |
| Z_23* | 22 | 1, 2, 11, 22 |
| Subgroup of prime order q | q | 1, q only |
The last row is the design target for cryptography: a prime-order group has no proper non-trivial subgroups, so no decomposition attack is available.
03When is Z_n* cyclic?
Primitive root theorem
Z_n* is cyclic exactly when n = 1, 2, 4, p^k or 2p^k for an odd prime p.
In particular Z_p* is cyclic for every prime p, which is the case that matters for Diffie–Hellman. For a general composite modulus the group is a product of cyclic groups and typically not cyclic itself.
The same theorem in the finite field setting is unconditional and stronger: F_q* is cyclic for every prime power q, with no exceptional cases. This is one reason finite fields are a cleaner setting than composite moduli.
04Frequently asked questions
Is there an efficient way to find a primitive root?
Random search with verification, using the factorisation of p − 1 to test candidate orders. No unconditional deterministic polynomial-time method is known, though one exists under the generalised Riemann hypothesis.
Why does Z_n* fail to be cyclic for most n?
Because the Chinese remainder theorem decomposes it into a product over prime powers, and a product of cyclic groups is cyclic only when the orders are pairwise coprime. For most n that condition fails.
Does a cyclic group of composite order weaken security?
Yes, through Pohlig-Hellman. The subgroup of each divisor order permits a partial discrete logarithm, and the results reassemble by Chinese remaindering. Prime-order subgroups avoid this entirely.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 202-208.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.