Engineering/Mathematics/Abstract algebra
Abelian Groups and Cyclic Structure
One set of axioms covers integer addition, modular multiplication, points on an elliptic curve and the units of a finite field. Proving a theorem once at the level of groups means it holds in all of them — which is why cryptographic protocols are specified over abstract groups rather than over specific number systems.
- Structural theory
- Abstract algebra
- Protocol foundation
- ≈17 min read
- Feeds discrete logarithms
01
Executive summary
An abelian group is a set with an associative, commutative operation, an identity and inverses. The definition is deliberately thin, and its value is exactly that thinness: results proved from it apply verbatim to ℤ under addition, to ℤ*n under multiplication, to the additive group of a vector space, and to elliptic curve groups.
Three tools do most of the work. Cosets partition a group by a subgroup and give Lagrange's theorem. Homomorphisms transport structure, and their kernels and images give the isomorphism theorems. Cyclic groups classify the one-generator case completely, and the structure theorem reduces the finite abelian case to that classification.
Written additively or multiplicatively depending on context; the theory is identical.
aH for a subgroup H; all cosets have the same size, so |H| divides |G|.
Preserves the operation. Kernel measures failure of injectivity, image measures reach.
Finite abelian groups are products of cyclic prime-power pieces — nothing else occurs.
02
Definitions and worked examples
Notation: multiplicative unless the group is naturally additive.
Abelian group
A set G with a binary operation satisfying: closure; associativity (ab)c = a(bc); commutativity ab = ba; an identity 1 with 1a = a; and an inverse a−1 for every a. The order |G| is the cardinality; the order of an element is the least k > 0 with ak = 1, or infinite if no such k exists.
| Group | Operation | Order | Where it appears |
|---|---|---|---|
| ℤ | addition | infinite | Cyclic, generated by 1; the model for all infinite cyclic groups |
| ℤn | addition mod n | n | Cyclic of every finite order; the canonical finite cyclic group |
| ℤ*n | multiplication mod n | φ(n) | RSA, Fermat and Euler theorems, primality testing |
| ℤ*p | multiplication mod prime p | p − 1 | Cyclic; the classical Diffie–Hellman setting |
| F*q | field multiplication | q − 1 | Always cyclic — a key structural fact about finite fields |
| E(Fq) | chord-and-tangent addition | ≈ q | Elliptic curve cryptography; abelian but not generally cyclic |
| (V, +) | vector addition | |F|dim | The additive group underlying any vector space |
Additive versus multiplicative notation
The same theorem reads ak = 1 multiplicatively and ka = 0 additively. Discrete logarithm protocols are usually written multiplicatively for ℤ*p and additively for elliptic curves, so gx becomes xP. Nothing mathematical changes, and confusing the two is a frequent source of error when porting protocol descriptions.
03
Subgroups, cosets and Lagrange's theorem
A subgroup is a non-empty subset closed under the operation and inverses. For each a ∈ G the powers ⟨a⟩ = {ak : k ∈ ℤ} form the cyclic subgroup generated by a, of order ord(a).
Lagrange's theorem
For a finite group G and subgroup H, the cosets aH partition G into blocks of equal size |H|. Hence |H| divides |G|, the index [G:H] = |G|/|H| is an integer, and applying this to H = ⟨a⟩ gives ord(a) ∣ |G| and a|G| = 1 for every a.
Euler's theorem
Apply a|G| = 1 to G = ℤ*n, order φ(n).
Prime order rigidity
If |G| is prime, the only subgroups are trivial, so every non-identity element generates. Prime-order groups are the preferred setting for discrete-log protocols.
Small-subgroup attacks
If |G| has small factors, an adversary can confine a key exchange to a small subgroup. Order validation of received points or elements is mandatory.
In an abelian group every subgroup is normal, so the quotient G/H — the set of cosets under (aH)(bH) = abH — is always a group. This is the construction behind ℤn = ℤ/nℤ and behind every quotient ring later in the library.
Contents04
Homomorphisms and the isomorphism theorems
Homomorphism, kernel, image
A map ρ : G → G′ with ρ(ab) = ρ(a)ρ(b). Then ρ(1) = 1 and ρ(a−1) = ρ(a)−1 follow. The kernel ker ρ = {a : ρ(a) = 1} is a subgroup of G, the image is a subgroup of G′, and ρ is injective exactly when the kernel is trivial.
First isomorphism theorem
Counting version for finite groups: |G| = |ker ρ| · |img ρ|. This single identity replaces a large number of ad hoc counting arguments.
| Map | Kernel | What the theorem says |
|---|---|---|
| ℤ → ℤn, a ↦ [a] | nℤ | ℤ/nℤ ≅ ℤn — the definition of modular arithmetic |
| ℤ*n → ℤ*n, a ↦ ak | elements of order dividing k | The k-th power map is a bijection iff gcd(k, |G|) = 1 — the RSA correctness argument |
| ℤ*p → {±1}, Legendre symbol | the quadratic residues | Exactly half the non-zero residues are squares |
| ℤ*mn → ℤ*m × ℤ*n | trivial | CRT as a group isomorphism; gives multiplicativity of φ |
| ℤ → G, k ↦ ak | ord(a)·ℤ | ⟨a⟩ ≅ ℤord(a) — every cyclic group is a quotient of ℤ |
05
Cyclic groups
The completely understood case — and the one protocols are built in.
Classification and subgroup lattice
A cyclic group is one of the form ⟨g⟩. Infinite cyclic groups are isomorphic to ℤ; a cyclic group of order m is isomorphic to ℤm. In G = ⟨g⟩ of order m:
- ord(gk) = m/gcd(k,m), so gk generates G exactly when gcd(k,m) = 1;
- there is exactly one subgroup of order d for each d ∣ m, namely ⟨gm/d⟩, and no others;
- the number of elements of order exactly d is φ(d), and the number of generators is φ(m).
The multiplicative group of a field is cyclic
Any finite subgroup of the multiplicative group of a field is cyclic. Proof sketch: in a group of order m that is not cyclic, some d ∣ m would admit more than d solutions of xd = 1, contradicting the fact that a degree-d polynomial over a field has at most d roots. This is why ℤ*p and F*q always have generators.
Protocol reading
Discrete-log security depends on the subgroup lattice. In ℤ*p of order p−1, every small factor of p−1 is a small subgroup that Pohlig–Hellman can exploit. Protocols therefore work in a prime-order subgroup of order q ∣ p−1 with q large, and validate that received elements satisfy hq = 1.
06
The structure theorem for finite abelian groups
Primary decomposition and invariant factors
Equivalently G ≅ ℤm₁ × ⋯ × ℤms with m1 ∣ m2 ∣ ⋯ ∣ ms. The largest invariant factor ms is the exponent of the group — the smallest e with ae = 1 for all a — and G is cyclic exactly when s = 1.
| Group | Decomposition | Exponent | Cyclic? |
|---|---|---|---|
| ℤ*15 | ℤ2 × ℤ4 | 4 | No — order 8, exponent 4 |
| ℤ*2e, e ≥ 3 | ℤ2 × ℤ2e−2 | 2e−2 | No |
| ℤ*p | ℤp−1 | p−1 | Yes |
| ℤ*pq | ℤp−1 × ℤq−1 | lcm(p−1,q−1) = λ(n) | No |
| (Fq, +), q = pk | ℤpk | p | Only if k = 1 |
The exponent column is exactly Carmichael's λ for the modular cases — the theorem explains where that function comes from.
Why the exponent is the operational quantity
Correctness of exponent arithmetic depends on the exponent of the group, not its order. RSA works with d ≡ e−1 (mod λ(n)) because λ(n) is the exponent of ℤ*n; using φ(n) is correct but wasteful. Reading the structure theorem correctly is what tells you the difference.
07
Computational questions in abstract groups
Once a protocol is written over an abstract group, its security rests on which computational problems are hard in that group. The same abstract problem can be trivial in one realisation and intractable in another.
| Problem | In (ℤn, +) | In ℤ*p | In E(Fq) |
|---|---|---|---|
| Group operation | trivial | one modular multiplication | a few field operations |
| Exponentiation gx | one multiplication | O(log x) squarings and multiplications | O(log x) point operations |
| Discrete logarithm | trivial — solve xa ≡ b with extended gcd | subexponential (index calculus) | believed exponential, O(√q) best known generic |
| Order computation | trivial | needs the factorization of p−1 | point counting via Schoof–Elkies–Atkin |
This table is the reason elliptic curve groups give equivalent security at much smaller parameter sizes: no subexponential attack is known for well-chosen curves.
- Generic algorithms — those using only the group operation — need Ω(√q) operations for discrete logs in a group of prime order q, a proved lower bound in the generic model. Baby-step giant-step and Pollard rho attain it.
- Non-generic structure is what makes index calculus possible in ℤ*p: elements are integers and can be factored over a base of small primes. Elliptic curve points admit no comparable notion.
- Validation matters. Accepting an unvalidated group element allows an attacker to move the computation into a small subgroup or off the curve entirely. Check the order and membership of every received element.
08
Quick reference and FAQ
| Fact | Statement |
|---|---|
| Lagrange | H ≤ G finite ⇒ |H| ∣ |G| |
| Element order | ord(a) ∣ |G| and a|G| = 1 |
| Power order | ord(ak) = ord(a)/gcd(k, ord(a)) |
| Generators | A cyclic group of order m has φ(m) generators |
| Subgroups of cyclic | Exactly one of each order dividing m |
| First isomorphism | G/ker ρ ≅ img ρ |
| Field units | Any finite subgroup of F* is cyclic |
| Structure | Finite abelian ⇒ product of cyclic prime-power groups |
Why restrict to abelian groups?
How do I tell whether a group is cyclic without listing elements?
What is the practical impact of the structure theorem?
Is a group of prime order always safe for discrete-log protocols?
10
References and further reading
- V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapter 8.
- S. Lang, Algebra, 3rd ed., Springer, 2002 — Chapter I for groups and the structure theorem.
- D. S. Dummit and R. M. Foote, Abstract Algebra, 3rd ed., Wiley, 2004 — Chapters 1–5.
- V. Shoup, 'Lower bounds for discrete logarithms and related problems', EUROCRYPT '97, LNCS 1233, 256–266 — the generic group lower bound.
KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: abelian-groups-and-cyclic-structureReview cycle: annual