原根（半转载）

原根定义：

设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。（其中φ(m)表示m的欧拉函数）(from 51nod)

原根要求

k有原根当且仅当\(k=2,4,p^a,2p^a\) 其中p是奇素数，a是正整数 ### 如何找模k的最小原根： 暴力枚举判断是不是满足条件。 ### 判断算法： （首先保证\(\gcd(a,m)=1\)） #### 暴力 假设要判断的数为s，判断2到\(\phi(k)-1\)中是否有一个正整数t满足\(s^t\equiv 1(\mod k)\)，如果有则不是，否则就是。 时间复杂度\(O(\phi(k))\)，其实就是\(O(k)\) #### 更快速的方法 设\(x=\phi(k)\),对于每个x的素因数p判断\(s^{\frac{x}{p}}\mod k\)是否为1。如果是则s不是原根。如果都不是则s是原根。

感性理解吧。