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

  • blocksight
  • 更新于 2020-07-30 17:34
  • 阅读 5099

本节讲了原根及其定理

写在前面

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

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

原根定义

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

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

点赞 1
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
blocksight
blocksight
江湖只有他的大名,没有他的介绍。