Roots of Unity in a Finite Field

The classical Fast Fourier Transform evaluates at complex numbers $e^{2\pi i k / n}$. There are no complex numbers in $\mathbb{Z}_q$. This note finds replacements inside the field itself, and discovers a condition on $q$ that decides whether the whole method is available at all.

01.What we are looking for

An element $\omega$ of $\mathbb{Z}_q$ is a primitive $m$th root of unity when

$$\omega^m = 1, \qquad \text{and} \qquad \omega^j \neq 1 \text{ for every } 0 < j < m .$$

The first condition says $\omega$ returns to $1$ after $m$ steps. The second says it does not do so any earlier. The number $m$ is called the order of $\omega$.

The second condition matters as much as the first. The element $1$ satisfies $1^m = 1$ for every $m$ and is useless, because its powers are all the same value and evaluating at the same point $n$ times determines nothing.

02.When they exist

Theorem. The non-zero elements of $\mathbb{F}_q$ under multiplication form a cyclic group of order $q - 1$. It contains an element of order $m$ if and only if $m$ divides $q - 1$.

Cyclic means there is a single element $g$, called a generator, whose powers $g^0, g^1, \ldots, g^{q-2}$ run through every non-zero element exactly once. Given a generator, an element of order $m$ is

$$\omega \;=\; g^{(q-1)/m},$$

and that exponent is a whole number precisely when $m$ divides $q - 1$. That is the whole content of the theorem.

Working it out in $\mathbb{F}_{17}$

Take $q = 17$, so $q - 1 = 16$. The divisors of $16$ are $1, 2, 4, 8, 16$, so $\mathbb{F}_{17}$ contains primitive roots of unity of exactly those orders and no others. There is no primitive cube root of unity in $\mathbb{F}_{17}$, because $3$ does not divide $16$.

A generator is $3$. Its powers, which appeared in Chapter 2, are

$$3,\; 9,\; 10,\; 13,\; 5,\; 15,\; 11,\; 16,\; 14,\; 8,\; 7,\; 4,\; 12,\; 2,\; 6,\; 1,$$

which is all sixteen non-zero residues, confirming it generates.

So a primitive $8$th root is $3^{16/8} = 3^2 = 9$, and a primitive $4$th root is $3^{16/4} = 3^4 \equiv 13$.

But $9$ is not the only element of order $8$. Check $2$:

$$2^1 = 2, \quad 2^2 = 4, \quad 2^4 = 16 \equiv -1, \quad 2^8 = 256 \equiv 1 \pmod{17}.$$

The value $2^8 = 1$ shows the order divides $8$, and $2^4 = -1 \neq 1$ rules out order $4$ or less. So $2$ has order exactly $8$ as well, and it is the one this chapter uses, because its powers are pleasant to compute with by hand.

04.The negacyclic requirement

Evaluation and Interpolation ended on a mismatch. The natural construction computes modulo $X^n - 1$, and $R_q$ needs modulo $X^n + 1$.

The fix is to evaluate not at the $n$th roots of unity but at the roots of $X^n + 1$, which are the elements whose $n$th power is $-1$ rather than $+1$.

Here is where to find them. Let $\zeta$ be a primitive $2n$th root of unity. Then $\zeta^{2n} = 1$, so $(\zeta^n)^2 = 1$, so $\zeta^n$ is either $+1$ or $-1$. It cannot be $+1$, because that would make the order at most $n$ rather than $2n$. Therefore

$$\zeta^n = -1 .$$

Now take the odd powers $\zeta^1, \zeta^3, \zeta^5, \ldots, \zeta^{2n-1}$. Each raised to the $n$th power gives

$$(\zeta^{2k+1})^n \;=\; (\zeta^n)^{2k+1} \;=\; (-1)^{\text{odd}} \;=\; -1 .$$

So all $n$ of them are roots of $X^n + 1$, and they are distinct because $\zeta$ has order $2n$.

Those are the evaluation points. Evaluating at the roots of the reduction polynomial is what makes the reduction invisible to the transform, and therefore what makes pointwise multiplication compute the correct negacyclic product.

The requirement is now explicit:

$$2n \;\text{ must divide }\; q - 1 .$$

Check it for the running example. With $n = 4$, we need $8 \mid 16$, which holds, and $\zeta = 2$ is the primitive $8$th root found above. The four evaluation points are

$$\zeta^1 = 2, \qquad \zeta^3 = 8, \qquad \zeta^5 = \zeta^4 \zeta = (-1)(2) \equiv 15, \qquad \zeta^7 = \zeta^4 \zeta^3 = (-1)(8) \equiv 9 .$$

Verify each is a root of $X^4 + 1$ modulo $17$:

$$2^4 = 16 \equiv -1, \qquad 8^4 \equiv -1, \qquad 15^4 \equiv (-2)^4 = 16 \equiv -1, \qquad 9^4 \equiv (-8)^4 \equiv -1 .$$

All four check out. The evaluation grid is $(2, 8, 15, 9)$.

The $q = 3329$ quirk

Now apply the same test to the modulus ML-KEM actually uses, and it fails.

For ML-KEM, $q = 3329$ and $n = 256$. Then

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

The requirement is that $2n = 512 = 2^9$ divides $3328$. It does not, because $3328$ carries only eight factors of two and $512$ needs nine.

So $\mathbb{F}_{3329}$ contains no primitive $512$th root of unity, and the full length-$256$ negacyclic transform this chapter is building does not exist for ML-KEM's parameters.

What does exist is a primitive $256$th root, since $256 = 2^8$ divides $3328$ exactly. FIPS 203 uses $\zeta = 17$, and it can be checked that $17$ has order exactly $256$ modulo $3329$, with $17^{128} \equiv 3328 \equiv -1$.

That is enough to run the transform for seven levels instead of eight. Rather than splitting all the way down to $256$ single values, the recursion stops one level early, leaving $128$ polynomials of degree less than $2$. Pointwise multiplication is then not quite pointwise: each of the $128$ pairs is a small product of linear polynomials rather than a single coefficient multiplication.

This is the incomplete NTT, and every ML-KEM implementation in existence carries it. It costs roughly a factor of two against what a complete transform would achieve.

It is reasonable to ask why NIST accepted a modulus that does not quite fit. The answer is that $3329$ is small, small enough that a product of two residues fits in $24$ bits and a coefficient in $12$. That keeps multipliers narrow, keeps memory small, and keeps vectorised software fast. A modulus one bit larger with a friendlier factorisation would have paid for its clean transform everywhere else.

06.ML-DSA has no such problem

For ML-DSA, $q = 2^{23} - 2^{13} + 1 = 8380417$, and

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

Thirteen factors of two, and only nine are needed. So $512 \mid q - 1$ comfortably, a primitive $512$th root exists, FIPS 204 uses $\zeta = 1753$, and the complete length-$256$ negacyclic transform runs exactly as described in this chapter.

The modulus was chosen with the transform in mind, which is what the special form $2^{23} - 2^{13} + 1$ is for. It also makes reduction cheap, as Chapter 7 will show.

With the evaluation points in hand, the next note defines the transform and computes one.