05b-primitive-roots-generators.ipynb

Kernel: SageMath 10.5

Notebook 05b: Primitive Roots and Generators

Module 05. The Discrete Logarithm and Diffie-Hellman

---

Motivating Question. In $\mathbb{Z}/7\mathbb{Z}^*$, the element $g = 3$ generates every nonzero residue: $3^1 = 3, 3^2 = 2, 3^3 = 6, 3^4 = 4, 3^5 = 5, 3^6 = 1$. But $g = 2$ only generates $\{1, 2, 4\}$, half the group. Why the difference? Which elements are generators, how many are there, and how do we find them efficiently? This matters because the DLP is only meaningful when $g$ generates a large (sub)group.

---

Prerequisites. You should be comfortable with:

• Cyclic groups and element order (Module 01)

• Euler's totient function $\varphi(n)$ (Module 04)

• The discrete logarithm problem (notebook 05a)

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

1. Define the order of an element and compute it.

2. Define primitive root (generator) and explain why primitive roots exist for primes.

3. Test whether a given element is a primitive root using the factorisation of $p - 1$.

4. Count and find all primitive roots modulo $p$.

5. Explain why the choice of generator matters for DLP-based cryptography.

1. Order of an Element

Definition. Let $G$ be a group and $g \in G$. The order of $g$, written $\text{ord}(g)$, is the smallest positive integer $k$ such that $g^k = 1$ (the identity).

In $\mathbb{Z}/p\mathbb{Z}^*$, the identity is $1$, and the group has order $p - 1$. By Lagrange's theorem (Module 01), $\text{ord}(g)$ always divides $p - 1$.

Key fact: $g$ is a generator (primitive root) of $\mathbb{Z}/p\mathbb{Z}^*$ if and only if $\text{ord}(g) = p - 1$.

# Compute the order of every element in Z/7Z*
p = 7
print(f"Element orders in Z/{p}Z* (group order = {p-1}):")

for g in range(1, p):
    gmod = Mod(g, p)
    powers = [int(gmod^k) for k in range(1, p)]
    order = multiplicative_order(gmod)
    is_gen = order == p - 1
    powers_str = ', '.join(str(x) for x in powers)

Checkpoint 1. Look at the table above. Which elements have order 6 (= $p - 1$)? Which have order 3? Order 2? Can you see that the orders are always divisors of 6?

2. Primitive Roots

Definition. An element $g \in \mathbb{Z}/p\mathbb{Z}^*$ is a primitive root modulo $p$ if $\text{ord}(g) = p - 1$, i.e., the powers $g^0, g^1, \ldots, g^{p-2}$ give every element of $\mathbb{Z}/p\mathbb{Z}^*$.

Theorem (Existence). For every prime $p$, primitive roots modulo $p$ exist. In fact, there are exactly $\varphi(p-1)$ of them.

This is a nontrivial result! Not every group has generators, but $\mathbb{Z}/p\mathbb{Z}^*$ always does (because it is cyclic).

---

Misconception alert. "Small elements like 2 or 3 are always primitive roots." Not true! For example, $2$ is not a primitive root mod 7 (it has order 3), but $3$ is (order 6). Whether a given element is a primitive root depends on the prime, not on the element's size.

# Count primitive roots for several primes
print("p p-1 phi(p-1) #generators Match?")
for p in primes(3, 50):
    gen_count = sum(1 for g in range(1, p) if multiplicative_order(Mod(g, p)) == p - 1)
    phi_pm1 = euler_phi(p - 1)
    print(f"{p} {p-1} {phi_pm1} {gen_count} {'YES' if gen_count == phi_pm1 else 'NO'}")

The count always matches $\varphi(p-1)$.

3. The Efficient Primitive Root Test

Testing whether $g$ is a primitive root by computing all $p - 1$ powers is $O(p)$, far too slow for cryptographic primes.

The trick: $g$ has order $p - 1$ if and only if $g$ does NOT have order dividing any maximal proper divisor of $p - 1$. By Lagrange's theorem, if $\text{ord}(g) < p - 1$, then $\text{ord}(g)$ divides $(p-1)/q$ for some prime factor $q$ of $p - 1$.

Theorem (Efficient Test). $g$ is a primitive root modulo $p$ if and only if $$g^{(p-1)/q} \not\equiv 1 \pmod{p} \quad \text{for every prime factor } q \text{ of } p - 1.$$

This requires only as many exponentiations as there are distinct prime factors of $p - 1$, which is typically very few.

def is_primitive_root(g, p):
    """
    Test whether g is a primitive root modulo p
    using the efficient prime-factor test.
    """
    g = Mod(g, p)
    if g == 0:
        return False
    pm1 = p - 1
    prime_factors = [q for q, _ in factor(pm1)]
    for q in prime_factors:
        if g^(pm1 // q) == 1:
            return False
    return True

# Test with p = 23, where p - 1 = 22 = 2 * 11
p = 23
print(f"p = {p}, p-1 = {p-1} = {factor(p-1)}")
print(f"Prime factors of p-1: {[q for q, _ in factor(p-1)]}")
print()

for g in range(1, p):
    result = is_primitive_root(g, p)
    detail = ""
    if not result:
        gmod = Mod(g, p)
        for q in [2, 11]:
            if gmod^((p-1)//q) == 1:
                detail = f"  (g^{(p-1)//q} = 1, so ord(g) | {(p-1)//q})"
                break
    print(f"  g={g}: {'GENERATOR' if result else 'not'}{detail}")

Checkpoint 2. For $p = 31$ (so $p - 1 = 30 = 2 \cdot 3 \cdot 5$), how many exponentiations do we need to test one candidate? Test whether $g = 3$ is a primitive root mod 31 by checking $3^{15}, 3^{10}, 3^{6}$ modulo 31.

# Checkpoint 2, verify
p = 31
g = Mod(3, p)
print(f"p = {p}, p-1 = {factor(p-1)}")
print(f"Prime factors: {[q for q, _ in factor(p-1)]}")
print()
for q in [2, 3, 5]:
    exp = (p - 1) // q
    val = g^exp
    print(f"  g^({p-1}/{q}) = g^{exp} = {val}  {'== 1 (FAILS)' if val == 1 else '!= 1 (OK)'}")

print(f"\nis_primitive_root(3, 31) = {is_primitive_root(3, 31)}")
print(f"SageMath: multiplicative_order(3 mod 31) = {multiplicative_order(Mod(3, 31))}")

4. Finding All Primitive Roots

Once you have one primitive root $g$, you can find all of them:

Theorem. If $g$ is a primitive root mod $p$, then $g^k$ is also a primitive root if and only if $\gcd(k, p-1) = 1$.

In other words, the set of all primitive roots is $\{g^k : k \in (\mathbb{Z}/(p-1)\mathbb{Z})^*\}$.

---

Bridge from Module 01. This is a direct application of the theory of cyclic groups from Module 01: in a cyclic group $\langle g \rangle$ of order $n$, the element $g^k$ has order $n / \gcd(k, n)$. So $g^k$ is a generator iff $\gcd(k, n) = 1$.

# Find all primitive roots mod 23 using one known generator
p = 23
g = Mod(primitive_root(p), p)
print(f"One primitive root: g = {g}")
print(f"p - 1 = {p-1}")

# Method: g^k is a primitive root iff gcd(k, p-1) = 1
prim_roots_formula = sorted([int(g^k) for k in range(1, p-1) if gcd(k, p-1) == 1])

# Verify by brute force
prim_roots_brute = sorted([a for a in range(1, p) if multiplicative_order(Mod(a, p)) == p-1])

print(f"\nPrimitive roots (formula):     {prim_roots_formula}")
print(f"Primitive roots (brute force): {prim_roots_brute}")
print(f"Match? {prim_roots_formula == prim_roots_brute}")
print(f"Count: {len(prim_roots_formula)} = phi({p-1}) = {euler_phi(p-1)}")

5. Subgroups and Non-Generators

When $g$ is not a primitive root, its powers form a proper subgroup of $\mathbb{Z}/p\mathbb{Z}^*$. The subgroups of a cyclic group of order $n$ correspond to divisors of $n$: for each divisor $d \mid n$, there is exactly one subgroup of order $d$.

# Visualise all subgroups of Z/13Z*
p = 13
print(f"Z/{p}Z* has order {p-1} = {factor(p-1)}")
print(f"Divisors of {p-1}: {divisors(p-1)}")
print()

# Group elements by their order
from collections import defaultdict
order_groups = defaultdict(list)
for a in range(1, p):
    order_groups[multiplicative_order(Mod(a, p))].append(a)

for d in sorted(order_groups.keys()):
    elements = order_groups[d]
    g = Mod(elements[0], p)
    subgroup = sorted([int(g^k) for k in range(d)])
    print(f"Order {d}: elements with this order = {elements}")
    print(f"          subgroup <{elements[0]}> = {subgroup}")
    print()

6. Why Generators Matter for Cryptography

If you use a non-generator $g$ for Diffie-Hellman, the "shared secret" $g^{ab}$ lives in a subgroup. If that subgroup is small, an attacker can:

1. Enumerate all elements of the subgroup.

2. Check which one equals the public value.

3. Recover the secret exponent.

This is called a small-subgroup attack.

---

Crypto foreshadowing. In practice, DH uses one of two strategies to avoid this:

1. Safe primes: choose $p = 2q + 1$ with $q$ prime. Then $p - 1 = 2q$ has only subgroups of order $1, 2, q, 2q$. Use a generator of the order-$q$ subgroup (the quadratic residues).

2. Schnorr groups: work in a prime-order subgroup of order $q$ where $q \mid p - 1$ and $q$ is large.

Both ensure that the DLP has no exploitable substructure.

# Danger of using a non-generator: small subgroup
p = 23   # p - 1 = 22 = 2 * 11

# Using a generator (order 22): DLP over full group
g_good = Mod(primitive_root(p), p)
subgroup_good = sorted([int(g_good^k) for k in range(p-1)])
print(f"Generator g={int(g_good)}: powers fill all of Z/{p}Z*")
print(f"  Subgroup size: {len(subgroup_good)}")

# Using a non-generator of order 2: trivially breakable!
g_bad = Mod(p - 1, p)  # = -1 mod p, always has order 2
subgroup_bad = sorted([int(g_bad^k) for k in range(2)])
print(f"\nNon-generator g={int(g_bad)} (= -1): powers = {subgroup_bad}")
print(f"  Subgroup size: {len(subgroup_bad)}")
print(f"  An attacker only needs to check {len(subgroup_bad)} possibilities!")

7. SageMath Tools

SageMath provides primitive_root(p) (smallest primitive root) and multiplicative_order() (order of any element).

# SageMath primitives
for p in [7, 23, 101, 1009, 10007]:
    g = primitive_root(p)
    print(f"p = {p}: smallest primitive root = {g}, "
          f"phi(p-1) = {euler_phi(p-1)} generators out of {p-1}")

# How common are primitive roots? Fraction phi(p-1)/(p-1)

ps = list(primes(3, 500))
ratios = [float(euler_phi(p-1)) / float(p-1) for p in ps]

G = point(list(zip(ps, ratios)), size=20, alpha=0.7, color='blue')
G += line([(3, float(6/pi^2)), (500, float(6/pi^2))], color='red', linestyle='--',
          legend_label=f'$6/\\pi^2 \\approx {float(6/pi^2):.4f}$')
G.show(figsize=10, axes_labels=['Prime p', '$\\varphi(p-1)/(p-1)$'],
       title='Fraction of elements that are primitive roots',
       gridlines=True)

Checkpoint 3. For a safe prime $p = 2q + 1$ with $q$ prime, we have $\varphi(p-1) = \varphi(2q) = q - 1$. What fraction of $\mathbb{Z}/p\mathbb{Z}^*$ are generators? (Answer: $(q-1)/(2q) \approx 1/2$.) Safe primes have the highest possible generator density.

8. Exercises

Exercise 1 (Worked): Primitive Root Test by Hand

Problem. Is $g = 2$ a primitive root modulo $p = 13$?

Solution. We have $p - 1 = 12 = 2^2 \cdot 3$. The distinct prime factors are $\{2, 3\}$.

Check:

• $2^{12/2} = 2^6 = 64 \equiv 12 \equiv -1 \pmod{13}$. Since $-1 \neq 1$: pass.

• $2^{12/3} = 2^4 = 16 \equiv 3 \pmod{13}$. Since $3 \neq 1$: pass.

Both checks passed, so $g = 2$ is a primitive root mod 13.

# Exercise 1, verification
p = 13
g = Mod(2, p)
print(f"p - 1 = {p-1} = {factor(p-1)}")
print(f"2^6 mod 13 = {g^6}")
print(f"2^4 mod 13 = {g^4}")
print(f"is_primitive_root(2, 13) = {is_primitive_root(2, 13)}")
print(f"multiplicative_order(2 mod 13) = {multiplicative_order(g)}")

Exercise 2 (Guided): Finding All Primitive Roots mod 19

Problem.

1. Factor $p - 1 = 18$.

2. Use the efficient test to find the smallest primitive root $g$ modulo 19.

3. List all primitive roots modulo 19 using the formula $\{g^k : \gcd(k, 18) = 1\}$.

4. Verify that the count equals $\varphi(18)$.

Hint: $18 = 2 \cdot 3^2$, so the prime factors are $\{2, 3\}$.

# Exercise 2, fill in the TODOs
p = 19

# TODO 1: Factor p - 1
# print(f"p - 1 = {p-1} = {factor(p-1)}")

# TODO 2: Test g = 2, 3, ... until you find a primitive root
# for g_candidate in range(2, p):
#     if is_primitive_root(g_candidate, p):
#         print(f"Smallest primitive root: {g_candidate}")
#         break

# TODO 3: List all primitive roots using the formula
# g = Mod(???, p)
# all_roots = sorted([int(g^k) for k in range(1, p-1) if gcd(k, p-1) == 1])
# print(f"All primitive roots mod {p}: {all_roots}")

# TODO 4: Verify the count
# print(f"Count: {len(all_roots)} = phi({p-1}) = {euler_phi(p-1)}")

Exercise 3 (Independent): Safe Primes and Generator Density

Problem.

1. A prime $p$ is safe if $q = (p-1)/2$ is also prime. Find all safe primes less than 200.

2. For each safe prime, compute the fraction of elements that are primitive roots.

3. Compare with non-safe primes of similar size. Is the generator density higher or lower for safe primes? Explain why.

# Exercise 3, write your solution here

Summary

Concept	Key Fact
Order of $g$	Smallest $k > 0$ with $g^k \equiv 1$; always divides $p - 1$
Primitive root	$g$ with $\text{ord}(g) = p - 1$; generates the full group
Existence	Primitive roots exist for every prime $p$
Count	Exactly $\varphi(p-1)$ primitive roots modulo $p$
Efficient test	Check $g^{(p-1)/q} \neq 1$ for each prime factor $q$ of $p - 1$
Crypto relevance	Using a non-generator enables small-subgroup attacks

Now that we know how to pick a good generator, we are ready to build the Diffie-Hellman key exchange protocol.

---

Next: 05c. Diffie-Hellman Key Exchange