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

• 作者: 郑建德 陈晓文
• 来源期刊: 厦门大学学报（自然科学版）
• 学科: 工学
• 关键词: 素数分布 素数生成 搜索 并行
• 年，卷（期）: 2008,（2）
• 所属期刊栏目: 研究论文
• 页码范围: 207-210
• 页数: 4页
• 分类号: TP393.08
• 字数: 3521字
• 语种: 中文
• DOI: 10.3321/j.issn:0438-0479.2008.02.013

摘要

有效地进行素性判定和搜索大素数一直是公钥密码学中研究的热点,但由于大素数的分布具有稀疏的特点,而且大素数搜索和判定的开销巨大,所以大素数的产生速度较慢.因此.本文提出了一种崭新的并行大素数搜索的限界过滤算法.根据素数的分布规律,将大素数的搜索限制在一定范围内的连续奇数中.搜索时,通过一轮预过滤算法,可淘汰大约83.7%的搜索空间内的整数,消除了传统随机递增搜索方法大量的大整数试除运算,从而提高素数生成的速度.实验结果表明:本文提出的算法在平均素性测试次数和搜索时间上均少于传统的随机递增法.而将限界过滤法扩展为并行算法并在双核CPU上计算.其搜索速度又可加倍提高.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郑建德	厦门大学计算机科学系	22	185	7.0	13.0
2	陈晓文	厦门大学计算机科学系	2	5	1.0	2.0