常见素性检验算法的比较分析

Comparative Analysis of Common Primality Testing Algorithms

在现代密码系统中,大素数对一些加密系统的建立来说有着不可忽视的作用,如RSA密码系统和椭圆曲线密码体制ECC,作为应用最广和最具有发展潜力的两个密码体系,其安全性都是建立在大素数之上。而大素数的检验显得尤为重要,常见的素性检验算法包括Fermat素性检验、Solovay-Strassen素性检验、Miller-Rabin素性检验、Pocklington素性检验、Lucas-Lehmer素性检验、Pepin素性检验、Lucas素性检验、AKS素性检验等算法。素性检验算法可按照待检验数的形式分为一般形式素性检验算法和特殊形式素性检验算法,也可以按照检验结果的准确性分为概率型素性检验算法以及确定型素性检验算法。本文介绍了上述常见的素性检验的理论算法,并从不同分类、软件实现等方面对这些素性检验算法进行了比较分析,最后得出Miller-Rabin素性检验算法的综合效率最高。

In the modern cryptosystem, large prime number is essential to establishing some encryption systems, e.g. the RSA cryptosystem and the ECC cryptosystem. As the two most popular and potential cryptosystems, the RSA and the ECC build the security based on the large prime number. Testing the large prime number is particularly important and common primality testing algorithms include the Fermat, the Solovay Strassen, the Miller Rabin, the Pocklington, the Lucas Lehmer, the Pepin, the Lucas, the AKS, etc. A primality testing algorithm could be classified as a general form or a special form primality testing algorithm according to the form of the tested number, or as a probabilistic or a deterministic primality testing algorithm according to the accuracy of the test result. In this paper, abovementioned algorithms are introduced, and compared and analyzed from the aspects of classification and software implementation. Theoretical analysis indicates that the Miller Rabin primality testing algorithm has the highest comprehensive efficiency.