写在前面
上一节讲了二次剩余和欧拉准则,证明欧拉准则时候，用到了原根的性质。
本节我们系统地了解下原根及其性质。原根涉及到数论中较多内容，不一定一次讲完，先看看吧。
原根定义
首先引入一个阶的在模运算下的定义：
阶的定义：设?>1，且???(?,?)=1即a,m互质，那么使得$a^r \equiv 1(mod \ m)$ 成立的最小的正整数?，称为?模?的阶，记为??(?)，即r = ??(?)
阶性质一：
若?>1并且$???(?,?)=1$，满足$a^n \equiv 1(mod \ m)$，那么$\delta ?(?)∣?$ [ $\delta ?(?)$整除n,是n的乘因子]。
阶性质二：
由一可推得：$\delta m(a)|\Phi (m)$，即$\delta m(a)$整除$\Phi (m)$。这里的$\Phi (m)$是欧拉函数。
有了阶的定义，下面看下原根：
原根（primitive root）的定义:
假设m是正整数，a是整数，若a模m的阶等于$\Phi (m)$，则称a为模m的一个原根。
换句话说， 假设一个数g是p的原根，若p是素数，1<g<p，0<i<p,那么 $g^i \ mod \ p$ 的结果两两不同，本质上是因为：
$g^{p-1} \equiv 1( mod \ p)$
当且仅当指数为p-1的时候成立.
所以，当a是模m的原根时，$a^0,a^1,...,a^{p-1}$ 构成模 m 的简化剩余系。
容易证明,不再详述。
举例说明：
$ 3^1\ ???\ 7 = 3$
$ 3^2\ ???\ 7 = 2$
$ 3^3\ ???\ 7 = 6$
$ 3^4\ ???\ 7 = 4$
$ 3^5\ ???\ 7 = 5$
$ 3^6\ ???\ 7 = 1$
可以看到3模7阶是6，等于$\Phi (7)$，3是模7的原根。3的幂模7结果各不相同，恰好构成模7运算的简化剩余系。
再看一个例子
$ 2^1\ ???\ 7 = 2$
$ 2^2\ ???\ 7 = 4$
$ 2^3\ ???\ 7 = 1$
$ 2^4\ ???\ 7 = 2$
$ 2^5\ ???\ 7 = 4$
$ 2^6\ ???\ 7 = 1$
可以看到2模7的阶是3，不是6，不是模7的原根。2的幂模7也不能构成模7运算的简化剩余系。同样的大家可以检验5也是模7的一个原根。
原根定理
知道了原根，接下来看一下原根一些特性，也称定理。
定理一：一个正整数?有原根的充要条件是$m=2,4,p^e,2p^e$，其中，?奇素数，?为正整数。
定理二：每一个素数?都有原根且有$\phi(?−1)$个原根，推广之，每一个正整数?都有$\phi (\phi (?))$个原根。
定理三：若?是?的一个原根，则$g,g^2,...,g^{\phi(m)}$，各数对?取模的非负最小剩余就是小于?且与?互质的$\phi (?)$个数的一个排列。
【注：以上定理推导用到了欧拉定理，和数论其他知识，此处不再给出证明过程，感兴趣可以自行查阅】
利用定理二，可以知道素数7有2个原根，$\phi (?−1)=\phi (7−1)=\phi (6)=2$ 。这两个原根是3和5（参见上面举例）.
通过上面的定理，也可以得到以下性质：
-
设g是模p的原根，则g或者g+p是模$p^2$的原根；
-
设p是奇素数，则对任意a,模$p^a$的原根存在；
-
a>=1, 若g是模$p^a$的一个原根，则g与$g+p^a$中的奇数是模$2p^a$的一个原根
应用原根可以证明：若x的$[\Phi (n)/2]$次方模n余1，则x为模n的二次剩余；若x的$[\Phi (n)/2]$次方模n余-1，则x为模n的非二次剩余。这正是上一篇文章用到的。
原根求法
由原根的定义和定理，不难得到原根的求法。
暴力枚举：
从2开始枚举，然后暴力判断$g^{m-1} ≡ 1 (mod\ m)$是否当且当指数为m-1的时候成立，之所以可以这么做，是由于原根一般都不大，下面介绍一种较快速的办法。
素幂分解法：
- 求$\phi (?)$的素幂分解式：
$\phi (?)=p_1^{i_1}p_2^{i_2}...*p_k^{i_k}$
- 枚举g(g < ?)，若恒满足
$g^{\frac{\phi (m)}{p^i}} \not=1(mod \ m),i=1,2,...,k$
则?是?的一个原根。为什么这样求解是正确的？
留给大家自己思考，如果必要，下一篇加上。
小结
本节讲了原根及其定理，并没有给出很多证明，因为不少朋友反馈，证明过程读起来困难。确实是，如果不是数学专业或密码学专业的话。如果对理论不感兴趣的朋友，可以略过推导部分，知道几个主要的结论就可以了。
总有一些人想刨根问底，格物致知，是非常值得提倡的！！
好了，有了原根知识，下一篇继续回到二次剩余方程求解的问题。
欢迎关注公众号：blocksight
