求原根算法及原理

原根是什么就不说了。

首先要知道怎样的数有原根。

一个数有原根，当且仅当这个数为$1,2,4,2p,p^n$。其中$n$为正整数,$p$为奇素数。这里$1$可以忽略掉，它并没有什么用。

一般题目都是求素数的原根。

首先要知道，一个数$n$若有原根，那么其原根的个数为$\varphi(\varphi(n))$个。而且其中最小的那一个一般很小——可以从小到大暴力枚举。所以接下来的算法思想就是从2开始从小到大判断它是不是原根，关键问题就转换为检查一个数是否是另一个的原根。

根据原根的性质，若$g$是$p$的原根，那么$g^0,g^1,…,g^{\varphi(n)-1}$在模$p$意义下各不相同。若一个数不是原根，那么一定存在$0\leq i<j\leq\varphi(n)-1$使得$g^i\equiv g^j \ (mod\ p)$，那么有$g^{j-i}\equiv1\ (mod\ p)$。

设$d=j-i$。由于$g^{\varphi(n)}\equiv1\ (mod\ p)$，因此有$d|\varphi(n)$。

到这里有一个直接的想法：预处理出$\varphi(n)$不等于自身的约数$e_1,e_2,..e_k$，每枚举到一个$d$，就分别计算出$d^{e_1},d^{e_2},…,d^{e_k}$在模$p$意义下的值。如果其中存在1，那么$d$就不是原根，否则就找到了一个原根。

考虑优化这个算法。注意到若$g^{d}\equiv1\ (mod\ p)$，那么当$d^{‘}=2d,3d,…(d^{‘}<\varphi(n) )$时，均有$g^{d^{‘}}\equiv1\ (mod\ p)$。因此我们并不需要枚举$\varphi(n)$的所有约数。只需要枚举$\frac{\varphi(n)}{p_1},\frac{\varphi(n)}{p_2},…,\frac{\varphi(n)}{p_k}$即可。这里的$p_1,p_2,..p_k$为$\varphi(n)$的质因数。