中国剩余定理 (CRT)

我们实现NTT时，总是在 整数模质数 $p=2^kq+1$ 域上进行的。原因很简单：为了在 $\mathbb{Z}/p\mathbb{Z}$ 上使用原根以套用复数域 $\mathbb{C}$ 上“单位根”的概念，其阶必然也应当是 $2^k$ 的倍数才行。这就为我们带来了很多不便。假如现在给定一质数 $p’$ 且不保证有 $p’=2^kq+1$，我们就需要另辟蹊径完成卷积。

实现一：中国剩余定理

中国剩余定理：若数 $n$ 的质因数分解为 $\sum_{i=1}^{k}p_i^{e_i}$，有整数模 $n$ 加法群（或者环，随便你怎么叫吧）

$$\mathbb{Z}/n\mathbb{Z}\cong \mathbb{Z}/p_1^{e1}\mathbb{Z}\times \mathbb{Z}/p_2^{e2}\mathbb{Z}\times \cdots \times\mathbb{Z}/p_k^{ek}\mathbb{Z}$$

或者通俗地讲，若 $m_1, m_2, \cdots, m_k$ 两两互质，则线性同余方程组 $$\left\{\begin{aligned} x &\equiv x_1\pmod{m_1}\\ x &\equiv x_2\pmod{m_2}\\ &\quad \vdots\\ x &\equiv x_k\pmod{m_k}\end{aligned}\right.$$ 在 $\bmod \prod_{i=1}^{k}m_i$ 意义下有唯一解。 （更多…）