The Parameters the Standards Actually Use

The chapter has been built on $q = 17$ and $n = 4$. This note gives the real numbers, and explains the one place where ML-KEM cannot run the algorithm as described.

01.The two moduli

Both use $n = 256$, which is the design decision from Module-LWE that lets one transform length serve every parameter set of both standards.

02.ML-DSA: the clean case

For ML-DSA everything works as this chapter described.

The modulus is $q = 2^{23} - 2^{13} + 1 = 8380417$, so

$$q - 1 \;=\; 8380416 \;=\; 2^{13} \cdot 3 \cdot 11 \cdot 31 .$$

The transform needs $2n = 512 = 2^9$ to divide that, and there are thirteen factors of two available. It divides with room to spare.

FIPS 204 fixes $\zeta = 1753$, which has order exactly $512$ modulo $q$. Eight levels of butterflies split a length-$256$ polynomial all the way down to $256$ individual values, pointwise multiplication is genuinely pointwise, and $1024$ butterflies do the work.

The modulus was chosen for this. The form $2^{23} - 2^{13} + 1$ has two properties at once: it has enough factors of two in $q-1$ for the transform, and its sparse binary representation makes reduction modulo $q$ cheap, which Chapter 7 covers.

03.ML-KEM: the incomplete transform

For ML-KEM, $q = 3329$ and

$$q - 1 \;=\; 3328 \;=\; 2^8 \cdot 13 .$$

Eight factors of two. The transform needs nine. As Roots of Unity in a Finite Field established, there is no primitive $512$th root of unity in $\mathbb{F}_{3329}$, so the complete negacyclic transform does not exist here.

A primitive $256$th root does exist, and FIPS 203 uses $\zeta = 17$. Two facts about it are worth checking:

$$17 \text{ has order exactly } 256 \pmod{3329}, \qquad 17^{128} \equiv 3328 \equiv -1 \pmod{3329}.$$

The consequence is that the recursion stops one level early. Seven levels of butterflies instead of eight, splitting the length-$256$ polynomial into $128$ pieces rather than $256$. Each piece is a polynomial of degree less than $2$, meaning a pair of coefficients, rather than a single value.

So the "pointwise" step is not pointwise. Each of the $128$ positions holds a linear polynomial, and combining two of them means multiplying two linear polynomials modulo a quadratic. Concretely, at position $i$ the multiplication is

$$(a_0 + a_1 X)(b_0 + b_1 X) \bmod (X^2 - \gamma_i)$$

for a position-dependent constant $\gamma_i$, which works out to three or four coefficient multiplications rather than one.

That is the incomplete NTT. Every ML-KEM implementation carries it, and the cost is roughly a factor of two against a hypothetical complete transform.

04.Why accept that

The obvious question is why NIST did not pick a slightly different prime.

Because $3329$ is small, and small has consequences everywhere.

A coefficient fits in $12$ bits. A product of two coefficients fits in $24$, which is inside a single $32$-bit register with room for accumulation. On a processor with $256$-bit vector registers, sixteen coefficients are processed per instruction. On a $16$-bit microcontroller the arithmetic still fits without multi-word tricks. In hardware, a $12 \times 12$ multiplier is a small block, and a $256 \times 12$-bit memory is a small memory.

A prime one bit larger, chosen for a friendlier factorisation, would push coefficients to $13$ bits and products to $26$. That is worse in the vector register, worse in the multiplier array, and worse in every memory in the design, on every single operation. The clean transform would have been paid for continuously, everywhere, to save a factor of two in one place.

The committee took the small prime. It is a good illustration of the trade this whole book keeps circling: mathematical convenience losing to implementation cost, deliberately.

05.The twiddle table

One practical detail that matters for both schemes.

The butterflies need powers of $\zeta$, and computing them on demand would mean an exponentiation per butterfly, which would undo the entire saving. Instead the powers are precomputed into a table of $n$ constants, stored in bit-reversed order as The Butterfly and Bit Reversal described, and simply looked up.

For ML-KEM that is $128$ twiddles at $12$ bits each, about $192$ bytes. For ML-DSA it is $256$ twiddles at $23$ bits, under a kilobyte. Both are small enough to sit in a ROM in hardware or a constant array in software, and both standards publish the exact tables so that independent implementations agree bit for bit.

That last point is not a formality. The transform is deterministic, so two correct implementations must produce identical intermediate values, and the published tables are what makes cross-implementation test vectors possible.