Abstract: Judgment of large prime numbers plays a key action in the public-key encryption. This paper analyzes common algorithm for large prime numbers judgment：Demytko algorithm, the algorithm put forward by LIU Minghua. It realizes algorithm of constructing prime numbers on the basis of Laime theorem, and obtains large prime numbers after several synthetic and judgment from small prime factors base. The paper gives description of the algorithm and an example to explain, and analyzes time complexity, advantages and disadvantages of algorithm. Data show that the efficiency of the algorithm is better than Demytko algorithm. It uses this algorithm and Demytko algorithm to generate large numbers of the RSA public-key cryptosystem [p、][q] and [n].

Key words: Demytko algorithm, Laime theorem, safe primes

摘要： 大素数的判定在公钥密码体制中起关键作用，分析了用于素数构造的相关定理及常的素数判定算法：Demytko算法、刘明华提出的素数构造算法。在莱梅定理的基础上实现素数构造算法，即由小素数组成的因数基经过多次合成和判断得到大素数;给出算法的描述，举例加以说明;对算法的时间复杂度及优缺点进行分析，实验数据表明算法的效率优于素数构造算法：Demytko。分别用该算法及Demytko算法生成的大素数构造RSA公钥密码体制中的[p、][q]及[n]。

关键词: Demytko算法, 莱梅定理, 安全素数