Chapter 2 — Discrete mathematics | Engineering 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 2 — Discrete mathematics

Lesson map

Lesson 02 published. Map, example, EX003.

flowchart TD
  N0["Learning outcomes"]
  N1["2.1 Modular arithmetic"]
  N2["2.2 Polynomial rings"]
  N3["2.3 Practical activity — Lab R"]
  N4["2.4 Hash functions"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5
  N5 --> EX["Worked example"]
  EX --> Q["Exercise EX003"]

Logical drawing

flowchart LR
  N0["Learning outcomes"]
  N1["2.1 Modular arithmetic"]
  N2["2.2 Polynomial rings"]
  N3["2.3 Practical activity — Lab R"]
  N4["2.4 Hash functions"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX003"]

[Learning outcomes]
    |
    v
[2.1 Modular arithmetic]
    |
    v
[2.2 Polynomial rings]
    |
    v
[2.3 Practical activity — Lab R]
    |
    v
[2.4 Hash functions]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX003]

Learning outcomes

You will (1) compute in modular arithmetic and polynomial rings; (2) explain the ring Z_q[x]/(x^n+1) used by ML-KEM and ML-DSA; (3) state what a hash function's security properties are; and (4) connect group structure to why Shor's algorithm works. It builds on Chapter 1 and prepares probability (Chapter 7) and the lattice methods of Chapter 24.

2.1 Modular arithmetic

Arithmetic modulo q keeps numbers in {0, …, q−1}. RSA uses a composite modulus; elliptic-curve cryptography uses groups of points over a prime field. Both rely on the hardness of finding a hidden period — the order of an element, or a discrete logarithm. Shor's insight is that a quantum computer can find periods efficiently with the quantum Fourier transform; that is why every scheme whose security reduces to a hidden period in an abelian group falls together.

This shared weakness is why migration cannot be done one algorithm at a time by swapping RSA for elliptic curves: both fall to the same idea. Post-quantum schemes are chosen precisely because their hard problems, such as noisy linear equations or hash inversion, have no known hidden period for a quantum computer to find.

2.2 Polynomial rings

ML-KEM (FIPS 203) computes with polynomials of degree below 256 whose coefficients are integers modulo q = 3329, reduced modulo x^256 + 1. In this ring, multiplying by x shifts coefficients up one place, and the coefficient that falls off the top wraps to the bottom with its sign flipped, because x^n = −1. Vectors and matrices of such polynomials form a module, hence "module-lattice". The structure gives compact keys and fast multiplication (via the number-theoretic transform), while hardness comes from adding small noise — the subject of Chapter 24.

2.3 Practical activity — Lab R

# Lab R (ch 2): 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⁴ = x + 2x² − 3 ≡ 14 + x + 2x² (mod 17).

The hand check shows the wrap-around rule at work: the x⁴ term exceeds the degree limit for n equal to four, so it becomes minus three, and minus three modulo seventeen is fourteen. ML-KEM uses the same rule with n equal to 256 and q equal to 3329. Students who get the sign wrong will compute a different polynomial, and in a real implementation that mistake would break every decapsulation, which is why known-answer tests catch it at once.

2.4 Hash functions

A cryptographic hash maps any input to a fixed-length digest. Its required properties are preimage resistance (given a digest, find no input), second-preimage resistance and collision resistance. Hash-based signatures (SLH-DSA in FIPS 205; LMS and XMSS in SP 800-208) need only these properties, which is why they are the most conservative post-quantum signatures: quantum computers are not known to do much better than Grover-style speed-ups against good hash functions.

Grover can search for preimages faster, roughly square-rooting the work, so a 256-bit hash still offers about 128 bits against preimage search. Collision search with quantum algorithms gains less in practice than the idealised bounds suggest. The trade-off for hash-based signatures is size and speed, not security assumptions.

2.5 Worked example

A BPA developer asks why the post-quantum library "multiplies polynomials" when RSA "just exponentiates". The answer: RSA's security lives in the multiplicative group modulo N, where Shor finds periods. ML-KEM's lives in noisy linear algebra over a polynomial ring, where no period-finding shortcut is known; the ring is for efficiency, the noise is for security.

The developer's follow-up is usually about cost: polynomial multiplication with the number-theoretic transform is fast, and ML-KEM key generation is often quicker than RSA key generation. What changes for the system is size: keys and ciphertexts are larger than elliptic-curve ones. That shifts the engineering problem from CPU time to bytes on the wire.

2.6 Common errors and limits

Forgetting the sign flip when reducing by x^n + 1.
Thinking ring structure alone provides security (without noise, the linear system is easy).
Confusing collision resistance with preimage resistance.

A missed sign flip produces outputs that look plausible but fail interoperability tests against the standard. Assuming the ring alone gives security misses the role of noise: without small errors, Gaussian elimination recovers the secret. Mixing up collision and preimage resistance leads to wrong parameter claims, for example halving a hash length for a use that only needs preimage resistance.

Exercises

EX003 — Ring multiplication. Compute (2 + x)(3 + x³) in Z_17[x]/(x⁴ + 1) by hand and check with Lab R. Rubric: 3 = correct with reduction steps.
EX004 — Hash properties. For each of SLH-DSA, a file-integrity manifest and password storage, state which hash property matters most. Rubric: 3 = correct and justified.

Synthesis

Traditional public-key cryptography hides a period that Shor's algorithm finds; lattice schemes compute in a polynomial ring and hide secrets under noise; hash-based schemes rely only on hash properties.

Continue studying — chapter 02 of 50

← Chapter 01 (draft) · Course chapter index · Chapter 03 (draft) →