【硕士论文】Miller-Rabin素数检测优化算法研究及其并行实现.pdf

《【硕士论文】Miller-Rabin素数检测优化算法研究及其并行实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、摘要密码破译技术的快速发展，一方面促进了学者们对加密算法的深入研究，另一方面对现有算法的密钥长度，提出了更高的要求。素数，作为几种常用加密算法的密钥参数，研究价值不言而喻。本文以此为背景，针对素数值越大，检测时间越长，效率越低等问题，在研究了Mill*Rabin算法基础之上，通过加入预处理过程，对原算法进行了更加细致具体的优化，减少了原算法中幂模运算的次数，从而大大提高了对于素数的检测速度。优化后的算法具备数据并行性，为了更进一步提高检测效率，本文采用并行计算技术，通过服务端向客户端发送检测参数，利用多台客户端同时进行运算的方式，根据机器性能的不同分配任务量，实现了用Ⅳ

2、台客户端完成相同任务量所用时间仅为单机所用时间的1／Ⅳ，即达到了并行计算的理想状态值。系统的整个研究设计过程都以最大限度地压缩通信量为基准，尽量减少通信所带来的额外开销，通过大素数的本地存储以及多线程调度结合异步编程模式等多种技术手段，实现了素数检测效率的更进一步提高，最后通过多项实验对比得到的结果令人满意。本文在程序实现上采用的技术主要有基于．Net环境的WiIlSock编程技术、多线程编程、异步编程模式，以及目前国内外较为流行的面向对象系统分析技术，确定了由对象层、结构层、主题层和属性层构成的静态架构以及用于表示系统功能的高层逻辑模型，实现了在计算机机群网络范围内的

3、分布式计算。该系统运行稳定、通信情况优良。关键词：大素数；Mill昏RabiIl算法；并行计算东北师范大学硕士学位论文引言密码学是一门研究加密与解密技术的科学。研究密码变化的客观规律，应用于加密数据信息保守通信秘密的，称为编码学；应用于破译密码以获取通信情报的，称为破译学，总称密码学【11。密码学最早起源于密写术，发展至今融合了多个科学领域，从社会学、数学、物理学、计算机科学中都吸收了思想和方法。一个多世纪以来，密码学从单钥加密法、多钥加密法，发展到流加密法、块加密法，一直到公钥密码体制诞生，才暴发了密码学史上最大的而且也是唯一一次真正的革命。公钥密码体制的优点是以非对

4、称的形式使用两个密钥，加密密钥可以公开传播，解密密钥则需要特别的选择和管理，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义【21。在公钥密码体制的密钥研究中，素数，由于其自身具有的一些特性而引起了人们的广泛关注，被合理运用到加密算法当中，收到了良好的效果，发挥了关键性的作用。以沿用至今最有生命力的公钥密码体制国际标准RSA为例，其理论基础是数论中的一条重要论断：求两个大数之积是容易的，而将一个具有大素数因子的合数进行分解却是非常困难的【3，4】。RSA公钥密码体制描述如下：(1)选取两个大素数p和g(保密)。(2)计算疗=p}g(公开)，依据Euler定理得到

5、吠，z)=(p一1)(g—1)(保密)。(3)随机选取正整数e，1_≮P<烈，1)，满足gcd(P，烈，z))=1，P是公开的加密密钥。(4)计算d，满足d幸P耋1(mod烈玎))。d是解密密钥。(5)加密变换：对明文m，密文为c=m。mod，l。(6)解密变换：对密文c，明文为m=cdmodn。然而，随着人类计算能力的不断提高以及分解算法的进一步改进，原来被认为是不可能分解的大数已被成功分解。例如RSA．129(即129位十进制数玎)，用二次筛选法在网络上通过分布式计算，历时八个月，于1994年4月被成功分解；RSA．130，利用一种新的分解算法——推广的数域筛选法，

6、于1996年4月被成功分解[5】，所做的计算仅比分解RSA．129多10％。不仅RSA如此，诸如椭圆曲线密码体制【6，孔、Di彘r-HellmaIl密钥交换协议及由它派生出的其他公钥密码体制，也都要应用大素数来定义有限域，这些算法面临同样的危机。l东北师范大学硕士学位论文在这种背景下，提高加密算法中的密钥长度显得尤为重要。在未来相当长的一段时期内，使用300位长的十进制素数做密钥参数对于像RSA这样的算法来说是足够安全的【81。一般来说，待测数位数越长，素性检测难度越大，耗费时间越多。如何在确保检测精度的同时，提高检测速度以及效率，是本文解决的主要问题。此问题关系到公钥

7、密码体制的完善乃至今后密码学的发展，因此具有很高的研究价值、应用价值和深远的历史意义。2东北师范大学硕士学位论文第一章绪论素数就是自然数中除l和自身外没有其他因子的一类数。素数具有许多特异的性质和现象，千百年来一直吸引着众多的数学家对它进行研究。早在2300多年前，希腊数学家欧几里得就运用反证法证明了素数个数是无限的【9】。随后各国科学家开始寻找素数的一般表达式，1772年，欧拉给出了一个表达素数的三项式；17世纪法国著名数学家费马也曾宣布过一个二次方定理；米乐斯、布雷迪欣、罗斯杭斯伯格等等也都有成果发表[10，111。科学研究的道路是曲