Exercises

1. Does $\mathbb{F}_{97}$ support a length-8 transform?

Let $q = 97$ and $n = 8$. Does $\mathbb{F}_{97}$ contain a primitive $16$th root of unity? Find one if so.

Answer. The condition from Roots of Unity in a Finite Field is $2n \mid q - 1$. Here $q - 1 = 96 = 2^5 \cdot 3$, and $2n = 16 = 2^4$ divides it. So yes.

To find one, take a generator of $\mathbb{F}_{97}^{\times}$ and raise it to the power $96/16 = 6$. The element $5$ is a generator, and $5^6 = 15625 \equiv 8 \pmod{97}$.

Check the order of $8$: $8^8 \equiv 96 \equiv -1$, and $8^{16} \equiv 1$. Since $8^8 \neq 1$, the order is exactly $16$.

So $\zeta = 8$ works, and the eight evaluation points for a negacyclic transform are its odd powers modulo $97$: $8, 27, 79, 12, 89, 70, 18, 85$. Each raised to the eighth power gives $96 \equiv -1$, confirming they are the roots of $X^8 + 1$.

02.2. ML-KEM's evaluation points

For $q = 3329$, $n = 256$, $\zeta = 17$, describe the evaluation points of ML-KEM's length-128 transform and explain why there are half as many as a length-256 transform would use.

Answer. $\zeta = 17$ has order exactly $256$, not $512$, because $3329 - 1 = 2^8 \cdot 13$ has only eight factors of two.

A complete length-256 negacyclic transform would need a primitive $512$th root and would evaluate at its $256$ odd powers. No such root exists here.

What is available is the $128$ points $\zeta^{1}, \zeta^{3}, \ldots, \zeta^{255}$, the odd powers of a $256$th root. Each satisfies $(\zeta^{2j+1})^{128} = (\zeta^{128})^{2j+1} = (-1)^{\text{odd}} = -1$, so they are the $128$ roots of $X^{128} + 1$.

Evaluating at $128$ points splits the degree-255 polynomial into $128$ pieces of degree less than $2$, not $256$ pieces of degree less than $1$. That is the incomplete transform, and the missing level is exactly the one the absent factor of two would have provided.

03.3. Run the butterflies

Run the Cooley-Tukey forward transform on $(3, 1, 4, 2)$ over $\mathbb{F}_{17}$ with $\zeta = 2$, then bit-reverse and check against direct evaluation.

Answer. Worked in full in The Butterfly and Bit Reversal. Level one uses twiddle $4$ and pairs entries two apart, giving $(2, 9, 4, 10)$. Level two uses twiddles $2$ and $8$ on adjacent pairs, giving $(3, 1, 16, 9)$.

Bit-reversing two-bit indices swaps positions 1 and 2, turning $(3, 1, 16, 9)$ into $(3, 16, 1, 9)$, which is the direct evaluation from The Negacyclic NTT.

Four butterflies, four multiplications, against sixteen for direct evaluation. At $n = 4$ that is a tie once the twiddle setup is counted, which is the honest caveat from the overview.

04.4. Invert the transform

Apply the inverse transform to $(9, 8, 16, 5)$ and confirm it gives $(1, 4, 5, 6)$.

Answer. The inverse from The Negacyclic NTT is

$$a_j \;=\; \frac{1}{n}\,\zeta^{-j} \sum_{k=0}^{n-1} \hat{a}_k \zeta^{-2jk} .$$

Here $n^{-1} = 4^{-1} \equiv 13 \pmod{17}$ and $\zeta^{-1} = 2^{-1} \equiv 9 \pmod{17}$.

Carrying out the four sums gives $(1, 4, 5, 6)$, which is $a \cdot b$ computed directly in $\mathcal{R}_{17}$ in that same note.

The $\zeta^{-j}$ prefactor is what distinguishes this from an ordinary inverse DFT. Dropping it produces a cyclic rather than negacyclic result, and the symptom is that the answer is right in its first half and wrong in its second.

05.5. The negacyclic circulant

Write out the negacyclic circulant of $a(X) = 5 + 6X + 7X^2 + 8X^3$ in $\mathcal{R}_{17}$ and verify it against the polynomial product with $s(X) = 1 + 2X + 3X^2 + 4X^3$.

Answer. Built in Ring-LWE:

$$\operatorname{circ}_-(a) = \begin{pmatrix} 5 & -8 & -7 & -6 \\ 6 & 5 & -8 & -7 \\ 7 & 6 & 5 & -8 \\ 8 & 7 & 6 & 5 \end{pmatrix}.$$

Multiplying by $s = (1,2,3,4)$ and reducing modulo $17$ gives $(12, 15, 2, 9)$, which is exactly $a \cdot s$ computed as a polynomial product with $X^4 = -1$.

The sign pattern is the reduction rule showing up as matrix structure. Each column is the previous one shifted down with the wrapped entry negated.

06.6. How many equations does one Module-LWE sample carry?

Show that Module-LWE with rank $k$ and degree $n$ gives $k \cdot n$ scalar equations per sample, and compare with plain LWE.

Answer. A Module-LWE sample is $(\mathbf{a}, b)$ with $b \in R_q$ a single polynomial. Each of its $n$ coefficients is one scalar equation in the unknown coefficients of $\mathbf{s}$, of which there are $k \cdot n$. So one sample yields $n$ equations in $kn$ unknowns.

Note this is $n$ equations per sample, not $kn$. The $k$ enters as the number of unknowns, so roughly $k$ samples are needed before the system is determined.

Compare the storage. Plain LWE producing $n$ equations in $kn$ unknowns needs $n$ separate vectors of length $kn$, so $kn^2$ stored values. Module-LWE needs $\mathbf{a}$, which is $k$ polynomials, so $kn$ values. A factor of $n$, which is the compression from Ring-LWE.

07.7. Butterfly gate count

Estimate the two-input XOR gates in one radix-2 butterfly over $\mathbb{F}_q$ with $q < 2^{23}$, given an external multiplier.

Answer. With the multiplication provided, the butterfly is $A' = A + tB$ and $B' = A - tB$, so what remains is one modular addition and one modular subtraction on 23-bit values, plus the reduction.

A 23-bit ripple-carry adder is 23 full adders, and a full adder is two XORs plus supporting gates, so about $46$ XOR gates per adder. Subtraction is an addition with an inverted operand, so another $46$ plus the inversion.

Modular addition needs a conditional subtraction of $q$, which is a second adder plus a select, roughly doubling it. So the order of magnitude is $200$ to $250$ two-input XOR gates per butterfly, exclusive of the multiplier and its reduction.

The figure is an estimate rather than a synthesis result, and the point of computing it is the ratio rather than the number: the multiplier and its reduction dominate, which is why Chapter 7 is about reduction and not about adders.