NTT - Transformation of Polynomials in Kyber

Question

In Kyber with $q=3329$, we end up with a field that das 256th roots of unity, when we apply the chinese remainder theorem (CRT) for such a field, it may look like, according to a post here:

$$\mathbb{F}_{3329}[x]/(x^{256}+1)\cong\prod_{i=0}^{127}\mathbb{F}_{3329}[x]/(x^2-\zeta^{2i+1}),$$

My question is, why we can then transform a polynomial $f(x)=\sum_{i=0}^{255}f_ix^i$ into a list say e.g.

$$\hat{f}=(\hat{f}_{2i}+x\hat{f}_{2i+1})_{i=0}^{127}.$$

The isomorphism suggests that we are dealing with polynomials with degree $\leq 1$ and there are 128 of such polynomials, so that would give us something like $(a_i+xb_i)_{i=0}^{127}$.

What interests me is how the NTT comes into play here so that we have this mapping (or how we obtain this mapping): $\hat{f}=(\hat{f}_{2i}+x\hat{f}_{2i+1})_{i=0}^{127}$.

Answer 1

This is explained by the fact that in the linked post, the upper limit in the product is misquoted. Per page 5 of the original Kyber documentation we have $$X^{256}+1=\prod_{i=0}^{127}\left(X^2-\zeta^{2i+1}\right).$$

The transcription error is forgivable as the product runs over odd powers of $\zeta$ less than or equal to 255.

The list $\hat f$ is simply the list of residue polynomials of $f(X)$ with respect to the various factor polynomials $X^2-\zeta^{2i+1}$. Specifically, by the Euclidean division lemma for polynomials we can write $$f(X)=(X^2-\zeta^{2i+1})q_i(X)+r_i(X)$$ for some polynomials $q_i(X)$ and $r_i(X)$ where $\deg r_i(X)<2$. If we write $\hat f_{2i}$ for the constant coefficient in $r_i(X)$ and $\hat f_{2i+1}$ for the coefficient of $X$ in $r_i(X)$, we have the list of linear polynomials that make up $\hat f(X)$. Our original polynomial can be reconstructed from this list using the polynomial Chinese remainder theorem (which can be viewed as a generalisation of Lagrange interpolation).