论Miller-Rabin算法预处理的局限性

• 作者: 周靖 王景中
• 来源期刊: 通信技术
• 学科: 工学
• 关键词: 素性检测 Miller-Rabin算法 误判率与出错率 素数分布 预处理的局限性 算法底层优化
• 年，卷（期）: 2015,（4）
• 所属期刊栏目: 安全与保密
• 页码范围: 469-472
• 页数: 4页
• 分类号: TP301.6
• 字数: 3154字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-0802.2015.04.017

摘要

信息安全领域中极为重要的公钥密码体制的关键在于生成两个大素数,目前虽已有多项式运行时间的确定性素性检测算法AKS算法,可惜运行时间还达不到实用要求,故还是快速实用的概率性素性检测算法Miller-Rabin算法为主流,但其有一点一直被忽略——Miller-Rabin算法直接控制的其实是误判率而不是出错率,而后者才是真正需要降低的.对此做了详细分析,同时考察一些利用素数分布特性的预处理措施在降低出错率方面的效果,并分析了这一类优化的效果极限,否定了其必要性,相比之下,针对算法底层的优化更为直接有效.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王景中	北方工业大学信息与通信工程学院	87	412	10.0	15.0
2	周靖	北方工业大学信息与通信工程学院	2	12	1.0	2.0