2
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ @TreeBook1 I've added some detail about the transformation and its inverse. $\endgroup$
    – Daniel S
    Commented Nov 21, 2023 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.