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

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

Preprocessing Limit of Miller-Rabin Test

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 detecting algorithm, such as AKS algorithm, unfortunately its running time could not meet the practical demands, therefore, the fast and practical probabilistic primality testing algorithm, Miller-Rabin test, becomes 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 preprocessing methods with distribution features of primes to decrease error probability are tested. Finally, the optimized result limit is analyzed and its necessity negated. Comparison indicates that, the underlying optimization of algorithm is more effective.