GitHub Repository: duyuefeng0708/Cryptography-From-First-Principle
Path: blob/main/foundations/02-rings-fields-polynomials/sage/02b-integers-mod-n-as-ring.ipynb
⁴⁸³ views

unlisted

Kernel: SageMath 10.5

Integers Mod n as a Ring

Module 02 | 02-rings-fields-polynomials

Z/nZ with both operations, zero divisors, units, and the unit group

Objectives

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

Construct Z/nZ as a commutative ring with two operations and verify the ring axioms concretely.
Build complete addition and multiplication tables for Z/12Z and read off structural properties.
Define zero divisors, find them all in Z/nZ, and prove the gcd characterization.
Define units, find them all in Z/nZ, and connect to the unit group (Z/nZ)* from Module 01.
State and verify the dichotomy theorem: every nonzero element of Z/nZ is either a unit or a zero divisor.
Explain why zero divisors are catastrophic for cryptography and why we need fields.

Prerequisites

Completion of What Is a Ring?, you know ring axioms (closure under +, *, associativity, distributivity, additive identity/inverses, multiplicative identity).
From Module 01: You studied Z/nZ as an additive group and (Z/nZ)* as a multiplicative group. You know gcd and modular inverses.

Bridge from 02a: In the previous notebook, we saw that a ring is a set with two operations satisfying certain axioms. We verified those axioms for the integers Z. Now we apply the same lens to a structure you already know well: the integers mod n. The surprise is that putting both operations together on a finite set creates phenomena that neither operation exhibits alone.

Motivating Question

Think back to Module 01. You studied (Z/12Z)* = {1, 5, 7, 11}, the elements that have multiplicative inverses mod 12.

But what happens to the OTHER elements: 2, 3, 4, 6, 8, 9, 10?

They cannot have multiplicative inverses. Are they just... inert? Boring? Harmless?

It turns out they have a far more dangerous property. They can annihilate nonzero elements, multiply two perfectly good nonzero elements and get zero. This is called being a zero divisor, and it is the key new phenomenon that arises when we view Z/nZ as a ring rather than just a group.

Let us find them.

1. Z/nZ as a Ring: Two Operations at Once

Bridge from Module 01: In Module 01, you worked with Z/nZ under addition (an abelian group) and separately with (Z/nZ)* under multiplication (another abelian group). A ring packages both operations into a single algebraic structure, linked by the distributive law.

Let us build Z/12Z as a ring in SageMath and verify the key structure.

In [ ]:

# Build Z/12Z as a ring
R = Zmod(12)

print("Ring:", R)
print("Order (number of elements):", R.order())
print("Is commutative ring?", R.is_commutative())
print("Is a field?", R.is_field())
print()
print("Additive identity (zero):", R.zero())
print("Multiplicative identity (one):", R.one())
print()
print("Elements:", list(R))

Notice: SageMath tells us Z/12Z is not a field. By the end of this notebook, you will understand exactly why, it has zero divisors.

Let us verify the ring axioms concretely. We will check the distributive law, since that is the axiom that connects the two operations.

In [ ]:

# Verify distributive law: a * (b + c) == a*b + a*c for ALL triples in Z/12Z
R = Zmod(12)
failures = 0
for a in R:
    for b in R:
        for c in R:
            if a * (b + c) != a*b + a*c:
                failures += 1

print(f"Checked all {12^3} = {12**3} triples (a, b, c) in Z/12Z.")
print(f"Distributive law failures: {failures}")
print("Distributive law holds!") if failures == 0 else print("PROBLEM!")

2. The Complete Operation Tables

To really see the ring, let us build the full addition and multiplication tables for Z/12Z. In Module 01, you may have built the addition table. Now we add the multiplication table and compare them side by side.

2.1 Addition Table

In [ ]:

# Complete addition table for Z/12Z
R = Zmod(12)
elems = list(R)
n = len(elems)

# Build table as a matrix for clean display
add_table = matrix(ZZ, n, n, lambda i, j: ZZ(elems[i] + elems[j]))

# Display with labels
header = "  +  | " + " ".join(f"{ZZ(e)}" for e in elems)
print(header)
print("-----+" + "-" * (4 * n))
for i in range(n):
    row = f" {ZZ(elems[i])}  | " + " ".join(f"{add_table[i,j]}" for j in range(n))
    print(row)

The addition table looks perfectly well-behaved, every element has an additive inverse, every row is a permutation of Z/12Z (this is the Latin square property of group tables).

2.2 Multiplication Table

Now the multiplication table. Predict before you run: Will every row be a permutation of Z/12Z? (Hint: think about what happens in the row for element 2.)

In [ ]:

# Complete multiplication table for Z/12Z
R = Zmod(12)
elems = list(R)
n = len(elems)

mul_table = matrix(ZZ, n, n, lambda i, j: ZZ(elems[i] * elems[j]))

header = "  *  | " + " ".join(f"{ZZ(e)}" for e in elems)
print(header)
print("-----+" + "-" * (4 * n))
for i in range(n):
    row = f" {ZZ(elems[i])}  | " + " ".join(f"{mul_table[i,j]}" for j in range(n))
    print(row)

Observe the multiplication table carefully:

The row for 0 is all zeros. (Of course: 0 times anything is 0.)
The row for 1 is just 0, 1, 2, ..., 11. (The multiplicative identity.)
The row for 5 is a permutation of all 12 elements. (5 is a unit, it has an inverse!)
The row for 2 is 0, 2, 4, 6, 8, 10, 0, 2, 4, 6, 8, 10. It repeats! And it contains 0 in a position other than the first column.
The row for 3 contains a 0 at column 4: that is, 3 * 4 = 0 in Z/12Z.

That last observation is the key phenomenon: two nonzero elements whose product is zero.

3. Zero Divisors: When Nonzero Times Nonzero Equals Zero

Definition. Let R be a commutative ring. A zero divisor is a nonzero element $a \in R$ such that there exists a nonzero element $b \in R$ with $a \cdot b = 0$ .

Misconception Alert: "A zero divisor is an element equal to zero." No! A zero divisor is a nonzero element whose product with some other nonzero element gives zero. The name is confusing, it does not mean "divisor that is zero" but rather "divisor of zero" (an element that divides zero in a nontrivial way).

3.1 Finding Zero Divisors in Z/12Z

Let us find every zero divisor in Z/12Z by brute force.

In [ ]:

# Find ALL zero divisor pairs in Z/12Z
R = Zmod(12)

print("Zero divisor pairs (a * b = 0, with a != 0 and b != 0):")

zero_divisor_pairs = []
for a in R:
    for b in R:
        if a != 0 and b != 0 and a * b == 0:
            zero_divisor_pairs.append((ZZ(a), ZZ(b)))
            print(f"  {ZZ(a)} * {ZZ(b)} = 0  (mod 12)")

print(f"\nTotal zero divisor pairs: {len(zero_divisor_pairs)}")

# Which elements appear as zero divisors?
zd_elements = sorted(set(a for a, b in zero_divisor_pairs))
print(f"\nZero divisor elements: {zd_elements}")

3.2 The gcd Characterization

Look at those zero divisors: {2, 3, 4, 6, 8, 9, 10}. What do they have in common?

Checkpoint. Predict: Compute gcd(a, 12) for each zero divisor a. What pattern do you see?

Theorem. In Z/nZ, a nonzero element $a$ is a zero divisor if and only if $\gcd(a, n) > 1$ .

Why? If $d = \gcd(a, n) > 1$ , then let $b = n/d$ . We have $b \neq 0$ in Z/nZ (since $1 \leq b < n$ ), and $a \cdot b = a \cdot (n/d) = (a/d) \cdot n \equiv 0 \pmod{n}$ . So $a$ is a zero divisor.

Conversely, if $\gcd(a, n) = 1$ , then $a$ has a multiplicative inverse (it is a unit), and units can never be zero divisors (proof: if $ab = 0$ and $a$ is a unit, multiply both sides by $a^{-1}$ to get $b = 0$ ).

Let us verify this computationally.

In [ ]:

# Verify: zero divisor <=> gcd(a, 12) > 1
R = Zmod(12)
n = 12


for a in range(1, n):  # skip 0 (zero divisors are nonzero by definition)
    g = gcd(a, n)
    is_gcd_gt1 = g > 1
    # Check if a is a zero divisor by searching for a witness
    is_zd = any(R(a) * R(b) == 0 and b != 0 for b in range(1, n))
    match = "MATCH" if is_gcd_gt1 == is_zd else "MISMATCH!"

Every single element matches. The characterization is:

a \text{ is a zero divisor in } \mathbb{Z}/n\mathbb{Z} \iff \gcd(a, n) > 1

4. Units: The Elements That Can Divide

Bridge from Module 01: You already know this! In Module 01, you studied the multiplicative group (Z/nZ)*, the set of elements with multiplicative inverses. That was the unit group of the ring Z/nZ. Now we see where it fits in the bigger picture.

Definition. An element $a \in R$ is a unit if there exists $b \in R$ with $a \cdot b = 1$ . The element $b$ is called the multiplicative inverse of $a$ , written $a^{-1}$ .

Theorem. In Z/nZ, element $a$ is a unit if and only if $\gcd(a, n) = 1$ .

In [ ]:

# Find all units in Z/12Z and their inverses
R = Zmod(12)
n = 12

print("Units of Z/12Z (elements with multiplicative inverses):")

units = []
for a in R:
    if a == 0:
        continue
    if gcd(ZZ(a), n) == 1:
        inv_a = R(a)^(-1)
        units.append(ZZ(a))
        print(f"  {ZZ(a)} is a unit:  {ZZ(a)} * {ZZ(inv_a)} = {ZZ(a * inv_a)}  (mod 12)")

print(f"\nUnit group (Z/12Z)* = {{{', '.join(str(u) for u in units)}}}")
print(f"Order of unit group: |phi(12)| = {euler_phi(12)}")
print(f"\nThis is exactly the group you studied in Module 01!")

5. The Dichotomy Theorem: Unit or Zero Divisor, Never Both

We have two characterizations:

$a$ is a unit $\iff$ $\gcd(a, n) = 1$
$a$ is a zero divisor $\iff$ $\gcd(a, n) > 1$

Since $\gcd(a, n)$ is always either equal to 1 or greater than 1, we get a beautiful dichotomy.

Theorem (Dichotomy). In Z/nZ with $n > 1$ , every nonzero element is either a unit or a zero divisor. No element is both. No nonzero element is neither.

Proof sketch:

If $\gcd(a,n) = 1$ : $a$ is a unit (has an inverse). $a$ cannot be a zero divisor (if $ab = 0$ , multiply by $a^{-1}$ to get $b = 0$ ).
If $\gcd(a,n) > 1$ : $a$ is a zero divisor (take $b = n / \gcd(a,n)$ ). $a$ cannot be a unit (the equation $ax \equiv 1 \pmod{n}$ has no solution).

Let us visualize this partition.

In [ ]:

# Visualize the dichotomy: classify every element of Z/nZ
def classify_elements(n):
    """Classify each element of Z/nZ as 'zero', 'unit', or 'zero divisor'."""
    R = Zmod(n)
    classification = {}
    for a in range(n):
        if a == 0:
            classification[a] = 'zero (additive identity)'
        elif gcd(a, n) == 1:
            classification[a] = 'UNIT'
        else:
            classification[a] = 'ZERO DIVISOR'
    return classification

# Show for Z/12Z
n = 12
cls = classify_elements(n)

print(f"Classification of elements in Z/{n}Z:")
for a in range(n):
    g = gcd(a, n) if a > 0 else '-'
    print(f"  {a}   gcd({a},{n}) = {str(g)}   -->  {cls[a]}")

units = [a for a in range(n) if cls[a] == 'UNIT']
zds = [a for a in range(n) if cls[a] == 'ZERO DIVISOR']
print(f"\nUnits ({len(units)}):        {units}")
print(f"Zero divisors ({len(zds)}): {zds}")
print(f"Total nonzero: {len(units) + len(zds)} = {len(units)} + {len(zds)} = {n - 1}  (check!)")

Key takeaway: The nonzero elements of Z/12Z split cleanly into two camps:

Units (gcd = 1)	Zero divisors (gcd > 1)
{1, 5, 7, 11}	{2, 3, 4, 6, 8, 9, 10}
Have inverses	Annihilate nonzero elements
Form a group (Z/12Z)*	Do NOT form a group (not closed under *)

When Does Z/nZ Have NO Zero Divisors?

Checkpoint. Predict: For which values of n does Z/nZ have no zero divisors at all? (Think about what makes gcd(a, n) = 1 for ALL nonzero a.)

In [ ]:

# When does Z/nZ have no zero divisors?
print("Checking Z/nZ for n = 2 through 20:\n")
for n in range(2, 21):
    zds = [a for a in range(1, n) if gcd(a, n) > 1]
    units = [a for a in range(1, n) if gcd(a, n) == 1]
    status = "NO zero divisors (every nonzero element is a unit!)" if len(zds) == 0 else f"zero divisors: {zds}"
    marker = " <-- FIELD!" if len(zds) == 0 else ""
    print(f"  Z/{n}Z : {len(units)} units, {len(zds)} zero divisors ,  {status}{marker}")

The pattern: Z/nZ has no zero divisors precisely when $n$ is prime. When $n$ is prime, every nonzero element is a unit, so Z/pZ is a field. We will study fields in depth in notebook 02d.

Crypto Foreshadowing: This is why RSA works with a composite modulus $n = pq$ (zero divisors exist and finding them means factoring $n$ ), while elliptic curve cryptography works over a prime field $\mathbb{F}_p$ (no zero divisors, clean algebraic structure). Zero divisors are not just an algebraic curiosity, they are a security boundary between different types of cryptosystems.

6. Crypto Implications: Why Zero Divisors Are Dangerous

Imagine you try to build a "cryptosystem" by multiplying messages in Z/nZ with a composite n. If your key happens to be a zero divisor, you lose information irreversibly:

In [ ]:

# Demonstration: zero divisors destroy information
R = Zmod(12)

# Suppose we "encrypt" by multiplying by a key
key = R(3)  # 3 is a zero divisor in Z/12Z!

print(f"Key = {key} (a zero divisor in Z/12Z)")
print(f"\n'Encrypting' each message m by computing m * {key} mod 12:\n")

ciphertexts = {}
for m in R:
    c = m * key
    if ZZ(c) not in ciphertexts:
        ciphertexts[ZZ(c)] = []
    ciphertexts[ZZ(c)].append(ZZ(m))
    print(f"  m = {ZZ(m)}  -->  c = {ZZ(m)} * {ZZ(key)} = {ZZ(c)}  (mod 12)")

print("\nCiphertext collisions (different messages, same ciphertext):")
for c, msgs in sorted(ciphertexts.items()):
    if len(msgs) > 1:
        print(f"  Ciphertext {c} <-- messages {msgs}")

print(f"\nProblem: {len(R)} messages map to only {len(ciphertexts)} distinct ciphertexts.")
print("Decryption is IMPOSSIBLE, you cannot invert multiplication by a zero divisor!")

The lesson: Multiplication by a zero divisor is a lossy operation. It maps multiple distinct inputs to the same output, so decryption is impossible. This is fundamentally different from multiplication by a unit, which is a bijection (every output comes from a unique input, because you can multiply by the inverse).

This is why cryptographic operations (encryption, signature, etc.) must use units or, better yet, work in a field where every nonzero element is automatically a unit. We will see this principle again and again.

7. Comparing Different Moduli

Let us compare the unit/zero-divisor structure across several moduli to build intuition for which rings are "nice" (few or no zero divisors) vs. "dangerous" (many zero divisors).

In [ ]:

# Compare structure across different moduli

for n in [2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 15, 16, 30]:
    units = [a for a in range(1, n) if gcd(a, n) == 1]
    zds = [a for a in range(1, n) if gcd(a, n) > 1]
    ratio = f"{len(units)}/{n-1}" if n > 1 else "n/a"
    p = "YES" if is_prime(n) else "no"
    zd_str = str(zds) if len(zds) <= 10 else str(zds[:8]) + "..."

Observations:

When $n$ is prime: unit ratio = $(n-1)/(n-1) = 1$ (i.e., 100% units, 0 zero divisors). This is a field.
When $n$ is a prime power ( $4, 8, 16, \ldots$ ): there are still zero divisors (multiples of $p$ ), but fewer than for general composites.
When $n$ is highly composite ( $12, 30, \ldots$ ): zero divisors dominate. The ring is "far from a field."

Exercises

Exercise 1: Analyze Z/15Z (Fully Worked)

Task: Find all zero divisors and all units in Z/15Z. Verify the dichotomy.

Solution:

In [ ]:

# EXERCISE 1. FULLY WORKED SOLUTION
# Analyze Z/15Z: find units, zero divisors, verify dichotomy

n = 15
R = Zmod(n)

print(f"Analysis of Z/{n}Z")

# Step 1: Classify each nonzero element
units = []
zero_divisors = []
for a in range(1, n):
    g = gcd(a, n)
    if g == 1:
        units.append(a)
    else:
        zero_divisors.append(a)

print(f"\nUnits (gcd(a, {n}) = 1):        {units}")
print(f"Zero divisors (gcd(a, {n}) > 1): {zero_divisors}")

# Step 2: Verify units have inverses
print(f"\nUnit inverses:")
for u in units:
    inv_u = R(u)^(-1)
    print(f"  {u}^(-1) = {ZZ(inv_u)}  (check: {u} * {ZZ(inv_u)} = {ZZ(R(u) * inv_u)} mod {n})")

# Step 3: Verify zero divisors have witnesses
print(f"\nZero divisor witnesses:")
for a in zero_divisors:
    # Find smallest nonzero b with a*b = 0 mod n
    for b in range(1, n):
        if (a * b) % n == 0:
            print(f"  {a} * {b} = 0  (mod {n})  [gcd({a},{n}) = {gcd(a,n)}]")
            break

# Step 4: Verify dichotomy
print(f"\nDichotomy check:")
print(f"  #units + #zero_divisors = {len(units)} + {len(zero_divisors)} = {len(units) + len(zero_divisors)}")
print(f"  n - 1 = {n - 1}")
print(f"  Match: {len(units) + len(zero_divisors) == n - 1}")

Exercise 2: Analyze Z/20Z (Guided)

Task: Repeat the analysis for Z/20Z. Fill in the TODOs.

Hint: 20 = 4 * 5, so zero divisors are elements sharing a factor of 2 or 5 with 20.

In [ ]:

# EXERCISE 2. GUIDED (fill in the TODOs)
n = 20
R = Zmod(n)

# TODO 1: Build the list of units (elements a with gcd(a, 20) == 1)
# units = [a for a in range(1, n) if ...]

# TODO 2: Build the list of zero divisors (elements a with gcd(a, 20) > 1)
# zero_divisors = [a for a in range(1, n) if ...]

# TODO 3: For each zero divisor, find one witness b such that a * b = 0 mod 20
# Hint: b = n // gcd(a, n) always works. Why?

# TODO 4: Verify that #units + #zero_divisors == n - 1

# TODO 5: What is the order of the unit group (Z/20Z)*? Compare with euler_phi(20).

Exercise 3: Explore Z/pZ for a Prime p (Independent)

Task: Choose a prime $p$ of your choice (try $p = 17$ or $p = 23$ ). Verify computationally that Z/pZ has no zero divisors and that every nonzero element is a unit. Build the multiplication table and confirm that every row (except row 0) is a permutation of all elements.

In [ ]:

# EXERCISE 3. INDEPENDENT
# Choose a prime p and explore Z/pZ
# Your code here:

Summary

Concept	Key idea
$\mathbb{Z}/n\mathbb{Z}$ as a ring	Addition and multiplication mod $n$ , linked by the distributive law
Zero divisors	Nonzero elements $a$ with $ab = 0$ for some nonzero $b$ . In $\mathbb{Z}/n\mathbb{Z}$ , $a$ is a zero divisor iff $\gcd(a, n) > 1$
Units	Elements with multiplicative inverses. In $\mathbb{Z}/n\mathbb{Z}$ , $a$ is a unit iff $\gcd(a, n) = 1$ . These form the group $(\mathbb{Z}/n\mathbb{Z})^*$ from Module 01
Dichotomy theorem	Every nonzero element of $\mathbb{Z}/n\mathbb{Z}$ is either a unit or a zero divisor, never both, never neither
Prime modulus = no zero divisors	$\mathbb{Z}/n\mathbb{Z}$ has no zero divisors iff $n$ is prime, making $\mathbb{Z}/p\mathbb{Z}$ a field (notebook 02d)
Crypto implication	Zero divisors destroy information (multiplication is not injective). Cryptosystems need units or fields

What we learned here will be essential for:

Notebook 02d: defining fields precisely (a ring where every nonzero element is a unit)
Module 03: constructing extension fields GF(2^8) for AES
Module 04: understanding why RSA works in (Z/nZ)* with composite n

Next: Polynomial Rings