原根与 NTT

Tangninghaha · 2025-01-10 08:07:29 · 算法·理论

如何得到 n 次单位根

在 FNTT 中，我们并不是用原根来代替单位根，而是利用原根的性质，得到 n 次单位根。

考虑 FTT 中我们需要的单位根具有什么性质：

1. 我们需要知道单位根 \omega_n^0 以及 \omega_n^1。
2. 每一次用当前的单位根 \omega_n^i 乘上 \omega_n^1 即可得到 \omega_n^{i+1}。
3. 进行 n 次操作之后恰好回到 \omega_n^0。
4. 这些单位根互不相同，否则点值会重复，插值会错误。
5. 推导结论时需要用到的一些结论
   1. \omega_n^i\times\omega_n^j=\omega_n^{(i+j)\mod n}
   2. \omega_n^{2i}=\omega_{\frac{n}{2}}^{i}
   3. \omega_n^i+\omega_n^{i+\frac{n}{2}}=0

若 x 模 p 意义下的阶恰好为 n。根据阶的定义 x^{i},0\le i<n 互不相同，且 x^{n}\equiv 1。那么我们设 \omega_{n}^{i}=x^{i}\bmod p，容易验证，除 5.3 以外上述性质全部被满足。如何找到满足 x 模 p 意义下阶为 n 的数呢？

由原根的性质，若模 p 意义下有原根 g，则 g^{k} 的阶数为 \frac{p-1}{(k,p-1)}。我们希望 g^{k} 的阶数恰好为 n，这样就能满足我们上述性质了。

也就是说，n=\frac{p-1}{(k,p-1)}，容易知道，当 n 不是 p-1 的因子时无解；否则，取 k=\frac{p-1}{n}，就能得到 n 了。

所以，我们只需要知道 p 的一个原根，就能得到阶数为任意一个 p-1 的因子的数 x，进而用 x 代替单位根。

性质 5.3 由我们计算方法可以得到。

例如 p=998244353 时，p-1=2^{23}\times 7\times 17，此时 n=2^{k},k\le 23 的所有长度的 n 都存在 n 次单位根，我们就可以解决长度不超过 2^{23}=8388608 的多项式乘法了。

常用原根