Skip to main content

📜 Recipes That Loop

Understanding Polynomial Rings​

🎯 The Simple Story​

Imagine a recipe card that says:

"1. Take 3 cups flour 2. Take 2 teaspoons salt
3. Mix together 4. Step 6: Go back to step 2"

This recipe loops back on itself!

The same thing happens in polynomial rings - but with numbers, not ingredients!

🧠 Mental Model​

Hold this picture in your head:

Polynomial: a₀ + a₁x + a₂x² + a₃x³ + ... (list of coefficients)

Problem: This goes on forever!

Solution: Make it loop back!

Polynomial ring: When you reach xⁿ, you're back at constants!

Example for x⁴ + 1 = 0:
    x⁷ = x³ (looped: x⁴ = 1, so x⁵ = x, x⁶ = x², x⁷ = x³)

Think of it like:

🔄 Circular number system - Like a clock, but for powers of x

🎯 Rule book - "When you get to x⁴, replace it with 1"

🏁 Bounded recipes - No matter how long the polynomial, you always have the same size!

📊 See It Happen​

Let's see how polynomials simplify in rings:

🎮 Try It Yourself​

Question 1: In the ring with rule x³ = x, what's x⁵?

Show Answer

Rule: x³ = x

Let's apply repeatedly:

x⁴ = x³·x = x·x = x² (substituted x³ with x again) x⁵ = x⁴·x = x²·x = x³ = x (substituted x³ with x)

Answer: x⁵ = x (power reduced dramatically!)

Question 2: Simplify 3x⁶ - x⁴ + 2 with rule x² = 1

Show Answer

Rule: x² = 1

Apply to each term:

  • x⁶ = (x²)³ = 1³ = 1
  • x⁴ = (x²)² = 1² = 1
  • Constant 2 stays 2

So: 3(1) - 1(1) + 2 = 3 - 1 + 2 = 4

Answer: Constant 4 (all x terms disappeared!)

Question 3: If the rule is x⁴ + x³ + x² + x + 1 = 0, what's x⁵?

Show Answer

Rule: x⁴ + x³ + x² + x + 1 = 0

Rearrange to solve for highest power: x⁴ = -(x³ + x² + x + 1)

Now compute x⁵: x⁵ = x·x⁴ = x·(-(x³ + x² + x + 1)) = -(x⁴ + x³ + x² + x) = -((-(x³ + x² + x + 1)) + x³ + x² + x) = -(-x³ - x² - x - 1 + x³ + x² + x) = -( -1 ) = 1

Answer: x⁵ = 1 (surprising, but true!)

🔢 The Math​

Polynomial Notation​

A polynomial is a sum of monomials:

p(x)=a0+a1x+a2x2+a3x3+⋯+an−1xn−1p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \dots + a_{n-1}x^{n-1}

Where:

  • aia_i = Coefficients 0 to q-1
  • x = Variable (indeterminate)
  • n = Degree (highest power before wrapping)

Example: p(x)=3+5x−2x2+x3p(x) = 3 + 5x - 2x^2 + x^3 =(3,5,−2,1)= (3, 5, -2, 1) (coefficient notation)

Polynomial Ring Notation​

Mathematicians write polynomial rings like this:

Rq=Zq[x]/(xn+1)R_q = \mathbb{Z}_q[x]/(x^n + 1)

Breaking it down:

  • Zq[x]\mathbb{Z}_q[x] = Polynomials with coefficients modulo q
  • (xn+1)(x^n + 1) = The "wrapping rule" (divisor)
  • RqR_q = The ring structure

ML-KEM's ring: R3329=Z3329[x]/(x256+1)R_{3329} = \mathbb{Z}_{3329}[x]/(x^{256} + 1)

So:

  • Coefficients: 0 to 3328 (mod 3329)
  • Rule: x²⁵⁶ = -1 (or x²⁵⁶ = 3328)
  • Polynomials: Always bounded to degree 255!

Why xⁿ + 1?​

Special property: Powers alternate

xⁿ = -1, so xn+1=−xx^{n+1} = -x, xn+2=−x2x^{n+2} = -x², etc.

Benefits:

  1. Alternating pattern = easier to implement
  2. Enables Number Theoretic Transform (NTT) = fast multiplication
  3. Coefficients don't explode = easier to work with

ML-KEM specific rule: x²⁵⁶ + 1 = 0 → x²⁵⁶ = 3328 (since -1 ≡ 3328 in centered mod 3329)

💡 Why We Care​

Problem: Polynomials Grows to Infinity​

Without rings: p(x)=1+x+x2+x3+...p(x) = 1 + x + x² + x³ + ... Keeps going forever!

With rings: p(x)=1+x+x2+...+xn−1p(x) = 1 + x + x² + ... + x^{n-1} (bounded! always degree n−1n-1)

Solution: Use polynomial rings to keep polynomials bounded!

Operation Speed​

Naïve polynomial multiplication: Two degree-255 polynomials → O(n2)O(n²) = 65,536 operations

With NTT (enabled by xⁿ + 1 structure): Same multiplication → O(nlog⁡n)O(n \log n) ≈ 2048 operations

Speedup: ~32× faster!

ML-KEM's Polynomial Use Case​

ML-KEM uses polynomials in its matrix operations:

As+e=t\mathbf{A} \mathbf{s} + \mathbf{e} = \mathbf{t}

Each entry is:

  • Matrix A: 256 coefficients (0 to 3328)
  • Vector s: 256 coefficients (0 to 3328)
  • Vector e: 256 coefficients (small errors)
  • Vector t: 256 coefficients (result)

All polynomials live in R3329R_{3329}!

This means:

  • Coefficients: 0, 1, 2, ..., 3328 (bounded by mod 3329)
  • Degree: 0, 1, 2, ..., 255 (bounded by x²⁵⁶ = -1)
  • Size: Always 256 coefficients = 3072 bits = 384 bytes

✅ Quick Check​

Can you explain polynomial rings to a 5-year-old?

Try saying this out loud:

"Imagine a recipe card that says 'go back to step 2' at the end. No matter how long the recipe is, you always follow the same rule and end up back at the start. Polynomial rings are like that - they make sure your polynomials never get too big!"

Can you work with polynomial ring rules?

Try this example:

Ring: R₁₀ = ℤ₁₀[x]/(x³)

Simplify: x⁸ - 2x⁵ + x² + 3

Using x³ = 0:

  • x⁸ = (x³)² · x² = 0 · x² = 0
  • x⁵ = x³ · x² = 0 · x² = 0

So: 0 - 0 + x² + 3 = x² + 3

Answer: x² + 3 (degree 2, not degree 8!)

🎓 Key Takeaways​

✅ Polynomial ring = Bounded polynomials (wrapping rule) ✅ Notation = Rq=Zq[x]/(divisor)R_q = \mathbb{Z}_q[x]/(\text{divisor}) or simply Rmodulus[x]/(xn+1)R_{\text{modulus}}[x]/(xⁿ + 1) ✅ Benefits = Bounded size, NTT speedup ✅ ML-KEM uses = R3329R_{3329} with x²⁵⁶ = -1 rule ✅ Polynomials = Always 256 coefficients × 384 bytes ✅ Structure = Enables fast operations and prevents overflow

🎉 What You'll Learn Next​

Now you understand polynomial rings! Next, we'll learn about the hard problem that protects ML-KEM:

🗺️ The Foggy Map Puzzle → MLWE Problem

Why adding small errors makes finding secrets impossible!