和上一篇 FFT 一样,其实还是复习笔记。
Part0. 参考资料
Tiw_Air_OAO 的 多项式乘法总结
Hint. 因为我上一篇博客写了 FFT,关于 FFT 的东西就不再赘述……
Part1. From FFT to NTT
FFT虽然跑得快,但是因为是浮点数运算,终究还是有 精度、常数 等问题。 - Tiw_Air_OAO
而且处理模数还比较麻烦……
于是就引入了 NTT —— 在模的意义下(多项式的系数对某数取模)将多项式和点值表达之间等价转化。分析 FFT 必须用到 double,会卡精度的原因,发现主要是 单位复根 在大多数情况下是一个涉及浮点数的复数。
NTT 即考虑在模的意义下,用别的东西来替换掉单位复根……
Part2. 原根
对于素数 $p$,定义它的原根为 $G^0,G^1,G^2,…,G^{p-2}$ 使得这 $p-1$ 个数互不相同(其中 $G$ 是整数)。
再根据原根定义出:对于一个 $n-1$ 次多项式(也就是 $n$ 项的多项式), $g_n^k=(G^{\frac {p-1}n})^k\bmod p$($k=0\text ~(n-1)$)。其中需要保证 $\frac{p-1}n$ 是一个整数 ——
只要学过 FFT,应该会知道一定要先把多项式的项数改为一个 $2$ 的幂才能 FFT ——
NTT 也一样,所以 $n$ 很有可能是一个比较大的 $2$ 的幂,要使得 $\frac {p-1}n$ 是整数,那么 $p-1$ 就需要包含很多个因子 $2$,但是这样的 $p$ 并不多。这就造成了 NTT 的实际应用非常受限……
那么我们能否用 $g_n^k$ 来替换掉单位复根?这需要检验它在模意义下是否具有单位复根在 FFT 中的全部性质……
Part2/1. 与单位复根的相似性
在 FFT 中,我们总共用到了单位复根的这些性质:
- $n$ 个单位复根互不相同;
- $\omega_n^k=\omega_{2n}^{2k}$;
- $\omega_n^{k}=-\omega_n^{k+n/2}$;
- $\omega_n^a\times\omega_n^b=\omega_n^{a+b}$。
于是再来检验一下 $g_n^k$ 的性质:
根据原根的定义,$g_n^k$ 也互不相同;
$g_{2n}^{2k}=(G^{\frac{p-1}{2n}})^{2k}=(G^{\frac{p-1}{n}})^k=g_n^k$;
$g_n^{k+n/2}=(G^{\frac{p-1}n})^{k+n/2}=(G^{\frac{p-1}n})^k\cdot(G^{\frac{p-1}2})=g_n^k\cdot G^{\frac{p-1}2}$;
因为 $(G^{\frac{p-1}2})^2=G^{p-1}=1$ (费马小定理)
然后又根据原根的定义 $G^{\frac{p-1}2}\not=G^{p-1}$;
所以得到 $G^{\frac{p-1}2}=-1$;
所以 $g_n^{k+n/2}=-g_n^k$;
$g_n^a\times g_n^b=(G^{\frac{p-1}n})^a\times(G^{\frac{p-1}n})^b=(G^{\frac{p-1}n})^{a+b}=g_n^{a+b}$;
开心的发现它具有单位复根的所有性质~
Part2/2. 常见的NTT模数及其原根
最为常见的 $998244353$ (建议背住),原根是 $3$;但是并不一定出现这个质数就是 NTT……
Copy 自 “not_exist” 的博客 [CSDN
质数 | 原根 |
---|---|
3 | 2 |
5 | 2 |
17 | 3 |
97 | 5 |
193 | 5 |
257 | 3 |
7681 | 17 |
12289 | 11 |
40961 | 3 |
65537 | 3 |
786433 | 10 |
5767169 | 3 |
7340033 | 3 |
23068673 | 3 |
104857601 | 3 |
167772161 | 3 |
469762049 | 3 |
998244353 | 3 |
1004535809 | 3 |
2013265921 | 31 |
2281701377 | 3 |
3221225473 | 5 |
75161927681 | 3 |
77309411329 | 7 |
206158430209 | 22 |
2061584302081 | 7 |
2748779069441 | 3 |
6597069766657 | 5 |
39582418599937 | 5 |
79164837199873 | 5 |
263882790666241 | 7 |
1231453023109120 | 3 |
1337006139375610 | 3 |
3799912185593850 | 5 |
4222124650659840 | 19 |
7881299347898360 | 6 |
31525197391593400 | 3 |
180143985094819000 | 6 |
1945555039024050000 | 5 |
4179340454199820000 | 3 |
Part3. 源代码
打包成了一个 namespace
……
1 | namespace NTT{ |
The End
Thanks for reading!
Email: lucky_glass@foxmail.com,欢迎提问~