区块链中的数学-用Miller Rabin算法判断大素数实例

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

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

区块链中的数学-用Miller Rabin算法判断大素数实例是很好的区块链资料,他说明了区块链当中的经典原理,可以给我们提供资料,区块链中的数学-用Miller Rabin算法判断大素数实例学习起来其实是很简单的,

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

区块链blockchain中的数学-用Miller Rabin算法判断大素数实例

本节从"凭证"的角度来扩展说明了Miller Rabin算法

写在前面

上一节说了抽象的椭圆曲线密钥协商和素数判断法, 对于Miller Rabin素数判定法做了简要的概述, 本文再展开说明一下,并附带具体实现如果篇幅允许的话。

Miller Rabin算法之凭证

结合上一文的说明,该算法利用费马小定理和二次探测定理的逆否性质:

把$p-1$分解为$ 2^k t $ 的形式,即:$ p-1=2^k t$

如果我们能找到这样一个a,使得对任意 0 < r < = k, 以下两个式子均满足:

<a href=区块链blockchain中的数学-用Miller Rabin算法判断大素数实例” /> <a href=区块链blockchain中的数学-用Miller Rabin算法判断大素数实例” />

那么p肯定就不是一个素数。这样的a称为p是合数的一个凭证(witness),否则a可能是一个证明p是素数的“强伪证”(strong liar)

也就是说,当p是一个合数的时候,由于a是一定范围内随机选取的,对某次选取的a来说,上述两个式子不同时满足,这时称为p是基于a的大概率素数【注:1-1/4 = 3/4 (单次素数概率),上文提及】。

每个奇合数n都有很多个对应的凭证a,但并不容易直接找出这些a。当前解决的办法是使用概率性的测试。我们从集合中随机选择数a,然后检测当前的a是否是p为合数的一个凭证。

如果p本身确实是一个合数,那么大部分被选择的a都应该是n的凭证,也即通过这个测试能检测出n是合数的可能性很大[注:也有极小概率我们找到的a是一个“强伪证”(反而表明了n可能是一个素数]见举例说明]。

通过多次独立测试不同的a,我们能减少这种出错的概率,这就是Miller Rabin算法思想的核心

对于测试一个大数是否是素数,通用的做法随机选取基数a,毕竟我们并不知道凭证和伪证在 [1, p-1]这个区间如何分布。

典型的例子是 Arnault 曾经给出了一个397位的合数n,但是所有小于307的基数a都是n是素数的“强伪证”。很不幸,如果函数通过检测a = 2,3,5,7,11这几种情况来进行素性检验,会被误判为素数。

所以使用Miller Rabin算法库,错误概率参数尽量设置非常低,即测试次数足够多。

实例说明

通过例子,更能清楚理解“强伪证”。

假设需要检验p = 221是否是一个素数。

首先$p – 1 = 220 =2^2 * 55$,于是我们得到了 k = 2和t = 55。我们随机从[1,p-1]中选取a,假设a = 174,于是有:

<a href=区块链blockchain中的数学-用Miller Rabin算法判断大素数实例” />

因为我们得到了一个-1,所以要么p = 221确实是一个素数,要么a = 174是一个“强伪证”。再尝试选取a=137,于是有:

<a href=区块链blockchain中的数学-用Miller Rabin算法判断大素数实例” />

可得,a = 137是 n = 221为合数的一个凭证,而a = 174是一个“强伪证”, 综合可得p = 221不是一个素数。

代码示例

具体实现代码容易在GitHub上找到,这里贴简单示例,方便直接查看(PC端阅读效果佳)

 #include <iostream> #include <cstdio> #include <algorithm>  #include <cmath>  #include <cstring>  #include <map>  using namespace std; int number = 0;  map<long long, int>m; long long Random( long long n )         //生成[ 0 , n ]的随机数 {     return ((double)rand( ) / RAND_MAX*n + 0.5); } long long q_mul( long long a, long long b, long long mod ) {//快速计算 (a*b) % mod     long long ans = 0;     while(b)     {         if(b & 1)         {             b--;             ans =(ans+ a)%mod;         }         b /= 2;         a = (a + a) % mod;      }     return ans; }  long long q_pow( long long a, long long b, long long mod ) {   //快速幂模运算 (a^b) % mod     long long ans = 1;     while(b)     {         if(b & 1)         {             ans = q_mul( ans, a, mod );         }         b /= 2;         a = q_mul( a, a, mod );     }     return ans; }  bool witness( long long a, long long n )//miller_rabin算法的核心 {  //用检验算子a来检验n是不是素数     long long tem = n - 1;     int j = 0;     while(tem % 2 == 0)     {         tem /= 2;         j++;     }     //将n-1拆分为a^r * s     long long x = q_pow( a, tem, n );     //得到a^r mod n     if(x == 1 || x == n - 1) return true;       //余数为1则为素数     while(j--) //否则试验条件2看是否有满足的 j     {         x = q_mul( x, x, n );         if(x == n - 1) return true;     }     return false; }  bool miller_rabin( long long n, int times )  {   //检验n是否是素数      if(n == 2)         return true;     if(n < 2 || n % 2 == 0)         return false; //注:特别大的数使用BigInt                   for(int i = 1; i <= times; i++)  //做times次随机检验     {         long long a = Random( n - 2 ) + 1;         //得到随机检验算子 a         if(!witness( a, n ))                                //用a检验n是否是素数             return false;     }     return true; }

可以看到用到了快速幂模运算等, 注意对于特别大的数使用BigInt,示例代码仅帮助理解。

小结

本节从"凭证"的角度来扩展说明了Miller Rabin算法,结合前文会有更好的理解。判断大素数的方法除了Miller Rabin这种概率性的算法,也有确定的算法,但是效率不高,未能广泛使用,故不再介绍。

有了数论,RSA,椭圆曲线密码学等基础,从下一篇起打算介绍VRF(随机可验证函数)的原理和在区块链blockchain中的应用。

欢迎关注公众号:blocksight

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

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

提供最优质的资源集合

立即查看 了解详情