蒟蒻自用，请数论大神们口下留情
由于原根一般比较小，所以可以从2开始暴枚去找
如果根据原根定义去check是否为原根，单次复杂度$O(phi(P))$
现有另一种check，复杂度$O(d(phi(P))*log(P-1))$
$d(x)$是x的质因数个数
即枚举$phi(P)$的质因数$p_i$，快速幂判断$a^{phi(P)/p_i}$，若都不等于1则$a$是一个原根
必要性显然，充分性需要利用反证法，设$a$满足上述条件但$a^c ==1,c<phi(P)$
设$u,v$满足$u*c+v*phi(P)==gcd(c,phi(P))$
$ u*c=gcd(c,phi(P))-v*phi(P) $
所以 $ a^{gcd(c,phi(P))-v*phi(P)}==a^{u*c}==1 $
由于$a^{phi(P)}=1$
所以$a^{gcd(c,phi(P))}=1$
由于 $gcd(c,phi(P))<phi(P)$,$gcd(c,phi(P))|phi(P)$
设phi(P)的质因数有$p1,p2,p3......$,则$gcd(c,phi(P))$至少整除$phi(P)/p1,phi(P)/p2......$中的一个
则$a^{phi(P)/p_i}$至少有一个等于$1$，与假设矛盾。
所以这样求是没问题的..
原文：https://www.cnblogs.com/yxsplayxs/p/11556212.html