NTT

作者: ffacs 分类: 总结 发布时间: 2020-05-09 17:48

在 $\text{FFT}$ 中,我们使用复数的单位根进行 $DFT$,这样会产生浮点数误差。对于只有整数参与的多项式运算,我们需要找到正好的方法。

引入

考虑 $\text{FFT}$ 的时候我们为什么选择使用复数单位根。
$$
\begin{align}
&1.\quad\omega_n^t(0\leq t <n)互不相同 &\qquad 这保证了代入的值不同\\
&2.\quad\omega_{2n}^{2t}=\omega_n^t&\qquad 这用于\text{DFT}的递归 \\
&3.\quad\omega_n^{t+n/2}=-\omega_n^{t}&\qquad 这也用于\text{DFT}的递归 \\
&4.\quad1+\omega_n^k+(\omega_n^{k})^2+(\omega_n^{k})^3…+(\omega_n^{k})^{n-1}=0\ (k \neq 0) &\qquad 这用于将\text{IDFT}规约到\text{DFT} \\
\end{align}
$$
如果有一类数有类似的性质的话好了。于是有人发现原根能够胜任这个任务。在数论中对于一个素数 $p$ ,他的一个原根 $g$ 被定义为 使得 $g,g^2,g^3…g^{\phi(p)}$ 两两模 $p$ 不同余的数。也就是 $ord_pg=\phi(p)=p-1$。

性质

我们假设一个素数 $p$ 可以被写作 $q*2^k+1$。$g$ 是 $p$ 的一个原根。令 $\omega_{2^k}^1=g^q$

  1. $\omega_{2^k}^t=g^{qt}$, 所以当$0\leq t <2^k 时,0\leq qt2^k$。根据原根的定义,两两 模 $p$ 不同余。
  2. $\omega_{2^{k+1}}^{2t}=g^{\frac{q}{2}*2t}=\omega_{2^k}^t$
  3. 根据费马小定理可知 $g^{\phi(p)}=g^{p-1}=g^{q2^k}=\omega_{2^k}^{2^k} \equiv 1 (\bmod p)$ ,那么 $\omega_{2^k}^{2^{k-1}} \equiv \pm 1 (\bmod p)$,又因为 $\omega_{2^k}^0=1$ 和性质1,得到 $\omega_{2^k}^{2^{k-1}}\equiv -1 (\bmod p)$,所以$\omega_{2^k}^{t+2^{k-1}} = \omega_{2^k}^t*\omega_{2^k}^{2^{k-1}} \equiv -\omega_{2^k}^t$
  4. $$
    \begin{align}
    S(k)&=1+\omega_n^k+(\omega_n^{k})^2+…+(\omega_n^{k})^{n-1}\\
    \omega_n^kS(k)&=\omega_n^k+(\omega_n^{k})^2+(\omega_n^{k})^3…+(\omega_n^{k})^{n} \\
    (\omega_n^k-1)S(k)&=(\omega_n^{k})^{n}-1 \\
    S(k)&=\frac{(\omega_n^{k})^{n}-1}{\omega_n^k-1}
    \end{align}
    $$ 因为 $\omega_n^{nk}\equiv1 (\bmod p)$ ,所以 $S(k) \equiv 0 (\bmod p)$

注意到以上性质在$\mod p$ 的条件下成立,所以我们可以用这些性质求出多项式 $f(x)$ 在$\mod p$ 下的点值对。同时也能通过点值对 $\text{IDFT}$ 出 $\mod p$ 意义下对应的多项式

求原根

对一个素数 $p$ 我们要想求出其一个原根可以采用枚举法。对于一个素数 $a$ ,若 $a^l \equiv 1 (\bmod p)$ 且 $l\neq p-1$,则 $a$ 不是 $p$ 的原根。同时,若 $a^l \equiv 1 (\bmod p)$ 则有 $l \mid p-1$。具体证明见 原根 一节。所以我们只要枚举 $p-1$的因子$q$,检验是否有 $g^q \equiv 1 (\bmod p)$ 即可。

常见的原根

$$
p=1004535809=4792^{21}+1,g=3 \\ p=998244353=717*2^{23},g=3
$$

发表评论

电子邮件地址不会被公开。 必填项已用*标注