# 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!