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.
There exists a unique ,
Therefore, the only thing we need to verify is:
In practice, you can just choose two to perform NTT and then you CRT to restore the original coefficient!