费马小定理和素数在密码学的应用

费马小定理和素数在密码学的应用【内容摘要】素数一直以来都是数学界研究的主要课题，而素数的正确利用能够为密码学提供有效的工具。本文将要介绍获取并检验素数的方法，以及有名的RSA密码的原理。【本文关键词语】求模运算RSA算法米勒拉宾算法密码学【中图分类号】G642【文献标识码】A【文章编号】2095-3089〔2016〕11-0199-02公元前在古希腊就产生了早期的算术，直到20初才开始使用数论这个词汇。而从早期到中期的这段时间数论却几乎没有什么发展，直到19世纪才由费马、梅森、欧拉、高斯、黎曼、希尔伯特等人发展起来。而且重要内容是寻找素数通项公式，由初等数论向解析数论和代数数论改变，但也产生许多无法解决的猜测。20世纪有些猜测得以解决，但如今仍然有许多结论是以黎曼猜测一类没有能被完全证明的猜测为理论基础的，也就是说假使这些猜测是正确的许多理论也会随之正确并有可能上升为定理，一旦猜测是毛病的许多理论也会随之毁灭。当前解决大多数猜测的瓶颈就是素数通项公式，有这样一个说法“假如找到一个素数通项公式，一些困难问题就能够由解析数论转回到初等数论范围〞，可见，素数在当今还有很大的研究空间，虽然我们无法确定素数通项公式能否存在。而我想就当下日益发展的科技领域谈谈数论中素数的关键地位。在这个科技化时代，计算机的地位不断上升，人们对计算机的诉求也不断增大，可能作为一个普通的程序员对于计算机内部的数据处理和优化没有太大的需求。而想要使计算机变得愈加强大性能愈加优异，除了在硬件方面的进步，在优化算法方面，数论方面的知识有着广泛的应用。例如在计算机算术、计算机设计、计算机理论、计算机复杂度等。而这之后，就会有大量的信息在网络中流通，而这之中不乏一些机密信息，信息安全就显得日益主要，密码学也就应运而生。20世纪中后期就产生了一种RSA码，这种神奇的密码恰是利用了素数成为至今仍有实用价值的密码。随着人们渐渐留意到素数的特殊性，人们对这种特殊数字的研究也愈加深切进入，素数在密码学的作用也变得越来越大。一、素数测试假如用最普通的方法获得素数，无非就是随机获得一个数，然后对其进行素性测试。素数的定义就是除了1和它自己以外没有其它的因子。假定该数字为p。用简单的计算机语言描绘叙述就是：for〔inti=1；ip；++i〕if〔p%i==0〕continue；//p≡0〔modi〕即p能被i整除则p不是素数。但是这样的方法复杂度高达O〔n〕。假如加以优化，只需要试除到：for〔inti=1；isqrt〔p〕；++i〕if〔p%i==0〕continue；//p≡0〔modi〕即p能被i整除这样复杂度就降到了O〔sqrt〔n〕〕。但是假如采取了米勒拉宾素性检测法，计算将愈加简单。数学原理如下：若p为素数，a为整数，且a、p互质。则有ap-1≡1〔modp〕其等价形式为：ap≡a〔modp〕证明如下：令ap-1=k×p+1则ap=〔k×p+1〕*a也即ap≡a〔modp〕引理：若p为素数〔p2〕，假如x2≡1〔modp〕且x既不是1也不是p-1，则称x为“1模p的非平凡平方根〞欲证明素数没有知足模p余1的非平凡平方根存在。证明：假设x是一个模p余1的非平凡平方根，则有：x2≡1〔modp〕〔x+1〕〔x-1〕≡0〔modp〕由于x是非平凡的，就有〔x+1〕与〔x-1〕和x互质，就是说〔x+1〕和〔x-1〕都不能被p整除，因而〔x+1〕〔x-1〕不能被p整除，矛盾。证毕素数没有知足模p余1的非平凡平方根。即假如一个数模p余1下有非平凡平方根，则n必为合数。由该引理可知，若存在x2≡1〔modp〕，则p必为合数。利用以上这些性质，产生了有名的米勒-拉宾素性检测算法：定义x02≡1〔modn〕x12≡1〔modn〕…xtt-12≡1〔modn〕xi是知足1xin-1的随机数，在这一计算经过中，假如有任意一个xi≡1〔modn〕，根据引理，则n必为合数。二、RSA码RSA码的发明就是对素数实际运用的例子。由欧几里得证明的算数基本定理可知任何一个天然数都能够分解为素数的乘积。但是将一个大整数分解只能用较小的素数依次尝试，这种方法无疑是很耗时的。大可在一段固定的时间就更换一次，这样的密码策略堪称无懈可击。接下来有N、a、X、p、q，其获得经过如下：1.任意选取素数p、q，N=p×q。2.中间量r=〔p-1〕×〔q-1〕。3.选取a和X两个互质的数，使之知足aX≡1〔modr〕。4.彻底销毁p、q，公开N和a，将X作为解密关键。小明想把数字A〔A要小于N〕传送给小芳，他并不是直接把A发出去由于这样有可能会被其别人截获，于是我将A连续乘a次，再除以N，将余数发给小芳。小芳手里有一个小明都不知道的数字X，她将余数连乘X次，然后除以N，得到的余数就是A。即小明需要履行的程序是：temp=pow〔A，a〕；temp=temp%N；//temp是一个中间量然后将temp发给小芳，小芳需要履行的程序是：temp=pow〔temp，X〕；B=temp%N；答案:B就是当时小明实际想表达的A。只要素数p、q足够大，N也就很大，a和X的推导经过都是由p和q决定的，只要我销毁p、q，破密的人则需要对N进行整数分解，那将是一个非常庞大的计算量。而且只要N足够大，能够表达的A也就非常大。这种加密方式其实是公开了打乱一个特定信息的方式，任何人都能够用我公开的方法加密信息，但是由于计算量太大，最终能够整理混乱的信息解出最终答案:的人只要我自己。可是有人会说利用现有的费马小定理加上概率测试素数法，在一个较短的能够承受的时间内是能够算出几十位数的分解结果的。即使是一百多位的数，利用如今的网络技术无数台电脑通过沟通信息将这个庞大的计算任务细分化，也就是云计算的方式，也是能够解决的。但是试想如今已经计算出的素数位数早已上千位，两个千位级其余素数相乘之后得到的数字恐怕计算机技术有再大的突破也是难以匹敌的。综上所述RSA码成功的秘诀就是能够获得很大的素数，米勒算法就是一个获得素数的不错算法。将两者结合起来就构成了有名的RSA密码。陈政培以下为参考文