跳转至

原根

原根

定义与性质

对于两个正整数 a,p满足 \gcd(a,p)=1,由欧拉定理可知,存在正整数 d<p(如 d=\varphi(p)),使得 a^d\equiv 1\pmod{p}

因此,在 \gcd(a,p)=1时,定义 a在模 m意义下的阶为使 a^d\equiv 1\pmod{p}成立的最小正整数 d。若 a在模 p意义下的阶等于 \varphi(p),则称 a是模 p的原根。

g是模 p的原根,那么对于所有 1\leqslant i<pg^{i}\bmod{p}互不相同。

求法

暴力枚举当然可以,但是有更好的方法:

p-1进行质因数分解得到不同的质因子 d_{1},d_{2},\ldots,d_{m},对于任意的 1<a<p,要判定 a是否是模 p的原根,只需要检验 a^{\frac{p-1}{d_{1}}},a^{\frac{p-1}{d_{2}}},\ldots,a^{\frac{p-1}{d_{m}}}m个数中是否存在一个数在模 p意义下与 1同余。若存在,则 a不是 p的原根;若不存在,则 ap的原根。

证明:

假设存在一个 t<\varphi(p)=p-1使得 a^t\equiv 1\pmod{p}\forall i\in\left[1,m\right]:a^{\frac{p-1}{d_{i}}}\not\equiv 1\pmod{p}

由裴蜀定理得,一定存在一组 k,x满足 kt=x(p-1)+\gcd(t,p-1);由欧拉定理/费马小定理得 a^{p-1}\equiv 1\pmod{p};故有:

1\equiv a^{kt}\equiv a^{x(p-1)+\gcd(t,p-1)}\equiv a^{\gcd(t,p-1)}\pmod{p}

又有 t<p-1,故 \gcd(t,p-1)\leqslant t<p-1

\gcd(t,p-1)\mid(p-1),故 \gcd(t,p-1)必至少整除 a^{\frac{p-1}{d_{1}}},a^{\frac{p-1}{d_{2}}},\ldots,a^{\frac{p-1}{d_{m}}}中的至少一个,设 ,则 a^{\frac{p-1}{d_{i}}}\equiv a^{\gcd(t,p-1)}\equiv 1\pmod{p}

故假设不成立。

用途

我们发现原根 g拥有所有 FFT 所需的单位根 \omega的性质,于是我们用 g^{\frac{p-1}{n}}\bmod{p}来代替 \omega_{n},就能把复数对应到一个整数,在模 p意义下进行快速变换了。


评论