以下涉及到的运算如无特殊说明均为模 \(p\) 意义下的运算

阶与原根

我们把最小的满足 \(a^x\equiv1\) 的正整数 \(x\) 称为 \(a\) 在模 \(p\) 意义下的阶。

如果 \(a\not\perp p\)，则 \(a\) 的阶不存在。这是因为 \(a,p\) 均有 \((a,p)\) 这个因子，所以 \(a^x-kp\) 也一定含有 \((a,p)\) 这个因子，不可能为 \(1\)。

而如果 \(a\perp p\)，由欧拉定理，\(a^{x}\equiv a^{x\%\varphi(p)}\)，即 \(a^{\varphi(p)}\equiv 1\)。故 \(a\) 的阶小于等于 \(\varphi(p)\)。如果 \(a\) 的阶等于 \(\varphi(p)\)，则称 \(a\) 为 \(p\) 的原根。有些数是不存在原根的，比如 15。存在原根的数一定形如 \(2,4,p^c,2p^c\)（不会证）。设 \(g\) 为 \(p\) 的一个原根，则 \(g^i\) 等价于 \(p\) 的简化剩余系。即 \(g^i\) 能取到模 \(p\) 意义下所有与 \(p\) 互质的数，这点由阶的定义易证。于是 \(g^i\) 构成了一个大小为 \(\varphi(p)\) 的环，同时，每个与 \(p\) 互质的数都能表示成 \(g\) 的幂的形式。

对于 \(g^x\)，其阶为 \(\frac{\varphi(p)}{\gcd(x,\varphi(p))}\)，这点是因为 \(g^x\) 不断乘自己相当于在环上挑一个出发点不断跳 \(x\) 步，显然首次回到出发点是在跳了 \(\frac{\varphi(p)}{\gcd(x,\varphi(p))}\) 次之后。于是当 \(\gcd(x,\varphi(p))=1\) 时 \(g^x\) 的阶为 \(\varphi(p)\)，也是 \(p\) 的原根。 这表明 \(p\) 的原根有 \(\varphi(\varphi(p))\) 个，由于 \(\varphi(p)\) 和 \(p\) 几乎是同一量级，所以 \(p\) 的原根相当稠密，有个很松的上界是 \(O(p^{0.25})\)，也就是说前 \(O(p^{0.25})\) 个自然数里必然至少含有一个原根。同时这也表明所有与 \(p\) 互质的数的阶都是 \(\varphi(p)\) 的约数（时刻不要忘记，与 \(p\) 不互质的数是没有阶的），这使得快速验证一个数是否是 \(p\) 的原根成为可能。

具体地，如果要验证 \(x\) 是不是 \(p\) 的原根，我们可以只枚举 \(\varphi(p)\) 的所有质因子 \(p_1,p_2……p_k\)，然后依次判断 \(x\) 的 \(\frac{\varphi(p)}{p_i}\) 次方是否等于 \(1\)。这是正确的，因为它覆盖到了 \(\varphi(p)\) 除本身以外的所有约数。这样我们就可以不断从小到大枚举找到最小的原根，然后根据 \(g^x(x\perp p)\) 也是原根的性质 \(O(p\log p)\) 地求出所有原根。

原根与单位根

FFT 涉及到大量浮点数运算，精度严重丢失，这是不好的。而且 OI 总喜欢把一些东西膜来膜去你复数岂不是太碍眼了。所以我们考虑用模意义下的某些东西代替复数域上的单位根。

还记得单位根的几何意义吗？它是把复平面上的单位圆均分成 \(n\) 份。而在模 \(p\) 意义下的原根 \(g\) 的所有幂组成了一个大小为 \(\varphi(p)\) 的环，我们可以考虑把这个环看做圆，把环均分成 \(n\) 份作为模意义下的“\(n\) 次单位根”，即 \(g^{\frac{\varphi(p)}{n}}\)。你会惊喜地发现 \(g^{\frac{\varphi(p)}{n}}\) 具有 \(n\) 次单位根的所有性质，那我们就可以愉快地用它来代替 FFT 中的 \(n\) 次单位根去跑 NTT 了！