01d-cyclic-groups-generators.ipynb

Kernel: SageMath 10

Cyclic Groups and Generators

Module 01d | Modular Arithmetic and Groups

Take one element, multiply it by itself over and over. Sometimes you get the entire group back. That's the idea behind most of modern cryptography.

Where we left off. In 01c we verified that $(\mathbb{Z}/7\mathbb{Z}^*, \times)$ is a group: you can multiply any two elements and get another element, there's an identity (1), and every element has an inverse. Now let's see what happens when we take one element and keep multiplying it by itself.

Objectives

By the end of this notebook you will be able to:

1. Explain why repeated multiplication in a finite group must cycle back to 1

2. Compute the order of an element (the length of its cycle)

3. Determine whether an element is a generator (its cycle is the whole group)

4. Define cyclic group and identify examples (and non-examples)

5. Count generators using Euler's totient function

6. Connect generators to the discrete logarithm problem

One Element, Repeated Multiplication

Pick the element 3 in $(\mathbb{Z}/7\mathbb{Z}^*, \times)$. Compute $3^1, 3^2, 3^3, \ldots$ and watch what happens.

R = Zmod(7)
g = R(3)

print('Successive powers of 3 in (Z/7Z*, x):\n')
val = R(1)
for k in range(1, 8):
    val = val * g
    hit_one = '  <-- back to 1!' if val == R(1) else ''
    print(f'  3^{k} = {val}{hit_one}')

After 6 steps we're back to 1, and the cycle would repeat: $3^7 = 3^1$, $3^8 = 3^2$, and so on.

Before hitting 1, the powers visited $\{3, 2, 6, 4, 5, 1\}$, which is the ENTIRE group $\{1, 2, 3, 4, 5, 6\}$. Every element appeared exactly once.

Now try element 2:

R = Zmod(7)
g = R(2)

print('Successive powers of 2 in (Z/7Z*, x):\n')
val = R(1)
for k in range(1, 8):
    val = val * g
    hit_one = '  <-- back to 1!' if val == R(1) else ''
    print(f'  2^{k} = {val}{hit_one}')

Element 2 hit 1 after only 3 steps: $2 \to 4 \to 1$. Then the cycle repeats: $2^4 = 2$, $2^5 = 4$, $2^6 = 1$. It only ever touches $\{1, 2, 4\}$, never reaching 3, 5, or 6.

Why must it cycle at all? The group has 6 elements. Each multiplication gives another element in the group (closure!). After 6 multiplications, you've produced 6 elements but there are only 6 possibilities. By the pigeonhole principle, some value must repeat. Once any value repeats, the whole pattern cycles. And it always cycles back to 1 (we'll see why shortly).

Every Element Traces a Cycle

Let's compute the power cycle for every element in $(\mathbb{Z}/7\mathbb{Z}^*, \times)$.

R = Zmod(7)
units = [R(g) for g in R.list_of_elements_of_multiplicative_group()]

print('Power cycles in (Z/7Z*, x):\n')
for g in units:
    # Compute g, g^2, g^3, ... until we return to 1
    cycle = []
    val = R(1)
    for k in range(1, 7):
        val = val * g
        cycle.append(int(val))
        if val == R(1):
            break
    all_six = len(cycle) == 6
    tag = '  <-- hits all 6!' if all_six else ''
    print(f'  g={g}:  {cycle}  (cycle length {len(cycle)}){tag}')

Some elements have long cycles (3 and 5 reach all 6 elements), others have short ones (6 cycles in just 2 steps). Let's visualize these cycles.

R = Zmod(7)
units = [R(g) for g in R.list_of_elements_of_multiplicative_group()]

# Place elements 1-6 on a circle
n = 6
positions = {int(units[i]): (cos(2*pi*i/n - pi/2), sin(2*pi*i/n - pi/2)) for i in range(n)}

# Pick 3 interesting generators/non-generators to show
show_elements = [R(3), R(2), R(6)]
colors = ['steelblue', 'orangered', 'forestgreen']
titles = ['g=3 (cycle length 6)', 'g=2 (cycle length 3)', 'g=6 (cycle length 2)']

plots = []
for g, color, title in zip(show_elements, colors, titles):
    P = Graphics()
    # Draw all nodes
    for elem, (ex, ey) in positions.items():
        P += circle((ex, ey), 0.12, fill=True, facecolor='lightgray',
                    edgecolor='gray', thickness=1, zorder=3)
        P += text(str(elem), (ex, ey), fontsize=10, color='black', zorder=4)

    # Draw cycle arrows
    val = R(1)
    for k in range(6):
        prev = int(val * g^0) if k == 0 else int(val)
        val = val * g if k > 0 else g
        if k == 0:
            val = g
            prev_elem = 1  # start from 1 conceptually: 1 -> g
        else:
            prev_elem = prev
        curr_elem = int(val)
        # Highlight visited nodes
        cx, cy = positions[curr_elem]
        P += circle((cx, cy), 0.12, fill=True, facecolor=color,
                    edgecolor='white', thickness=1.5, zorder=5)
        P += text(str(curr_elem), (cx, cy), fontsize=10, fontweight='bold',
                  color='white', zorder=6)
        # Arrow from previous to current
        px, py = positions[prev_elem]
        dx, dy = cx - px, cy - py
        dist = sqrt(dx^2 + dy^2)
        if dist > 0.01:
            shrink = 0.15
            P += arrow((px + shrink*dx/dist, py + shrink*dy/dist),
                       (cx - shrink*dx/dist, cy - shrink*dy/dist),
                       color=color, width=1.5, arrowsize=3, zorder=2)
        if val == R(1):
            break

    # Also highlight 1 (the starting/ending point)
    ox, oy = positions[1]
    P += circle((ox, oy), 0.12, fill=True, facecolor=color,
                edgecolor='white', thickness=1.5, zorder=5)
    P += text('1', (ox, oy), fontsize=10, fontweight='bold',
              color='white', zorder=6)

    P.axes(False)
    P.set_aspect_ratio(1)
    plots.append(P)

graphics_array(plots, 1, 3).show(figsize=[14, 4])
print('Left: g=3 visits all 6 elements (generator).  Middle: g=2 visits only 3.  Right: g=6 visits only 2.')

Order = Cycle Length

The length of an element's cycle has a name: its order.

Definition. The order of $g$, written $\text{ord}(g)$, is the smallest positive integer $k$ such that $g^k = 1$.

In other words, the order is how many times you need to multiply $g$ by itself before getting back to the identity. SageMath computes this with .multiplicative_order().

R = Zmod(7)
units = [R(g) for g in R.list_of_elements_of_multiplicative_group()]
group_order = euler_phi(7)  # 6

print(f'Orders of elements in (Z/7Z*, x)   [|G| = {group_order}]\n')

for g in units:
    order = g.multiplicative_order()
    tag = '  <-- generator' if order == group_order else ''
    print(f'  ord({g}) = {order}{tag}')

print(f'\nNotice something? Every order divides {group_order}.')
print(f'Divisors of {group_order}: {divisors(group_order)}')
print(f'And every order in the table is one of those divisors.')

Why must the order divide the group size? Here's the intuition.

We know $g^6 = 1$ for every $g$ in a group of size 6 (this is a consequence of Lagrange's theorem, which we'll prove in 01e). If $\text{ord}(g) = k$, then the powers cycle with period $k$. For $g^6$ to equal 1, the period $k$ must divide 6. If $k$ were 4, then $g^4 = 1$ and $g^6 = g^{4+2} = g^2 \neq 1$ (unless $g^2 = 1$ too, which means $k$ was really 2 or 1, not 4).

Checkpoint. Predict the possible orders in $(\mathbb{Z}/11\mathbb{Z}^*)$ before computing. The group has $11 - 1 = 10$ elements. What numbers divide 10?

# Verify your predictions: orders in (Z/11Z)*
R = Zmod(11)
units = [R(g) for g in R.list_of_elements_of_multiplicative_group()]
group_order = euler_phi(11)  # 10

print(f'Divisors of {group_order}: {divisors(group_order)}')
print(f'So the only possible orders are: {divisors(group_order)}\n')

observed_orders = set()
for g in units:
    order = g.multiplicative_order()
    observed_orders.add(order)
    tag = '  <-- generator' if order == group_order else ''
    print(f'  ord({g}) = {order}{tag}')

print(f'\nObserved orders: {sorted(observed_orders)}')
print(f'All divide {group_order}? {all(group_order % d == 0 for d in observed_orders)}')

Generators: Elements That Reach Everything

An element whose cycle covers the entire group has a special name.

Definition. An element $g$ is a generator of $G$ if $\text{ord}(g) = |G|$. Equivalently, $\{g^1, g^2, \ldots, g^{|G|}\} = G$.

If $g$ is a generator, then every element in the group can be written as $g^k$ for some unique $k$. This is like having a complete address system: every group element has a unique "exponent address."

# The "address table" for generator g=3 in (Z/7Z*, x)
R = Zmod(7)
g = R(3)

print(f'Generator g = {g} in (Z/7Z*, x)')
print(f'Every element = g^k for a unique k:\n')

for k in range(1, 7):
    print(f'  {g}^{k} = {g^k}')

print(f'\nThe exponent k is the "address" of element g^k.')
print(f'Going forward (k -> g^k) is easy: just multiply.')
print(f'Going backward (g^k -> k) is the discrete logarithm problem.')

Cyclic Groups

A group that has at least one generator is called a cyclic group. The name comes from the picture we just saw: a generator's powers cycle through every element in the group and then loop back to 1.

$(\mathbb{Z}/7\mathbb{Z}^*, \times)$ is cyclic because 3 is a generator (so is 5). One generator is enough for the group to earn the name "cyclic," even though most elements are not generators.

This is a big structural claim. It says the entire group can be "unrolled" from a single element. Every element is just a power of the generator. The group has no hidden corners, no elements that live outside some generator's reach.

Cyclic groups are everywhere

In fact, you already know the most natural cyclic group: $(\mathbb{Z}/n\mathbb{Z}, +)$, the integers mod $n$ under addition. The element 1 generates everything, because $1 + 1 + \cdots + 1$ ($k$ times) gives you $k \bmod n$, and that hits every element $\{0, 1, 2, \ldots, n-1\}$.

# (Z/12Z, +) is cyclic: generated by 1
R = Zmod(12)
g = R(1)

print('(Z/12Z, +) is cyclic, generated by 1:\n')
elements = []
val = R(0)
for k in range(1, 13):
    val = val + g
    elements.append(int(val))
    print(f'  1 + 1 + ... ({k} times) = {k} * 1 = {val}')

print(f'\nElements reached: {sorted(elements)}')
print(f'All of Z/12Z? {sorted(elements) == list(range(12))}')
print(f'\nSo (Z/12Z, +) is cyclic. One element (1) reaches everything.')

Not all groups are cyclic

Here's a natural question: is every group cyclic? No. Some groups have no generator at all. No single element can reach everything.

Consider $(\mathbb{Z}/15\mathbb{Z}^*, \times)$, the units mod 15. This group has $\varphi(15) = 8$ elements. If it were cyclic, some element would have order 8. Let's check.

# (Z/15Z)* is NOT cyclic: no element has order 8
R = Zmod(15)
units = [R(g) for g in R.list_of_elements_of_multiplicative_group()]
group_order = euler_phi(15)  # 8

print(f'(Z/15Z)* has {group_order} elements: {[int(u) for u in units]}')
print(f'If cyclic, some element would have order {group_order}.\n')

max_order = 0
for g in units:
    # Show the actual powers: g, g^2, g^3, ... until g^k = 1
    cycle = []
    val = R(1)
    for k in range(1, group_order + 1):
        val = val * g
        cycle.append(int(val))
        if val == R(1):
            break
    order = len(cycle)
    powers_str = ' -> '.join(str(c) for c in cycle)
    tag = '  <-- generator!' if order == group_order else ''
    print(f'  g={int(g):>2}: {int(g)}^1..{int(g)}^{order} = [{powers_str}]  (order {order}){tag}')
    max_order = max(max_order, order)

print(f'\nLargest order found: {max_order}')
print(f'Group size: {group_order}')
print(f'\nNo element has order {group_order}, so (Z/15Z)* is NOT cyclic.')
print(f'Every element cycles back to 1 too quickly. Nobody reaches all 8 elements.')

Why cyclic matters for cryptography

Cryptography needs cyclic groups. Here's why:

• If the group is cyclic with generator $g$, every element has a unique exponent: $h = g^k$. This exponent is the discrete logarithm, and finding it is the hard problem that secures Diffie-Hellman and related schemes.

• If the group is not cyclic, there's no single generator, so you can't set up a clean DLP. The algebraic structure is messier and harder to build protocols on.

That's why $(\mathbb{Z}/p\mathbb{Z}^*, \times)$ for prime $p$ is the classic choice: it's always cyclic (a theorem we'll take on faith for now). Elliptic curve groups used in practice are also cyclic.

Key fact. $(\mathbb{Z}/n\mathbb{Z}^*, \times)$ is cyclic if and only if $n = 1, 2, 4, p^k$, or $2p^k$ for an odd prime $p$. In particular, it's cyclic for every prime $n$, which is the case we care about most. We'll explore non-cyclic unit groups more in 01e.

The Discrete Logarithm Problem

If $g$ generates $G$, and someone gives you $h = g^k$, finding $k$ is called the discrete logarithm problem (DLP). It's called a "logarithm" because it undoes exponentiation, just like $\log$ undoes $\exp$ for real numbers.

For our tiny group, brute force works fine:

# Demo: solve 3^x = 5 (mod 7) by brute force
R = Zmod(7)
g = R(3)
target = R(5)

print(f'Discrete logarithm: find x such that {g}^x = {target} in (Z/7Z*, x)')
print(f'Brute-force search:\n')

for x in range(1, 7):
    val = g^x
    marker = '  <-- found!' if val == target else ''
    print(f'  {g}^{x} = {val}{marker}')

# SageMath can also compute this directly
x_solution = discrete_log(target, g)
print(f'\nSageMath confirms: log_{g}({target}) = {x_solution}')
print(f'\nThis was trivial for |G| = 6.')
print(f'For |G| ~ 2^256, brute force would take longer than the age of the universe.')
print(f'That computational gap is what makes Diffie-Hellman, ElGamal, and DSA secure.')

Why is the DLP hard? Computing $g^k$ is fast (you can use repeated squaring, which takes roughly $\log_2(k)$ steps). But going backward, finding $k$ from $g^k$, has no known shortcut for general groups. Exponentiation in a finite group scrambles the relationship between $k$ and $g^k$ so thoroughly that the only known approach for generic groups is to try exponents one by one.

This asymmetry (easy forward, hard backward) is the foundation of most public-key cryptography.

Counting Generators

Not every element is a generator. How many generators does $(\mathbb{Z}/p\mathbb{Z}^*, \times)$ have?

An element $g$ is a generator when $\text{ord}(g) = p - 1$. It turns out the count is exactly $\varphi(p - 1)$, where $\varphi$ is Euler's totient function.

Why? If $g$ is one generator, then $g^k$ is also a generator exactly when $\gcd(k, p-1) = 1$ (because $\text{ord}(g^k) = (p-1) / \gcd(k, p-1)$). The number of $k$ values with $\gcd(k, p-1) = 1$ is, by definition, $\varphi(p-1)$.

# Verify: number of generators = phi(p-1) for several primes
for p in [7, 11, 13, 23]:
    R = Zmod(p)
    units = [R(g) for g in R.list_of_elements_of_multiplicative_group()]
    group_order = p - 1
    phi_val = euler_phi(group_order)
    generators = [g for g in units if g.multiplicative_order() == group_order]

    match = '\u2713' if len(generators) == phi_val else '\u2717'
    print(f'p = {p}:  |G| = {group_order},  phi({group_order}) = {phi_val},  generators found: {len(generators)}  {match}')
    print(f'  generators: {[int(g) for g in generators]}\n')

Common mistake. "The order of an element is its numerical value." No! In $(\mathbb{Z}/7\mathbb{Z}^*, \times)$, element 2 has order 3, and element 3 has order 6. The order is the length of the cycle when you keep multiplying. It's a structural property, not a numerical one.

A Taste of Diffie-Hellman

Here's a sketch of how generators power real cryptography. Alice and Bob agree publicly on a prime $p$ and a generator $g$ of $(\mathbb{Z}/p\mathbb{Z}^*, \times)$.

# Tiny Diffie-Hellman demo
p = 23
R = Zmod(p)
g = R(5)  # 5 is a generator of (Z/23Z)*
print(f'Public parameters: p = {p}, g = {g}')
print(f'(ord({g}) = {g.multiplicative_order()} = p-1, so {g} is a generator)\n')

# Alice picks a secret exponent
a = 6  # Alice's secret
A = g^a  # Alice sends this publicly
print(f'Alice: secret a = {a},  sends g^a = {g}^{a} = {A}')

# Bob picks a secret exponent
b = 15  # Bob's secret
B = g^b  # Bob sends this publicly
print(f'Bob:   secret b = {b},  sends g^b = {g}^{b} = {B}')

# Both compute the shared secret
alice_key = B^a  # Alice computes (g^b)^a = g^(ab)
bob_key = A^b    # Bob computes (g^a)^b = g^(ab)
print(f'\nAlice computes B^a = {B}^{a} = {alice_key}')
print(f'Bob   computes A^b = {A}^{b} = {bob_key}')
print(f'\nSame key? {alice_key == bob_key}')
print(f'\nEve sees g={g}, A={A}, B={B} but needs to find a or b.')
print(f'That requires solving the discrete log problem.')

Exercises

Exercise 1 (Worked)

List all powers of 2 in $(\mathbb{Z}/13\mathbb{Z}^*)$. Determine $\text{ord}(2)$. Is 2 a generator?

# Exercise 1: Worked solution
R = Zmod(13)
g = R(2)
group_order = euler_phi(13)  # 12

print(f'Powers of {g} in (Z/13Z*, x):\n')

for k in range(1, group_order + 1):
    print(f'  {g}^{k} = {g^k}')

order = g.multiplicative_order()
print(f'\nord({g}) = {order}')
print(f'|G| = {group_order}')
print(f'\nIs {g} a generator? ord({g}) == |G|? {order} == {group_order}? {order == group_order}')
print(f'YES, 2 generates all of (Z/13Z)* because its order equals the group order.')

Exercise 2 (Guided)

Find all generators of $(\mathbb{Z}/11\mathbb{Z}^*)$. Verify the count matches $\varphi(10) = 4$.

# Exercise 2: Find generators of (Z/11Z)*
R = Zmod(11)
group_order = euler_phi(11)  # 10

# TODO: for each unit in R, compute its multiplicative_order()
# TODO: mark elements where order equals group_order as generators
# TODO: count them and compare with euler_phi(10)

Exercise 3 (Independent)

In $(\mathbb{Z}/31\mathbb{Z}^*)$, how many generators exist? Find them all. Then pick one generator $g$ and verify that every element in $\{1, 2, \ldots, 30\}$ can be written as $g^k$ for exactly one $k \in \{1, \ldots, 30\}$. What is $\log_g(17)$?

# Exercise 3: Your code here

Summary

Concept	Key idea
Power cycle	Repeated multiplication $g, g^2, g^3, \ldots$ must eventually return to 1
Order	$\text{ord}(g)$ = length of the cycle = smallest $k$ with $g^k = 1$
Divisibility	$\text{ord}(g)$ always divides $
Generator	$g$ is a generator iff $\text{ord}(g) =
Cyclic group	A group with at least one generator. All of $(\mathbb{Z}/p\mathbb{Z}^*, \times)$ are cyclic.
Non-cyclic	Some groups (like $(\mathbb{Z}/15\mathbb{Z}^*)$) have no generator at all
Generator count	Exactly $\varphi(
DLP	Finding $k$ from $g^k$ is the discrete logarithm problem, computationally hard for large groups

The punchline: a cyclic group can be "unrolled" from a single generator. Every element gets a unique exponent "address." Computing addresses is easy (multiply), but reversing them is hard (discrete log). That asymmetry is the foundation of Diffie-Hellman, ElGamal, and DSA.

Next: Subgroups and Lagrange's Theorem. Non-generators create smaller groups inside the big one, and their sizes are brutally constrained by divisibility.