Chapter 6 — Discrete structures | Bachelor's Quantum and post-quantum security

Open, free learning for anyone who wants to protect people and technology. No account is required to read this text or its worked answers.

Chapter 6 — Discrete structures

Lesson map

Lesson 06 published. Map, example, EX011.

flowchart TD
  N0["Learning outcomes"]
  N1["6.1 Modular arithmetic and groups"]
  N2["6.2 Polynomial rings"]
  N3["6.3 Practical activity — Lab R"]
  N4["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4
  N4 --> EX["Worked example"]
  EX --> Q["Exercise EX011"]

Logical drawing

flowchart LR
  N0["Learning outcomes"]
  N1["6.1 Modular arithmetic and groups"]
  N2["6.2 Polynomial rings"]
  N3["6.3 Practical activity — Lab R"]
  N4["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> Q["EX011"]

[Learning outcomes]
    |
    v
[6.1 Modular arithmetic and groups]
    |
    v
[6.2 Polynomial rings]
    |
    v
[6.3 Practical activity — Lab R]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX011]

Learning outcomes

You will (1) compute with modular arithmetic; (2) explain groups and why hidden periods matter; (3) multiply polynomials in the ring Z_q[x]/(x^n+1); and (4) connect these structures to RSA, elliptic curves and ML-KEM.

6.1 Modular arithmetic and groups

Working modulo q keeps numbers in {0, …, q−1}: 15 mod 7 = 1. A group is a set with an operation that is associative, has an identity and inverses. The non-zero numbers modulo a prime p form a group under multiplication; the points of an elliptic curve form a group under point addition. Repeating the operation from a starting element g eventually cycles: g, g², g³, … returns to 1 after r steps, where r is the order of g. Finding r — a hidden period — is hard classically for large groups, and RSA, Diffie–Hellman and elliptic-curve cryptography all rest on problems equivalent to or reducible to finding such periods or discrete logarithms. Shor's algorithm finds periods efficiently on a quantum computer, which is why all of these fall together.

6.2 Polynomial rings

A polynomial ring Z_q[x]/(x^n+1) contains polynomials of degree below n with coefficients modulo q. To multiply, multiply normally, then replace x^n by −1. ML-KEM (FIPS 203) uses n = 256 and q = 3329; ML-DSA (FIPS 204) uses n = 256 and q = 8380417. Vectors of these polynomials form modules, hence "module lattice". The ring is chosen for compactness and fast multiplication; security comes from adding small random noise, a topic of Chapter 23. No efficient quantum period-finding attack is known against these noisy problems.

6.3 Practical activity — Lab R

# Lab R (ch 6): multiplication in R_q = Z_q[x]/(x^n + 1), the ring behind ML-KEM (there n=256, q=3329).
q, n = 17, 4
def mul(a, b):
    c = [0] * n
    for i in range(n):
        for j in range(n):
            k = i + j
            if k < n:
                c[k] = (c[k] + a[i] * b[j]) % q
            else:                       # x^n = -1, so wrap around with a sign flip
                c[k - n] = (c[k - n] - a[i] * b[j]) % q
    return c
a = [1, 2, 0, 3]      # 1 + 2x + 3x^3
b = [0, 1, 0, 0]      # x
print("a*x  =", mul(a, b), " (coefficients shift; x^3 * x = x^4 = -1 -> 17-3 = 14)")
print("a*a  =", mul(a, a))

Expected output:

a*x  = [14, 1, 2, 0]  (coefficients shift; x^3 * x = x^4 = -1 -> 17-3 = 14)
a*a  = [6, 4, 12, 6]

Check by hand: (1 + 2x + 3x³)·x = x + 2x² + 3x⁴ = −3 + x + 2x² ≡ 14 + x + 2x² (mod 17).

The lab multiplies two small polynomials in a ring with toy parameters and prints the result. Doing one product by hand, as shown, is the best way to see where the sign flip happens. Real parameters are far larger, but the rule is the same, and the libraries you will use apply it with much faster algorithms. The toy ring is not secure; it exists only to make the arithmetic visible.

6.4 Worked example

An HCU developer asks why their post-quantum library "multiplies polynomials" when RSA "exponentiates numbers". RSA works in the multiplicative group modulo N, where a hidden period exists and Shor can find it. ML-KEM works with noisy linear algebra over polynomial rings, where no such period structure is known to help. The arithmetic looks different because the hard problem is different.

The developer's question is a good one to answer before any migration work, because it explains why the new algorithms need new review skills. Code that handles polynomials and noise has different failure modes from code that handles large integers, such as mistakes in reduction or in sampling the noise.

6.5 Common errors and limits

Forgetting the sign flip when reducing x^n to −1.
Believing the ring structure alone provides security; without noise the equations are easy to solve.
Assuming "no known attack" means "proved secure".

The sign flip is the most common hand-calculation mistake, and tests with known answers catch it. The second error matters more: the ring makes the arithmetic convenient, but the security comes from the added noise. Without it, the equations are ordinary linear algebra and easy to solve. No known attack is a statement about current knowledge, so standards include security margins and are reviewed as research continues.

Exercises

EX011 — Order of an element. Find the order of 3 modulo 7 by listing powers. Rubric: 3 = correct order with the list.
EX012 — Ring product. Compute (2 + x)(3 + x³) in Z_17[x]/(x⁴+1) and check with Lab R. Rubric: 3 = correct coefficients with the reduction shown.

Synthesis

Classical public-key cryptography hides periods in groups, which Shor's algorithm finds. Lattice-based PQC computes in polynomial rings and hides secrets under noise, a structure with no known quantum shortcut.

Continue studying — chapter 06 of 40

← Chapter 05 (draft) · Course chapter index · Chapter 07 (draft) →