质数的验证!你了解多少(从零开始学区块链 )

区块链资讯区块网2017-11-07 19:39:03  阅读 -评论 0

素数又称为质数,在数论领域是研究的重点,同时关于质数的产生和大数质数分解也是密码学中的重要课题,区块链世界也诞生过使用质数验证作为工作量证明的素数币

本文主要科普一下关于质数的验证的几种方式,质数验证可以用于通过随机数产生大质数这类的算法。


质数的验证也称为素性验证,是检验一个给定的整数是否为素数的测试,素数是除了自身和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]r∈[0,s−1],若admodN≠1admodN≠1且a2rdmodN≠−1a2rdmodN≠−1,则N是合数。否则,N有34的概率为素数。
目前在RSA的算法的部分实现中,米勒-拉宾验证被大量使用,有大量开源的这个算法实现。
普罗斯定理
普罗斯定理是数论的一个定理,可以判断普罗斯数是否是质数。
如果p是普罗斯数,也就是满足k2n + 1形式的数,其中k为奇数,且k < 2n,那么如果对于某个整数a,有
·p−1)/2≡−1(mod p)
则p是素数。此时p称为普罗斯质数。这是一个有实际用途的方法,因为如果p是素数,任何选定的a都有百分之50的机会满足这个关系式。
若a是是模p的二次非剩余,则上述定理的逆定理也成立,因此有一种可以找a的方式,就是在最小的质数中依序找a,计算雅可比符号,直到下式成立为止
.
。(a|p)=−1
蒙地卡罗算法的素性测试是乱数算法,可能会产生伪阳性的结果(不是素数的数却通过素性测试),根据普罗斯定理的算法是拉斯维加斯算法,其答案都是对的,但要找到答案的时间则是随机变化。

后记

原来知道质数测试比较复杂,但是查阅wiki资料后才发现的确非常复杂,部分公式完全看不懂,索性还是发出来全当自己收藏,在这些理论中我比较感兴趣卡米歇尔数这个伪质数,在大数中比较难寻找,或许可以作为一中新的pow算法基础,部分观点认为,由于素数在数轴上分布不均匀,且根据目前掌握的知识来看,数越大,素数越稀有,寻找难度并不是线性递增,耗时也就不可预估,但是区块链要求稳定出块,可能因为这些基于质数的pow算法没有很好的发展,但是肯定有人没有放弃在继续这方面的研究。

另外有人问过我关于量子计算对于密码学的攻击问题,我觉得最后能真正摧毁一个加密体系的应该是诞生天才数学家,如果有数学家能找到快速分解大整数为质数乘积的数学方法,RSA系列的加密算法应该就结束了,相比量子计算机我觉得数学家更恐怖 :)


来源:区块链大师 微信号DACMaster

声明:链世界登载此文仅出于分享区块链知识,并不意味着赞同其观点或证实其描述。文章内容仅供参考,不构成投资建议。投资者据此操作,风险自担。此文如侵犯到您的合法权益,请联系我们100@7234.cn

    参与讨论 (0 人参与讨论)

    相关推荐

    中信银行打造“区块链”信用证结算!

    中信银行打造“区块链”信用证结算!

    科技不会改变金融的实质,但却能让金融服务更高效,能让资金供、需方信息不对称的问题更好地解决。近期,中信银行首个区块链项目——基于区块链的国内信用证信息传输系统(简称BCLC)(一期)成功上线,这是国内银行业第一次将区块链技术应用于信用证结算领域。 据中信银行国际业务部总经理助理张栩青介绍,将现在流行的区块链技术应用在国内信用证中,改变了银行传统信用证业务模式,信用证的开立、通知、交单、承兑报文

    中国信息技术部门成立区块链研究实验室

    中国信息技术部门成立区块链研究实验室

    暴走时评:本月初,中国政府对国内的ICO和数字货币交易所的打击在世界范围内引起了强大反响,但政府已经多次声明不会将区块链与数字货币划等号,依然非常重视区块链技术在中国的发展。鉴于中国工业和信息化部成立了一个专门研究区块链的实验室,这一论调也得到了进一步的证实。 虽然中国政府最近在大力打击比特币交易所和ICO,但仍然致力于开发区块链在其他领域的潜力。 据财新网报道,中国工业和信息化部已经成立了一

     分布式账本中的生命科学

    分布式账本中的生命科学

    生物科学是医学领域涉及遗传研究,疾病预防和生活方式治疗(lifestyle treatments)的学科。它已经存在了很长时间,但区块链技术的基础设施应用给该学科提供了重大进步的可能性。 根据Pistoia Alliance进行的2016年6月份高级制药和生命科学领袖调查,83%的受访者表示,他们预计在五年内将全面采用区块链技术。 Pistoia Alliance是一个全球性的非营利组织,致

    区块链vs.核能:日本最大电力公司东京电力(TEPCO)寻求使用区块链减轻对核电的依赖

    区块链vs.核能:日本最大电力公司东京电力(TEPCO)寻求使用区块链减轻对核电的依赖

    东京电力公司 (TEPCO) 对于能源过度中心化的风险可以说绝不陌生。 也许最著名的就是2011年发生的福岛核电站事故,这个日本最大的能源公司如今正在寻求区块链技术来防止这种灾难再次发生。 然而,从使用微型风车的分布式风力发电到用于存储在电力成本低时购买的电力的智能电池,可替代能源项目一直以来都属于个人慈善事业。 然而,TEPCO风险投资部门主管Jeffrey Char认为区块链能够帮助为这

    继证监会发表代币发行声明之后,香港交易所Gatecoin将下线部分ICO币

    继证监会发表代币发行声明之后,香港交易所Gatecoin将下线部分ICO币

    经过一系列监管以及合规审查后,香港交易所Gatecoin将会下线那些被金融监管部门定性为"证券"的代币。 香港加密货币交易所Gatecoin透露,如果在该平台交易的ICO代币在法律上符合"证券"定义,他们就会下线这些代币。据巴比特上月报道,香港主要的金融监管部门证券及期货事务监察委员会(SFC)表达了对ICO这种日渐普及的募资模式的担忧。 尽管ICO中售卖的数字代币通常都被定义为虚拟商品,但

    IBM与超级账本共同加入去中心化身份基金会(DIF),推动创建区块链ID行业标准

    IBM与超级账本共同加入去中心化身份基金会(DIF),推动创建区块链ID行业标准

    IBM与超级账本已经签署协议加入去中心化身份基金会(DIF),这个于今年初成立的联盟旨在帮助推动基于区块链的ID系统的互操作性和标准。 这两个企业区块链大佬加入了这个有各种企业组成的团体,其中包括像微软和埃森哲这样的大企业,还有像Civic和Gem这样的创业公司,以及像uPort和Sovrin这样的开源项目。 DIF执行主管告诉Coindesk说: "这应该是一个信号,表明在这一领域有广泛的

    为打击人口贩卖,牙买加警方盯上了犯罪分子的比特币钱包

    为打击人口贩卖,牙买加警方盯上了犯罪分子的比特币钱包

    作为打击人口贩卖计划的一部分,牙买加警方已经开始行动,锁定了那些试图用比特币和数字支付来掩人耳目的犯罪分子。 越来越多的人口贩卖者都开始转向数字货币来帮助他们进行地下活动并接收非法活动所得,但牙买加警方已经盯上他们了。 牙买加的'大生意' 不幸的是,人口贩卖以及性奴市场规模十分庞大,预计涉资1500亿美元。在牙买加,大约有7000个妇女、儿童以及成年男性被奴役,他们的操控者出售奴役服务的价格

    深圳市将发布《深圳市扶持金融业发展若干措施》,奖励区块链、数字货币等金融创新

    10月9日,深圳市人民政府向各区人民政府,市政府直属各单位印发《深圳市扶持金融业发展若干措施》(以下简称"《若干措施》")。深圳市政府表示,此举是为进一步完善金融支持政策体系,吸引集聚优质金融资源,推动全市金融业可持续均衡发展,加快建设国际化金融创新中心。 《若干措施》共分五大项,33条。内容包括:坚持服务导向,优化金融政策环境;发展金融总部经济,鼓励金融总部企业做大做强;支持金融企业分支机构

    麦妖榜
    更新日期 2019-04-24
    排名用户贡献值
    1BitettFan23830
    2等待的宿命23697
    3六叶树20309
    4区块大康16762
    5天下无双16192
    6lizhen00214933
    7让时间淡忘14286
    8linjm122713830
    9冷风大q11188
    10momo11174
    返回顶部 ↑