新型大素数快速并行搜索策略  

Novel Fast Parallel Large Prime Search Algorithm

作　　者：陈晓文[1] 郑建德[1] 

机构地区：[1]厦门大学计算机科学系,福建厦门361005

出　　处：《厦门大学学报（自然科学版）》2008年第2期207-210,共4页Journal of Xiamen University：Natural Science

基　　金：国家自然科学基金(60373077)资助

摘　　要：有效地进行素性判定和搜索大素数一直是公钥密码学中研究的热点,但由于大素数的分布具有稀疏的特点,而且大素数搜索和判定的开销巨大,所以大素数的产生速度较慢.因此,本文提出了一种崭新的并行大素数搜索的限界过滤算法.根据素数的分布规律,将大素数的搜索限制在一定范围内的连续奇数中.搜索时,通过一轮预过滤算法,可淘汰大约83.7%的搜索空间内的整数,消除了传统随机递增搜索方法大量的大整数试除运算,从而提高素数生成的速度.实验结果表明:本文提出的算法在平均素性测试次数和搜索时间上均少于传统的随机递增法.而将限界过滤法扩展为并行算法并在双核CPU上计算,其搜索速度又可加倍提高.The search and generation of large prime is one of the hot spots in public-key cryptography. But the search and test of large prime cost high,this speeds down the prime generation. Hence,this paper proposed a novel parallel large prime search algorithm based on filtered limited scope strategy. According to the distribution law of prime number,it limited the search scope in some continuous odd numbers. The previous filter step eliminated plenty of division tests of large number in traditional methods, and about 83.7% number in search scope was filtered as well. Hence,the novel algorithm has an improved speed compared with the traditional incremental random search method. In additional,when this algorithm was extended and applied on the dual core computer,the speed of prime searching was almost doubled.

关 键 词：素数分布 素数生成 搜索 并行 

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]