摘要
信息安全领域中极为重要的公钥密码体制的关键在于生成两个大素数,目前虽已有多项式运行时间的确定性素性检测算法AKS算法,可惜运行时间还达不到实用要求,故还是快速实用的概率性素性检测算法Miller-Rabin算法为主流,但其有一点一直被忽略——Miller-Rabin算法直接控制的其实是误判率而不是出错率,而后者才是真正需要降低的。对此做了详细分析,同时考察一些利用素数分布特性的预处理措施在降低出错率方面的效果,并分析了这一类优化的效果极限,否定了其必要性,相比之下,针对算法底层的优化更为直接有效。
Public key cryptosystem is an extremely important part in information security field, and its key lies in generating two big primes. Nowadays, although there is polynomial-time definitive primality detec- ting algorithm, such as AKS algorithm, unfortunately its running time could not meet the practical de- mands, therefore, the fast and practical probabilistic primality testing algorithm, Miller-Rabin test, be- comes the main algorithm. However, some detail of Miller-Rabin test is always ignored： it is misjudgment probability not error probability that is directly controlled by the test, while the latter is what indeed needs to decrease. Detailed analysis of this point is given, and meanwahile, the effects of some methods with distribution features of primes to decrease error probability are tested. Finally, result limit is analyzed and its necessity negated. Comparison indicates that, the underlying algorithm is more effective. preprocesslng the optimized optimization of
出处
《通信技术》
2015年第4期469-472,共4页
Communications Technology
基金
国家自然基金项目(No.61371142)
北京市创新团队建设提升计划(No.ID HT20130502)~~
