PDF Run this chapter's code LaTeX source Comments

Chapter 5From Convolution to Negacyclic Ring Arithmetic

5.1Why this chapter matters#

Polynomial multiplication is the linear operation underlying RLWE and ML-KEM. The important distinction is the modulus: reduction modulo \(x^n-1\) gives cyclic convolution and ordinary circulant matrices, while reduction modulo \(x^n+1\) gives negacyclic convolution. ML-KEM uses the latter.

5.2Two kinds of wrap-around#

Let \(a(x)=\sum_{i=0}^{n-1}a_i x^i\) and \(s(x)=\sum_{j=0}^{n-1}s_j x^j\). Before reduction, the coefficient of \(x^k\) is \[\sum_{i+j=k} a_i s_j.\] For example, \[(1+2x+3x^2)(4+5x)=4+13x+22x^2+15x^3,\] where \(22=2\cdot5+3\cdot4\). This indexing condition, \(i+j=k\), is the ordinary convolution rule.

Now choose a quotient modulus.

• In \(\mathbb{F}_q[x]/(x^n-1)\), \(x^n=1\). A term that wraps past degree \(n-1\) returns with the same sign. This is cyclic convolution.

• In \(\mathbb{F}_q[x]/(x^n+1)\), \(x^n=-1\). A wrapped term returns with the opposite sign. This is negacyclic convolution.

Thus the two structures are related but not interchangeable. The quotient ring used by ML-KEM is \[R_q=\mathbb{Z}_{3329}[x]/(x^{256}+1),\] so its polynomial products are negacyclic.

5.2.1A four-coefficient hand calculation#

Take \(n=4\) and multiply \(a(x)=1+2x+3x^2+4x^3\) by \(s(x)=5+6x+7x^2+8x^3\). Before reduction, the product has degree six. The low-degree coefficients are the same in both quotient rings: \[\begin{aligned} [x^0](as)&=1\cdot5=5, & [x^1](as)&=1\cdot6+2\cdot5=16,\\ [x^2](as)&=1\cdot7+2\cdot6+3\cdot5=34, & [x^3](as)&=1\cdot8+2\cdot7+3\cdot6+4\cdot5=60. \end{aligned}\] The remaining terms are \(53x^4+52x^5+32x^6\). Modulo \(x^4-1\), they return as \(+53,+52x,+32x^2\); modulo \(x^4+1\), they return as \(-53,-52x,-32x^2\). Hence \[\begin{array}{rcl} as\bmod(x^4-1)&=&58+68x+66x^2+60x^3,\\ as\bmod(x^4+1)&=&-48-36x+2x^2+60x^3. \end{array}\] The inputs are identical. The sign of the wrap-around is the only change, but it changes the ring operation.

5.3Matrix representations#

Multiplication by \(a(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}\) is a linear map on coefficient vectors. In the cyclic case it is represented by the circulant matrix \[C(a)_{i,j}=a_{(i-j)\bmod n}.\] In the negacyclic case, the same wrapped coefficient receives a minus sign: \[N(a)_{i,j}=\begin{cases} a_{i-j},&i\ge j,\\ -a_{n+i-j},&i<j. \end{cases}\] For \(n=4\), multiplication by \(a_0+a_1x+a_2x^2+a_3x^3\) modulo \(x^4+1\) has matrix \[N(a)= \begin{bmatrix} a_0&-a_3&-a_2&-a_1\\ a_1&a_0&-a_3&-a_2\\ a_2&a_1&a_0&-a_3\\ a_3&a_2&a_1&a_0 \end{bmatrix}.\] It is therefore inaccurate to call ML-KEM multiplication ordinary circulant multiplication. A polynomial still compactly represents a structured linear map, which is the useful connection to linear algebra.

5.3.1Reading the negacyclic matrix#

The first column of \(N(a)\) is the coefficient vector of \(a(x)\). Moving one column right shifts the entries down, but the coefficient crossing the top boundary is negated. This is precisely \(x^4=-1\) written as a matrix. An ordinary circulant matrix has no minus signs in its upper-right corner and represents multiplication modulo \(x^4-1\).

5.4A reproducible Sage experiment#

The following experiment uses one field, one input vector, and the negacyclic matrix on both sides of the comparison.

q = 17
F = GF(q)
a = vector(F, [1, 2, 3, 4])
s = vector(F, [5, 6, 7, 8])

# Matrix for multiplication by a(x) modulo x^4 + 1.
N = Matrix(F, [[a[(i-j) % 4] if i >= j else -a[(i-j) % 4]
                for j in range(4)] for i in range(4)])

R.<x> = PolynomialRing(F)
Rq = R.quotient(x^4 + 1, 'y')
y = Rq.gen()
ap = sum(a[i]*y^i for i in range(4))
sp = sum(s[i]*y^i for i in range(4))

matrix_product = N * s
ring_product = vector(F, (ap*sp).lift().list() + [0]*4)[:4]
print(matrix_product)
print(ring_product)
print(matrix_product == ring_product)  # True

The sign in the upper-right part of \(N\) is the whole difference between this experiment and a circulant one. Changing \(x^4+1\) to \(x^4-1\) and removing those signs produces the cyclic version.

5.4.1A cyclic comparison#

It is useful to see the conventional circulant case too, provided it is labelled correctly. This version changes both the matrix and the quotient modulus to \(x^4-1\):

C = Matrix(F, [[a[(i-j) % 4] for j in range(4)] for i in range(4)])
Rc = R.quotient(x^4 - 1, 'z')
z = Rc.gen()
ac = sum(a[i]*z^i for i in range(4))
sc = sum(s[i]*z^i for i in range(4))
cyclic_ring_product = vector(F, (ac*sc).lift().list() + [0]*4)[:4]
print(C * s == cyclic_ring_product)  # True

The two experiments are deliberately parallel. Changing the field, input vector, or quotient modulus would no longer test a mathematical equivalence.

5.5What the NTT accelerates#

Transforms can convert a convolution into multiplication in a different representation, but the representation depends on the quotient ring and on the available roots of unity. A full cyclic NTT diagonalizes multiplication modulo \(x^n-1\) when an \(n\)-th root is available. A full negacyclic NTT that evaluates at \(n\) scalar points needs a primitive \(2n\)-th root. ML-KEM does not have such a root for \(n=256\) and \(q=3329\); its partial NTT instead produces 128 quadratic components. Chapter 6 develops that construction.

5.6From one polynomial to a module#

RLWE uses ring elements, whereas Module-LWE uses vectors and matrices whose entries lie in \(R_q\). For a \(k\times k\) polynomial matrix \(A\) and a polynomial vector \(\mathbf{s}\), \[(A\mathbf{s})_i=\sum_{j=1}^{k}A_{i,j}(x)s_j(x)\quad\text{in }R_q.\] Each scalar-looking product is still negacyclic polynomial multiplication. The module structure adds a small matrix layer; it does not turn the ring operation back into ordinary cyclic convolution.

5.7Checks before moving on#

1. Which quotient relation makes a coefficient wrap back with a minus sign?

2. Why is the upper-right corner of a negacyclic multiplication matrix signed?

3. Why is it invalid to compare a circulant integer-matrix product with a product in \(\mathbb{F}_{17}[x]/(x^4+1)\)?

4. What root-of-unity condition would be needed to represent negacyclic products by scalar evaluations?

5.8Summary#

The ordinary circulant/cyclic-convolution picture is useful background, but ML-KEM follows the negacyclic path shown above.