跳转至

原根

原根

定义与性质

对于两个正整数 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<p，g^{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的原根；若不存在，则 a是 p的原根。

证明：

假设存在一个 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意义下进行快速变换了。

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论