-
题名论Miller-Rabin算法预处理的局限性
- 1
-
-
作者
王景中
周靖
-
机构
北方工业大学信息与通信工程学院
-
出处
《通信技术》
2015年第4期469-472,共4页
-
基金
国家自然基金项目(No.61371142)
北京市创新团队建设提升计划(No.ID HT20130502)~~
-
文摘
信息安全领域中极为重要的公钥密码体制的关键在于生成两个大素数,目前虽已有多项式运行时间的确定性素性检测算法AKS算法,可惜运行时间还达不到实用要求,故还是快速实用的概率性素性检测算法Miller-Rabin算法为主流,但其有一点一直被忽略——Miller-Rabin算法直接控制的其实是误判率而不是出错率,而后者才是真正需要降低的。对此做了详细分析,同时考察一些利用素数分布特性的预处理措施在降低出错率方面的效果,并分析了这一类优化的效果极限,否定了其必要性,相比之下,针对算法底层的优化更为直接有效。
-
关键词
素性检测
Miller-Rabin算法
误判率与出错率
素数分布
预处理的局限性
算法底层优化
-
Keywords
primality test
Miller-Rabin test
misjudge probability and error probability
prime distribu-tion
preprocessing limit
underlying optimization of algorithm
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
