Groups

Groups

1. What a Group Is (Four Axioms)

A group $(G, \circ)$ is a set with an operation satisfying closure, associativity, identity, inverse:

1. Closure: $a, b \in G \Rightarrow a \circ b \in G$.
2. Associativity: $(a \circ b) \circ c = a \circ (b \circ c)$.
3. Identity: $\exists e: a \circ e = e \circ a = a$.
4. Inverse: $\forall a \; \exists a^{-1}: a \circ a^{-1} = e$.

Abelian (commutative) if additionally $a \circ b = b \circ a$. Finite if $|G| = n$ (order); cyclic if some $g$ generates all: $G = \{g^0, g^1, \dots, g^{n-1}\}$. Cryptography lives in finite abelian/cyclic groups: $(\mathbb{Z}_n, +)$, $(\mathbb{Z}_p^*, \times)$, elliptic-curve groups.

2. Worked Examples (Check All Four)

Set + op	Identity	Inverse	Group?
$(\mathbb{Z}, +)$	$0$	$-a$	✓ infinite abelian
$(\mathbb{Z}_7, +)$ i.e. $\{0..6\}$ mod 7	$0$	$7 - a$	✓ cyclic, generator 1, 3, 5...
$(\mathbb{Z}_7^*, \times) = \{1..6\}$ mod 7	$1$	$a^{-1}$: $2^{-1} = 4$ since $2 \times 4 = 8 \equiv 1$	✓ cyclic order 6, generator 3: $3^1..3^6 = 3,2,6,4,5,1$
$(\mathbb{Z}_8^*, \times) = \{1,3,5,7\}$	$1$	$3^{-1} = 3$ ($9 \equiv 1$), $5^{-1} = 5$, $7^{-1} = 7$	✓ abelian order 4, NOT cyclic (no element order 4)
$(\mathbb{Z}_8, \times)$ incl. evens	—	2,4,6 have none	✗ not a group (no inverses)

Generator check: $3$ mod 7: $3^1 = 3$, $3^2 = 2$, $3^3 = 6$, $3^4 = 4$, $3^5 = 5$, $3^6 = 1$ — all six nonzero residues ✓. Element order divides group order (Lagrange): orders in $\mathbb{Z}_7^*$ divide 6 ($1, 2, 3, 6$).

3. Key Theorems for Cryptography

• Lagrange: $|H| \mid |G|$ for subgroup $H$; hence $a^{|G|} = e$ for all $a$ — the engine behind Fermat ($a^{p-1} \equiv 1$), Euler ($a^{\phi(n)} \equiv 1$), RSA correctness (Module 5).
• Cyclic $\Rightarrow$ discrete-log setting: $y = g^x$ easy, $x = \log_g y$ hard (Module 5 Topic 6: Diffie–Hellman, ElGamal, DSA live here).
• Subgroup structure: $\mathbb{Z}_p^*$ has exactly one subgroup per divisor of $p-1$ — small-subgroup attacks confine keys there if validation skipped (use safe primes / cofactor clearing).

4. Why Groups Open the Algebra Block (Topics 9–12)

Groups need only ONE operation; rings add a second (+, ×), fields add inverses for ×. AES's $GF(2^8)$ (Module 3–4) is a field under $(\oplus, \bullet)$ — its nonzero elements form a cyclic group of order 255 (generator = $x+1$ = 0x03). Every S-box/power computation is group exponentiation.

Exam Points

• Four axioms verbatim + abelian/cyclic definitions — 2-mark opener.
• $\mathbb{Z}_7^*$ generator trace ($3^i = 3,2,6,4,5,1$) and inverse ($2^{-1} = 4$) — standard numerical.
• Non-example $(\mathbb{Z}_8, \times)$ with reason (evens lack inverses).
• Lagrange $a^{|G|} = e$ → Fermat/Euler/RSA bridge line.