NTT 小记

阿罗拉！ / 2023-08-20 / 原文

Pre
阶与原根
参考

数论来力……证明之类的也许会大挂。

或者其实还好，在参考别人的证明思路之后。

Pre

注意到 FFT 中需要复数计算，原因在于涉及到了单位复数根。

有没有替代品？复数域（这是包含实数和虚数的）内暂时没有。

不过我们可以考虑在模意义下找一个。

阶与原根

对于一个正整数 \(n\)，能满足 \(g^k \equiv 1(\mod n)\) 的最小 \(k\) 是 \(g\) 模 \(n\) 的阶，记作 \(\delta_m(g)\)。

阶的一条性质：若 \(g^k\equiv 1(\mod m)\)，则 \(\delta_m(g) \mid k\)。

证明则是把 \(k\) 除掉 \(\delta_m(g)\)，得到 \(g^{q\delta_m(g)+r}\equiv 1(\mod m)\)，然后 \((g^{\delta_m(g)})^q\equiv 1(\mod m)\)，所以若 \(r\ne 0\) 就和阶的最小性矛盾。

对于一个正整数 \(n\)，存在一个 \(g\) 使得 \(\gcd(g,n)=1\) 且 \(\delta_m(g)=\varphi(n)\)，则 \(g\) 称作模 \(n\) 的原根。

下面 \(p\) 为模数。

由于我们要用到不同 \(n\) 下的单位根，我们考虑给原根也配个类似的出来：\(g_n=g^{\frac{p-1}{n}}\)，其中 \(n \mid p-1\)，此时 \(g_n\) 是 \(p\) 的一个原根，且刚好和这个 \(\omega_n\) 意义类似。

证明的话考虑 \(g^k\)，其阶为 \(\frac{p-1}{\gcd(p-1,k)}\)（原因考虑欧拉定理，这里也可以说是费马小定理，把这玩意儿弄到上界），然后我们想要 \(n\) 是这个原根的阶，就可以考虑构造；发现 \(\frac{p-1}{\gcd(p-1,(p-1)/n)}=\frac{p-1}{(p-1)/n}=n\)，所以就取 \(g^{\frac{p-1}{n}}\)。

如果 \(n\nmid p-1\)，发现要求 \(\frac{p-1}{\gcd(p-1,x)}=n\)，也就是说 \(\gcd(p-1,x)=\frac{p-1}{n}\)，那这玩意儿就不是整数了，显然不合法。

然后我们看这个 \(g_n\)，它满足单位根的性质吗？

\(\omega_n^0,\cdots,\omega_n^{n-1}\) 两两不同。

单位根定义，显然。

证明考虑取 \(g_n^i \equiv g_n^j(\mod p)\)，然后两边做差发现同样违背阶得最小性。
\(\omega_{dn}^{dk}=\omega_n^k\)

消去引理。同理，和单位根那一模一样。
\(\left\{(\omega_n^0)^2,\cdots,(\omega_n^{n-1})^2\right\}=\left\{\omega_{n/2}^0,\cdots,\omega_{n/2}^{n/2-1}\right\}\)

折半引理，这里比较棘手。

首先说明 \(g_n^k=g_n^{k+n/2}\)，考虑两边分别平分，有 \(g_n^{2k}=g_{n}^{2k+n}\)。显然其中 \(g_n^n=(g^{\frac{p-1}{n}})^{n}=g^{p-1}=1\)，故成立。

然后就说好了，这玩意儿显然了，也不棘手。
\(\sum\limits_{k=0}^{n-1}(\omega_n^d)^k=\frac{(\omega_n^d)^n-1}{\omega_n^d-1}\)，要求 \(d\nmid n\)

有没有可能我们最先在整数域上学的等比数列这玩意儿。