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

《费马小定理和素数在密码学的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、费马小定理和素数在密码学的应用　　【摘要】素数一直以来都是数学界研究的重要课题，而素数的正确利用可以为密码学提供有效的工具。本文将要介绍获取并检验素数的方法，以及著名的RSA密码的原理。　　【关键词】求模运算RSA算法米勒拉宾算法密码学　　【中图分类号】G642【文献标识码】A【文章编号】2095-3089（2016）11-0199-02　　公元前在古希腊就产生了早期的算术，直到20世纪初才开始使用数论这个词汇。而从早期到中期的这段时间数论却几乎没有什么发展，直到19世纪才由费马、梅森、欧拉、高斯、黎曼、希尔伯特等人发展起来。而且主要内容是寻找素数通项公式，

2、由初等数论向解析数论和代数数论转变，但也产生很多无法解决的猜想。20世纪有些猜想得以解决，但现在仍然有很多结论是以黎曼猜想一类未能被完全证明的猜想为理论基础的，也就是说假使这些猜想是正确的很多理论也会随之正确并有可能上升为定理，一旦猜想是错误的很多理论也会随之覆灭。目前解决大多数猜想的瓶颈就是素数通项公式，有这样一个说法“如果找到一个素数通项公式，一些困难问题就可以由解析数论转回到初等数论范围”，可见，素数在当今还有很大的研究空间，尽管我们无法确定素数通项公式是否存在。而我想就当前日益发展的科技领域谈谈数论中素数的关键地位。5　　在这个科技化时代，计算机的地

3、位不断上升，人们对计算机的诉求也不断增大，可能作为一个普通的程序员对于计算机内部的数据处理和优化没有太大的需求。而想要使计算机变得更加强大性能更加优异，除了在硬件方面的进步，在优化算法方面，数论方面的知识有着广泛的应用。例如在计算机算术、计算机设计、计算机理论、计算机复杂度等。而这之后，就会有大量的信息在网络世界中流通，而这之中不乏一些机密信息，信息安全就显得日益重要，密码学也就应运而生。20世纪中后期就产生了一种RSA码，这种神奇的密码正是利用了素数成为至今仍有实用价值的密码。　　随着人们慢慢注意到素数的特殊性，人们对这种特殊数字的研究也更加深入，素数在密

4、码学的作用也变得越来越大。　　一、素数测试　　如果用最普通的方法获得素数，无非就是随机获得一个数，然后对其进行素性测试。素数的定义就是除了1和它本身以外没有其它的因子。假定该数字为p。　　用简单的计算机语言描述就是：　　for（inti=1;i<p;++i）　　if（p%i==0）continue;//p≡0（modi）即p能被i整除　　则p不是素数。　　但是这样的方法复杂度高达O（n）。如果加以优化，只需要试除到：　　for（inti=1;i<sqrt（p）;++i）　　if（p%i==0）continue;//p≡0（modi）即p能被i整除

5、　　这样复杂度就降到了O（sqrt（n））。　　但是如果采用了米勒拉宾素性检测法，计算将更加简单。5　　数学原理如下：　　若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为素数（p>2），　　如果x2≡1（modp）且x既不是1也不是p-1，则称x为“1模p的非平凡平方根”　　欲证明素数没有满足模p余1的非平凡平方根存在。　　证明：假设x是一个模p余1的非平凡平方根，则有：　　x2≡1（m

6、odp）　　（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必为合数。　　利用以上这些性质，产生了著名的米勒-拉宾素性检测算法：　　定义5　　x02≡1（modn）　　x12≡1（modn）　　…　　xtt-12≡1（modn）　　xi是满足1<xi<n-1的随机数，

7、在这一计算过程中，如果有任意一个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

8、，将X作为解密关键。　　小明想把数字A（A要小于N）