区块链中的数学-原根定理

写在前面

上一节讲了二次剩余和欧拉准则,证明欧拉准则时候，用到了原根的性质。

本节我们系统地了解下原根及其性质。原根涉及到数论中较多内容，不一定一次讲完，先看看吧。

原根定义

首先引入一个阶的在模运算下的定义：

阶的定义：设𝑚>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（参见上面举例）.

通过上面的定理，也可以得到以下性质：

1. 设g是模p的原根，则g或者g+p是模$p^2$的原根；

2. 设p是奇素数，则对任意a,模$p^a$的原根存在；

3. 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的时候成立，之所以可以这么做，是由于原根一般都不大，下面介绍一种较快速的办法。

素幂分解法：

1. 求$\phi (𝑚)$的素幂分解式：

$\phi (𝑚)=p_1^{i_1}*p_2^{i_2}*...*p_k^{i_k}$

2. 枚举g(g < 𝑚)，若恒满足

$g^{\frac{\phi (m)}{p^i}} \not=1(mod \ m),i=1,2,...,k$

则𝑔是𝑚的一个原根。为什么这样求解是正确的？
留给大家自己思考，如果必要，下一篇加上。

小结

本节讲了原根及其定理，并没有给出很多证明，因为不少朋友反馈，证明过程读起来困难。确实是，如果不是数学专业或密码学专业的话。如果对理论不感兴趣的朋友，可以略过推导部分，知道几个主要的结论就可以了。

总有一些人想刨根问底，格物致知，是非常值得提倡的！！

好了，有了原根知识，下一篇继续回到二次剩余方程求解的问题。

欢迎关注公众号：blocksight