这篇文章主要介绍了区块链中的数学-原根定理 ,文中通过代码以及文档配合进行讲解,很详细,它对在座的每个人的研究和工作具有很经典的参考价值。 如果需要,让我们与区块链资料网一起学习。

https://www.interchains.cc/19102.html

区块链中的数学-原根定理是很好的区块链资料,他说明了区块链当中的经典原理,可以给我们提供资料,区块链中的数学-原根定理学习起来其实是很简单的,

不多的几个较为抽象的概念也很容易理解,之所以很多人感觉区块链中的数学-原根定理比较复杂,一方面是因为大多数的文档没有做到由浅入深地讲解,概念上没有注意先后顺序,给读者的理解带来困难

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

本节讲了原根及其定理

写在前面

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

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

原根定义

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

阶的定义:设𝑚>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

部分转自网络,侵权联系删除www.interchains.cchttps://www.interchains.cc/19102.html

区块链毕设网(www.interchains.cc)全网最靠谱的原创区块链毕设代做网站 部分资料来自网络,侵权联系删除! 最全最大的区块链源码站 ! QQ3039046426
区块链知识分享网, 以太坊dapp资源网, 区块链教程, fabric教程下载, 区块链书籍下载, 区块链资料下载, 区块链视频教程下载, 区块链基础教程, 区块链入门教程, 区块链资源 » 区块链中的数学-原根定理

提供最优质的资源集合

立即查看 了解详情