zero-divisors-composite-n.ipynb

Kernel: SageMath 10.0

Break: Zero Divisors in Z_n for Composite n

Module 02 | Breaking Weak Parameters

When n is composite, $\mathbb{Z}/n\mathbb{Z}$ has zero divisors, and any scheme that assumes a field will break.

Why This Matters

Many cryptographic constructions require field arithmetic: every nonzero element must have a multiplicative inverse. The simplest fields are $\mathbb{Z}/p\mathbb{Z}$ for a prime $p$.

But if someone uses $\mathbb{Z}/n\mathbb{Z}$ where $n$ is composite, the ring has zero divisors, nonzero elements $a, b$ with $a \cdot b \equiv 0 \pmod{n}$. These elements have no multiplicative inverse, and any scheme that tries to divide by them will fail.

This notebook explores exactly what goes wrong in $\mathbb{Z}/12\mathbb{Z}$.

The Scenario

We work in $\mathbb{Z}/12\mathbb{Z} = \{0, 1, 2, \ldots, 11\}$ with arithmetic modulo 12. Since $12 = 2^2 \times 3$ is composite, this ring is not a field.

Goal: Find all elements that lack multiplicative inverses, discover all zero divisors, and show how a toy encryption scheme breaks.

# === Step 1: Which elements of Z/12Z have inverses? ===
n = 12
R = Zmod(n)

print(f'Ring: Z/{n}Z')
print(f'n = {n} = {factor(n)}')
print(f'Is this a field? {R.is_field()}')
print()

print('Searching for multiplicative inverses:')

units = []
non_units = []
for a in range(n):
    g = gcd(a, n)
    if g == 1:
        inv = R(a)^(-1)
        units.append(a)
    else:
        non_units.append(a)

print(f'\nUnits (invertible): {units}  ({len(units)} elements)')
print(f'Non-units:          {non_units}  ({len(non_units)} elements)')
print(f'\nIn a field, ALL {n-1} nonzero elements would be invertible.')
print(f'Here only {len(units)} are. The rule: a is invertible iff gcd(a, n) = 1.')

Step 2: Find Zero Divisors

A zero divisor is a nonzero element $a$ such that $a \cdot b \equiv 0 \pmod{n}$ for some nonzero $b$.

In $\mathbb{Z}/12\mathbb{Z}$: since $12 = 4 \times 3$, we expect $3 \times 4 = 12 \equiv 0$. And $2 \times 6 = 12 \equiv 0$. Let's find them all.

# === Step 2: All zero divisor pairs in Z/12Z ===
n = 12
R = Zmod(n)

print(f'Zero divisor pairs in Z/{n}Z (a * b = 0, with a != 0 and b != 0):')
print()

zd_set = set()
for a in range(1, n):
    for b in range(a, n):
        if (a * b) % n == 0:
            print(f'  {a:2d} * {b:2d} = {a*b:3d} ≡ 0 (mod {n})')
            zd_set.add(a)
            zd_set.add(b)

print(f'\nAll zero divisors: {sorted(zd_set)}')
print(f'Notice: these are exactly the non-units (elements with gcd(a, 12) > 1).')

# === Step 3: A toy scheme that breaks ===
# "Encrypt" by multiplying by a key, "decrypt" by multiplying by the inverse.

n = 12
R = Zmod(n)

# Choose a key that is a zero divisor
key = R(3)
print(f'Key k = {key} (gcd({key}, {n}) = {gcd(Integer(key), n)}. NOT coprime!)')
print()

# Encrypt: c = m * k mod n
print('Encrypting messages with c = m * k mod 12:')
print('Message | Ciphertext')
ciphertext_map = {}
for m in range(n):
    c = R(m) * key
    print(f'{m} | {c}')
    c_int = Integer(c)
    if c_int not in ciphertext_map:
        ciphertext_map[c_int] = []
    ciphertext_map[c_int].append(m)

print()
print('=== Collisions (different messages, same ciphertext) ===')
for c_val in sorted(ciphertext_map.keys()):
    msgs = ciphertext_map[c_val]
    if len(msgs) > 1:
        print(f'  Ciphertext {c_val}: could be message {msgs}')

print()
print('Multiple messages map to the same ciphertext!')
print('Decryption is ambiguous, information is irreversibly lost.')
print()
print('Try computing k^(-1):')
try:
    key_inv = key^(-1)
    print(f'  k^(-1) = {key_inv}')
except Exception as e:
    print(f'  ERROR: {e}')
    print(f'  Cannot decrypt!')

The Fix: Use a Prime Modulus

When $p$ is prime, $\mathbb{Z}/p\mathbb{Z}$ is a field: every nonzero element has a multiplicative inverse. There are no zero divisors.

This is why cryptographic protocols work modulo a prime $p$.

# === The fix: use a prime modulus ===
p = 13  # Prime close to 12 for comparison
F = Zmod(p)

print(f'Ring: Z/{p}Z  (p = {p} is prime)')
print(f'Is this a field? {F.is_field()}')
print()

print('Every nonzero element has an inverse:')
for a in range(1, p):
    inv = F(a)^(-1)
    print(f'  {a:2d}^(-1) = {inv:2d}   (check: {a} * {inv} = {Integer(F(a) * inv)})')

print(f'\nZero divisors? NONE.')
print(f'The toy encryption scheme works perfectly in Z/{p}Z.')

# Quick demo
key = F(3)
msg = F(7)
ct = msg * key
recovered = ct * key^(-1)
print(f'\nDemo: Encrypt({msg}) = {msg} * {key} = {ct}')
print(f'      Decrypt({ct}) = {ct} * {key}^(-1) = {ct} * {key^(-1)} = {recovered}')
print(f'      Correct? {recovered == msg}')

Exercises

1. Zero divisors in $\mathbb{Z}/15\mathbb{Z}$: Find all zero divisors in $\mathbb{Z}/15\mathbb{Z}$. Which elements are invertible? How many? Hint: $15 = 3 \times 5$, so look for products of 3 and 5 and their multiples.

2. Zero divisors in $\mathbb{Z}/21\mathbb{Z}$: Repeat for $\mathbb{Z}/21\mathbb{Z}$. $21 = 3 \times 7$.

3. Characterize invertible elements: In $\mathbb{Z}/n\mathbb{Z}$, the number of invertible elements is $\varphi(n)$ (Euler's totient). Verify that $\varphi(12) = 4$, $\varphi(15) = 8$, $\varphi(21) = 12$ by listing the units.

4. Prime power modulus: Consider $\mathbb{Z}/8\mathbb{Z}$ where $8 = 2^3$. Find all zero divisors. Is $\mathbb{Z}/p^k\mathbb{Z}$ ever a field for $k \geq 2$?

# === Exercise workspace ===

# Exercise 1: Zero divisors in Z/15Z
n = 15
print(f'Z/{n}Z where {n} = {factor(n)}')
print(f'Euler totient phi({n}) = {euler_phi(n)}')
print()

# TODO: Find all zero divisors
# TODO: List all units (invertible elements)
# Hint: an element a is invertible iff gcd(a, n) = 1

Summary

Modulus $n$	Structure of $\mathbb{Z}/n\mathbb{Z}$	Zero Divisors	Units	Field?
$n = 12 = 2^2 \times 3$	Ring with zero divisors	$2, 3, 4, 6, 8, 9, 10$	$1, 5, 7, 11$	No
$n = 13$ (prime)	Field	None	All $1, \ldots, 12$	Yes
$n = 15 = 3 \times 5$	Ring with zero divisors	$3, 5, 6, 9, 10, 12$	$1, 2, 4, 7, 8, 11, 13, 14$	No

Key takeaways:

• $\mathbb{Z}/n\mathbb{Z}$ is a field if and only if $n$ is prime.

• When $n$ is composite, elements with $\gcd(a, n) > 1$ are zero divisors and have no inverse.

• The number of invertible elements is $\varphi(n)$ (Euler's totient), not $n - 1$.

• Zero divisors cause information loss: distinct inputs produce identical outputs under multiplication.

• Any cryptosystem that requires division (multiplicative inverses) must use a prime modulus to work in a field.

• This is the integer analogue of the polynomial fact: $\mathbb{F}_p[x]/(f(x))$ is a field only when $f(x)$ is irreducible (see the companion break notebook).

---

Back to Module 02: Rings, Fields, and Polynomials