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 such that is larger than the required number.

Theorem

Let

There exists a unique ,

where

and

Proof

Because

Therefore, the only thing we need to verify is:

Practical Suggestion

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

References