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

本节讲了原根及其定理

## 写在前面 上一节讲了[二次剩余和欧拉准则](https://learnblockchain.cn/article/1524),证明欧拉准则时候，用到了原根的性质。 本节我们系统地了解下原根及其性质。原根涉及到数论中较多内容，不一定一次讲完，先看看吧。 ## 原根定义 首先引入一个阶的在模运算下的定义： **阶的定义**：设?>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)$是[欧拉函数](https://learnblockchain.cn/article/1559)。 有了阶的定义，下面看下**原根**： **原根（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$ 则?是?的一个原根。为什么这样求解是正确的？ 留给大家自己思考，如果必要，下一篇加上。 ## 小结 本节讲了原根及其定理，并没有给出很多证明，因为不少朋友反馈，证明过程读起来困难。确实是，如果不是数学专业或密码学专业的话。如果对理论不感兴趣的朋友，可以略过推导部分，知道几个主要的结论就可以了。 **总有一些人想刨根问底，格物致知，是非常值得提倡的！！** 好了，有了原根知识，下一篇继续回到[二次剩余方程求解的问题](https://learnblockchain.cn/article/1520)。 欢迎关注公众号：blocksight

写在前面

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

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

原根定义

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

阶的定义：设?>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}$

1. 枚举g(g < ?)，若恒满足

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

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

小结

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

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

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

欢迎关注公众号：blocksight

区块链技术网。

• 发表于 2020-07-30 17:34
• 阅读 ( 1314 )
• 学分 ( 7 )
• 分类：入门/理论