云计算在素性检测中的应用

发布时间：2019-11-21 02:26

【摘要】：云计算的兴起带来了又一次信息革命。云储存、云计算、云安全、云杀毒、云邮箱等等，一系列的和云有关的名词如雨后春笋般涌现。云计算是网格计算和效用计算的变身版，为用户提供包括自助式服务、虚拟化资源、快速弹性计算和海量存储等诸多服务。云计算的关键技术之一就是Google公司于2009年提出的MapReduce简化分布式计算模型，这是一种专门用来处理数据密集型计算的分布式计算方法。而这种思想早在2006年就已经在Apache公司的Hadoop产品中有所体现，并被Yahoo公司的网格计算团队采用。Hadoop主要由HDFS和MapReduce两部分组成，其基本思想就是把庞大的数据分成小块，分别对小块数据化简之后再进行归约。基本流程是首先把标准输入流中的元素分布式存储在每个分块（任务节点）中，再由主控节点给任务节点分配Map（化简）和Reduce（归约）任务，任务完成后由标准输出流输出。素性检测是公钥密码学的关键技术之一，目前已经找到的最大素数是第47个梅森素数（243,112,6091），其素性的判定采用的是Lucas-Lehmer素性检测法。除了判定梅森素数的Lucas-Lehmer素性检测法，目前比较流行的素性检测方法有theSieveofEratosthenes（试除法）、Miller-Rabin素性检测法、AKS素性检测法及AKS的一些改进算法。素性判定亟待解决的问题就是如何缩短算法的时间复杂度。考虑到简易和精确，试除法一直被人们广泛使用着，尽管它的算法时间复杂度达到Ο(n)。虽然2002年Agrawal、Kayal和Saxena提出了多项式时间算法复杂度的AKS素性检测算法（时间算法复杂度为Ο(logn)12 2），但是AKS算法一直没有被广泛使用，其关键原因是只有当n达到百万数量级，AKS算法才会优于试除法，并且对比概率性素性检测算Miller-Rabin（时间算法复杂度为Ο(2(logn)/2)），AKS显得太慢了。即使后人对AKS算法进行了很多改进，但是始终没能够达到满意的效果，在实际应用中人们仍旧普遍采用试除法和概率性素性检测算法进行素性判定。考虑到云计算的海量数据处理能力，本文拟采用基于云计算的分布式并行计算方法进行素性检测，以缩短素性检测时间，，提高素性检测效率。让崭露头角的云计算为素性的检测奉献一份力量，让新时代的产物为盘根错节的古老问题带来柳暗花明。现将本文的主要成果罗列如下： 1)实现了传统素性检测算法中部分环节的分布式计算。分布式计算要求的是输入流中各个元素之间的计算互不影响，并且计算和输入输出次序可以任意安排。在素性检测的很多算法里都会涉及到迭代的思想，而迭代算法是不满足进行分布式计算的前提条件的。但通过分析研究发现试除素性检测法和AKS素性检测法中的部分循环满足分布式计算的条件，因此可以通过选择准确的输入文件、设计适当的Map和Reduce算法、合理配置Hadoop来部分实现这两种确定性算法的分布式计算。对于素性检测的其他算法，本文列出了时下流行的Miller-Rabin和Lucas-Lehmer素性检测算法，考虑到其中的循环涉及迭代，不方便对算法中的循环进行Map和Reduce处理，但云计算同样可以提高这些算法的效率。 2)提出了给定范围内素数搜索的新方法。当需要寻找素数时，我们一般都是在某个范围内进行随机查找，本文给出的改进方案是把给定范围内需要查找的所有数据根据slave（任务节点）的数量分割成许多小块，让每个slave获得一小部分数据，然后用Miller-Rabin或者Lucas-Lehmer书写Map函数，再分配给每一个slave，每个slave并行地完成自己分配到的任务，最后进行Reduce处理。 3)解决了VC环境下大数处理的问题。在素性判定中，所用到的数一般都会超过20位（十进制），用普通的数据类型已经远远不能满足实验的要求。本文通过采用GMP软件包来进行数据类型扩展，解决了大数据的输入和输出问题。
【学位授予单位】：成都理工大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：O156;TP3

【参考文献】