Chinese Remainder Theorem (CRT)

In the last post, I discuss how to compute NTT under a finite field.

But as 从多项式乘法到快速傅里叶变换 post mentioned, sometimes you will be asked to compute modulus under a number that might not be prime.

In this case, you must use Chinese Remainder Theorem, that is, use multiple prime numbers $p_1, p_2, ..., p_k$ such that $p_1 \cdot p_2 \cdot ... p_k$ is larger than the required number.

Theorem

Let

There exists a unique $x \in [0, P)$,

where

and

Proof

Because

Therefore, the only thing we need to verify is:

Practical Suggestion

In practice, you can just choose two $p_1, p_2$ to perform NTT and then you CRT to restore the original coefficient!