# NTT - Transformation of Polynomials in Kyber

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}$$.

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).