阶&&原根性质：
我们不管阶。
对于一个数m，若对于所有的i,$1<=i<=\phi_m$
整数a满足$a^i mod\space m$的值是小于m和m互质的$\phi(m)$个数的排列，那么，a是m的一个原根一般要求最小的正原根g
求法：
暴力枚举g
性质：g是原根的充要条件：对于任意的i,$1<=i<\phi_m$若$g^i\neq 1 \space mod \space m$都成立那么，g是m的一个原根证明：必要性：显然假如不成立。那么，会和$a^i=1 \space mod \space \phi(m)$相同充分性：反证。在条件成立下，假如存在一个j，k，使得$a^j=c \space mod \space m$和$a^k=c \space mod \space m$相同那么，必然有$a^{(i-j)}=1 \space mod \space m$矛盾。证毕。然后优化求法的看这篇：
（这个博客挂了）
找原根，从2开始枚举
暴力验证1<=i<=phi是否有g^i=1
比较优化的是，枚举phi的所有约数（不包括phi自己），没有得1的是充分必要条件（必要性：显然。充分性：考虑一个p，使得g^p=1，由于g^phi=1，所以g^(phi-p)=1，进而，g^(gcd(phi,p)=1，而phi的所有约数k都不满足g^k=1 ，所以矛盾。）
最优化的话，phi=p1^q1*p2^q2*p3^q3...*pk^qk,枚举质因子t=pi,如g^(phi/t)都不为1的话，g是原根。
对于最优求法的证明补充：
必要性：显然。和上面我写的证明一样。
充分性：如果g满足条件却不是原根，那么，存在一个不属于那个验证集合的k满足，$k|\phi(m) $且$ g^k=1 \space mod \space m$（若不存在$k|\phi(m)$满足$ g^k=1 \space mod \space m$，那么就意味着，对于所有的$\phi(m)$的约数d，都满足$g^d=1 \space mod \space m$那么，根据第一个优化算法的证明，g一定是原根了）那么，显然有，$g^{tk}=1 \space mod \space m$那么，必然会有一个验证集合的数x，使得$x=g^{tk}$，会矛盾。证毕。
模板题：
#include#define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x);}namespace Miracle{const int N=1e5+5;int p;ll qm(int x,int y,int mod){ ll ret=1; while(y){ if(y&1) ret=(ll)ret*x%mod; y>>=1; x=(ll)x*x%mod; } return ret;}int fac[N],tot;void divi(int x){ for(reg i=2;(ll)i*i<=x;++i){ if(x%i==0){ fac[++tot]=i; while(x%i==0) x/=i; } }}int main(){ scanf("%d",&p); divi(p-1); int ans=2; while(1){ bool fl=true; for(reg i=1;i<=tot;++i){ ll tmp=qm(ans,(p-1)/fac[i],p); if(tmp==1) { fl=false;break; } } if(fl) break; ++ans; } printf("%d",ans); return 0;}}int main(){ Miracle::main(); return 0;}/* Author: *Miracle* Date: 2018/11/20 14:36:16*/
应用：
当m是质数的时候，g^i可以遍历j（属于1~m-1）
我们可以用i代替j
那么，如果要计算j*k，j、k的原根是x、y。
那么可以计算成x+y。再计算g^(x+y)
有的时候可以降低复杂度。