原根、阶相关

设a,m是正整数
阶：
如果(a,m)=1，对于$a^n \equiv 1 (mod~{p})$的最小的n，叫做a模p的阶。（阶|ϕ(m)）
原根：
若a模m的阶等于ϕ(m)，则称a为模m的一个原根。

求阶：bsgs
求原根：（原根都不大，一般不超过50）
检查$a^{(m/pi)}=1(mod~p)$，pi是m的质因子（因为假如存在更小的阶，一定有模不为1的值）
复杂度$O(原根大小lognlogn+sqrt(n)（质因数分解）)$