质数的验证！你了解多少（从零开始学区块链 193）
本文主要科普一下关于质数的验证的几种方式，质数验证可以用于通过随机数产生大质数这类的算法。
质数的验证也称为素性验证，是检验一个给定的整数是否为素数的测试，素数是除了自身和1以外，没有其它素数因子的自然数。自从欧几里得证明了有无穷个素数以后，人们就企图寻找一个可以构造所有素数的公式，寻找判定一个自然数是不是素数的方法。因为素数的地位非常重要。鉴别一个自然数是素数还是合数，这个问题在中世纪就引起人们注意，当时人们试图寻找质数公式，到了高斯时代，基本上确认了简单的质数公式是不存在的，因此，高斯认为对素性判定是一个相当困难的问题。从此以后，这个问题吸引了大批数学家。 素性判断算法可分为两大类，确定性算法及随机算法。前者可给出确定的结果但通常较慢，后者存在偶然不确定结果但是速度较快。
试除法（埃拉托斯特尼筛法）
尝试从2到的平方根n整数是否整除N。给定一个合数n（这里，n是待分解的正整数），试除法看成是用小于等于平方根n的每个素数去试除待分解的整数。如果找到一个数能够整除除尽，这个数就是待分解整数的因子。试除法一定能够找到n的因子。因为它检查n的所有可能的因子，所以如果这个算法“失败”，也就证明了n是个素数。试除法效率非常低，对于小质数的验证可用，大质数一般不适用这种方法。
卢卡斯-莱默检验法
数学中，卢卡斯-莱默检验法是检验梅森数的素性检验，是由爱德华·卢卡斯于1878年完善，德里克·亨利·莱默随后于1930年代将其改进。因特网梅森素数大搜索用这个检验法找到了不少很大的素数，最近几个最大的素数就是这个项目发现的。由于梅森数比随机选择的整数更有可能是素数，因此他们认为这是一个极有用的方法。卢卡斯－莱默检验法原理是这样：令梅森数 Mp = 2p− 1作为检验对象（预设p是素数，否则Mp就是合数了）。
AKS素数测试
AKS素数测试（又被称为Agrawal–Kayal–Saxena素数测试和Cyclotomic AKS test）是一个决定型素数测试算法 ，由三个来自印度坎普尔理工学院的计算机科学家，Manindra Agrawal、Neeraj Kayal和Nitin Saxena，在2002年8月6日发表于一篇题为素数属于P的论文。作者们因此获得了许多奖项，包含了2006年的哥德尔奖和2006年的Fulkerson Prize。这个算法可以在多项式时间之内，决定一个给定整数是素数或者合数。
AKS最关键的重要性在于它是第一个被发表的一般的、多项式的、确定性的和无仰赖的素数判定算法。先前的算法至多达到了其中三点，但从未达到全部四个。
1、AKS算法可以被用于检测任何一般的给定数字是否为素数。很多已知的高速判定算法只适用于满足特定条件的素数。例如，卢卡斯-莱默检验法仅对梅森素数适用，而Pépin测试仅对费马数适用。
2、算法的最长运行时间可以被表为一个目标数字长度的多项式。ECPP和APR能够判断一个给定数字是否为素数，但无法对所有输入给出多项式时间范围。
3、算法可以确定性地判断一个给定数字是否为素数。随机测试算法，例如米勒-拉宾检验和Baillie–PSW，可以在多项式时间内对给定数字进行校验，但只能给出概率性的结果。
4、AKS算法并未“仰赖”任何未证明猜想。一个反例是确定性米勒检验：该算法可以在多项式时间内对所有输入给出确定性结果，但其正确性却基于尚未被证明的广义黎曼猜想。
费马素性检验
利用费马小定理来测试一个数是否是素数的方法
根据费马小定理：如果p是素数，1≤a≤p−1，那么
ap−1≡1(mod p)
如果我们想知道n是否是素数，我们在中间选取a，看看上面等式是否成立。如果对于数值a等式不成立，那么n是合数。如果有很多的a能够使等式成立，那么我们可以说n可能是素数，或者伪素数。在我们检验过程中，有可能我们选取的a都能让等式成立，然而n却是合数。这时等式
an−1≡1(mod n)
被称为Fermat liar。如果我们选取满足下面等式的a
an−1≢1(modn)
那么a也就是对于n的合数判定的Fermat witness。
费马测试的缺点在于，对于卡米歇尔数n，全部的a都会令gcd(a,n)=1，我们称之为费马骗子数（Fermat liars）。尽管卡米歇尔数很是稀有，但是却足够令费马素性检验无法像如米勒-拉宾和Solovay-Strassen的素性检验般，成为被经常实际应用的素性检验
米勒-拉宾检验
利用随机化算法判断一个数是合数还是可能是素数。卡内基梅隆大学的计算机系教授Gary Lee Miller首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，其后由以色列耶路撒冷希伯来大学的Michael O. Rabin教授作出修改，提出了不依赖于该假设的随机化算法。
要测试N是否为素数，首先将N−1分解为2sd。在每次测试开始时，先随机选一个介于[1,N−1]的整数aa，之后如果对所有的r∈[0,s−1]，若admodN≠1且a2rdmodN≠−1，则N是合数。否则，N有34的概率为素数。
目前在RSA的算法的部分实现中，米勒-拉宾验证被大量使用，有大量开源的这个算法实现。
普罗斯定理
普罗斯定理是数论的一个定理，可以判断普罗斯数是否是质数。
如果p是普罗斯数，也就是满足k2n + 1形式的数，其中k为奇数，且k < 2n，那么如果对于某个整数a，有
a(p−1)/2≡−1(mod p)
则p是素数。此时p称为普罗斯质数。这是一个有实际用途的方法，因为如果p是素数，任何选定的a都有百分之50的机会满足这个关系式。
若a是是模p的二次非剩余，则上述定理的逆定理也成立，因此有一种可以找a的方式，就是在最小的质数中依序找a，计算雅可比符号，直到下式成立为止
-
(a|p)=−1
蒙地卡罗算法的素性测试是乱数算法，可能会产生伪阳性的结果（不是素数的数却通过素性测试），根据普罗斯定理的算法是拉斯维加斯算法，其答案都是对的，但要找到答案的时间则是随机变化。
原来知道质数测试比较复杂，但是查阅wiki资料后才发现的确非常复杂，部分公式完全看不懂，索性还是发出来全当自己收藏，在这些理论中我比较感兴趣卡米歇尔数这个伪质数，在大数中比较难寻找，或许可以作为一中新的pow算法基础，部分观点认为，由于素数在数轴上分布不均匀，且根据目前掌握的知识来看，数越大，素数越稀有，寻找难度并不是线性递增，耗时也就不可预估，但是区块链要求稳定出块，可能因为这些基于质数的pow算法没有很好的发展，但是肯定有人没有放弃在继续这方面的研究。
另外有人问过我关于量子计算对于密码学的攻击问题，我觉得最后能真正摧毁一个加密体系的应该是诞生天才数学家，如果有数学家能找到快速分解大整数为质数乘积的数学方法，RSA系列的加密算法应该就结束了，相比量子计算机我觉得数学家更恐怖 :)
这是一篇科普，大部分资料来源于wiki，汇总一下便于收藏，部分公式由于显示原因会出错；您也可以将本文分享出去让更多人了解这些知识，您的支持和鼓励是我最大的动力，长按二维码关注
长按关注，探索未来
默默无闻的Viewstamps算法（从零开始学区块链 60）
更多精彩内容
