科研之友
微信
新浪微博
Facebook
分享链接
摘要
基于中国剩余定理对改进的增量素数生成算法进行了改进，设计了基于中国剩余定理的门限素数生成算法(TCPG),以提高大素数生成的效率。具体地说，TCPG算法用中国剩余定理对小素数数组进行随机抽样，然后求解同余方程；在素性测试失败后，不需要对整个小素数数组重新抽样，而是仅抽样门限个随机数，降低了随机数的抽样个数，从而提高素数生成算法效率。最后，对TCPG算法与原生素数生成算法、增量素数生成算法、改进的增量算法、M-J特例算法、改进的M-J算法和中国剩余定理素数生成算法(简称CRT)进行素数生成平均时长的对比分析实验。实验结果表明TCPG算法生成长度为512 bit的素数的平均时长(7.80 ms)略多于改进的增量算法所需时长(7.73 ms),但是，生成长度为1 024 bit和2 048 bit的素数的平均时长最短：TCPG算法在Miller-Rabin素性测试算法下生成1个长度为512 bit的素数的平均时长为7.80 ms,比CRT算法耗时减少1.46 ms;生成1个长度为1 024 bit的素数的平均时长为53.30 ms,比改进的增量素数生成算法、CRT算法耗时分别减少5.50、4.30 ms;生成1个长度为2 048 bit的素数的平均时长为505.78 ms,比改进的增量素数生成算法、CRT算法耗时分别减少106.03、54.54 ms。
- 单位
