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

本节讲了原根及其定理

## 写在前面 上一节讲了[二次剩余和欧拉准则](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
  • 阅读 ( 74 )
  • 学分 ( 2 )
  • 分类:入门/理论

该内容来自于互联网公开内容,非区块链原创内容,如若转载,请注明出处:https://htzkw.com/archives/27847

联系我们

aliyinhang@gmail.com