基于莱梅素数判定定理的安全素数构造算法

计算机工程与应用 ›› 2016, Vol. 52 ›› Issue (13): 152-156.

基于莱梅素数判定定理的安全素数构造算法

周利荣1，胡天磊2

1.衢州职业技术学院信息工程学院，浙江衢州 324000
2.浙江大学计算机科学与技术学院，杭州 310007

出版日期:2016-07-01 发布日期:2016-07-15

Safe primes construction algorithm based on Laime primes judgment theorem

ZHOU Lirong1, HU Tianlei2

1.School of Information and Engineering, Quzhou College of Technology, Quzhou, Zhejiang 324000, China
2.College of Computer Science and Technology, Zhejiang University, Hangzhou 310007, China

Online:2016-07-01 Published:2016-07-15

摘要/Abstract

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

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

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

周利荣1，胡天磊2. 基于莱梅素数判定定理的安全素数构造算法[J]. 计算机工程与应用, 2016, 52(13): 152-156.

ZHOU Lirong1, HU Tianlei2. Safe primes construction algorithm based on Laime primes judgment theorem[J]. Computer Engineering and Applications, 2016, 52(13): 152-156.