书接上回...
我们知道，我们在使用 FFT 时，靠的是单位根 \(\omega\)。
数学家证明这是复数域中唯一符合条件的数。
可是它的浮点误差和带来的巨大运算时间使我们有点不能接受。
于是，我们想想能不能找个替代品替代掉 \(\omega\)。
于是，原根就出现了！
原根的引入
阶
对于一个数 \(x\) ，在 \(\bmod p\) 的意义下，存在一个最小的正整数 \(k\)，使得 \(a^k\equiv1\)，特别的，当 \(k\) 不存在时，我们认为 \(k=\infty\)。
这么个理解法，举个例子：
在 \(\bmod 7\) 情况下，\(3\) 的阶是 \(6\)。因为 \(3,2,6,4,5,1\)。
说白了就是求循环节。
所以有 \(\infty\) 的情况就是 \(a\) 的 \(p\) 的因数，到 \(0\) 后死循环了。
根据伟大的欧拉函数，我们知道这个循环节最多是 \(\varphi (p)\)。
我们记 \(\delta_p(a)\) 表示 \(a\) 的阶，在 \(\mod p\) 意义下。
原根
我们记 \(\delta_p(a)=\varphi(p)\) 的 \(a\)，叫做 \(a\) 的原根。
只有 \(2,4,2p^c,4p^c\) 的数才存在原根。(\(p\in prime\)，\(p\ne 2,c\in \mathbb{N^+}\))
性质
- 对于 \(a^n\equiv 1,\delta_p(a)|n\)