一种快速生成大素数的方法  

A Method of Fast Prime Number Generation

作　　者：叶文威 马昌社[1] YE Wenwei;MA Changshe(School of Computer Science,South China Normal University,Guangzhou 510631,China)

机构地区：[1]华南师范大学计算机学院,广州510631

出　　处：《华南师范大学学报（自然科学版）》2023年第2期124-128,共5页Journal of South China Normal University(Natural Science Edition)

基　　金：国家自然科学基金项目(61672243)。

摘　　要：基于中国剩余定理对改进的增量素数生成算法进行了改进,设计了基于中国剩余定理的门限素数生成算法(TCPG),以提高大素数生成的效率。具体地说,TCPG算法用中国剩余定理对小素数数组进行随机抽样,然后求解同余方程;在素性测试失败后,不需要对整个小素数数组重新抽样,而是仅抽样门限个随机数,降低了随机数的抽样个数,从而提高素数生成算法效率。最后,对TCPG算法与原生素数生成算法、增量素数生成算法、改进的增量算法、M-J特例算法、改进的M-J算法和中国剩余定理素数生成算法(简称CRT)进行素数生成平均时长的对比分析实验。实验结果表明TCPG算法生成长度为512 bit的素数的平均时长(7.80 ms)略多于改进的增量算法所需时长(7.73 ms),但是,生成长度为1024 bit和2048 bit的素数的平均时长最短:TCPG算法在Miller-Rabin素性测试算法下生成1个长度为512 bit的素数的平均时长为7.80 ms,比CRT算法耗时减少1.46 ms;生成1个长度为1024 bit的素数的平均时长为53.30 ms,比改进的增量素数生成算法、CRT算法耗时分别减少5.50、4.30 ms;生成1个长度为2048 bit的素数的平均时长为505.78 ms,比改进的增量素数生成算法、CRT算法耗时分别减少106.03、54.54 ms。Based on the Chinese remainder theorem,the improved incremental prime number generation algorithm is improved,and the threshold prime number generation algorithm(TCPG)based on the Chinese remainder theorem is designed to improve the efficiency of large prime number generation.Specifically,the TCPG algorithm uses the Chinese remainder theorem to randomly sample small prime arrays to solve the congruence equation;after the failure of the prime test,it is not necessary to resample the entire small prime array,but only to sample the threshold random numbers,reducing the number of random number sampling,thereby improving the efficiency of the prime number generation algorithm.Finally,the TCPG algorithm is compared with the original prime number genera-tion algorithm,the incremental prime number generation algorithm,the improved incremental algorithm,the M-J special case algorithm,the improved M-J algorithm and the Chinese remainder theorem prime number generation algorithm(CRT)to analyze the average time of prime number generation.The experimental results show that the average time of generating 512 bit primes by TCPG algorithm(7.80 ms)is slightly longer than that of the improved incremental algorithm(7.73 ms).However,the shortest average time is required to generate 1024 bit and 2048 bit primes.The average time of generating a 512 bit prime by TCPG algorithm under Miller-Rabiin prime test algorithm is 7.80 ms,which is 1.46 ms less than that of CRT algorithm.It takes 53.30 ms to generate a 1024 bit prime,which is 5.50 ms and 4.30 ms less than that of the improved incremental prime generation algorithm and CRT algorithm respectively.It takes 505.78 ms to generate a 2048 bit prime,which is 106.03 ms and 54.54 ms less than that of the improved incremental prime generation algorithm and CRT algorithm,respectively.

关 键 词：快速素数生成 RSA数字签名算法 公钥密码 中国剩余定理 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]