素数在公钥密码算法中广泛使用，公钥密码算法是基于难解性问题设计的，因此不需要像对称密码算法一样需要安全的信道传输密钥，但是公钥密码算法的计算量和大素数生成的资源开销较大。如：RSA算法^[1]需要生成2个相同比特长度的素数p和q, 然后计算公钥(n, e) (n=p·q)，以及计算私钥d=e^-1 mod φ(n)，其中e为随机数并与φ(n)互素。因为素数具有分布不均匀性，导致素数生成算法依赖于增量算法来寻找随机数的邻近素数，所以大素数的生成开销较大。

最原始生成素数的方法是选取一个随机奇数进行素性测试，如果不是素数则重新选取一个随机奇数，直到找到一个素数^[2]。1980年，RABIN^[3]提出了Miller-Rabin概率素性测试算法，该算法可以概率性检测输入的整数是否为合数。1988年，BEAUCHEMIN等^[4]将Miller-Rabin概率素性测试算法用于检验随机整数是否是素数的可靠性问题。1991年，BRANDT等^[5]对原始素数生成算法进行改进，提出了增量算法：在素性测试失败后，通过加2的方式寻找邻近的素数，从而提高算法效率。1992年，BRANDT和DAMGARD^[6]对文献[5]的增量算法进行了详细的性能分析。2000年，JOYE等^[7]改进了文献[5]的增量算法，降低了素性测试的次数，提出了M-J素数生成算法。2006年，JOYE和PALIIER^[8]对文献[7]提出的M-J素数生成算法的参数选取进行了优化，提出了M-J特例素数生成算法。2011年，雷文等^[9]改进了Miller-Rabin素性测试方法，增加了预测试环节，设计了快速大素数算法；汤鹏志和李彪^[10]基于概率论的方法，改进了Era-tosthenes筛法并构建素数库，通过分析素数库中素数尾数的分类频数和表达式下素数频率，使用Miller-Rabin算法对形如$\prod P_i^m \times n+1$(P_i为小素数)的整数进行校验，设计了快速大素数生成算法。2017年，郑朝霞等^[11]在素性测试阶段，通过并行实现小素数擦拭和Miller-Rabin素性测试，从而减少了小素数单独运算消耗时间。2018年，李峰等^[2]归纳并总结了原生素数生成算法、现代素数生成算法，并进行了性能比较分析。2019年，刘彦鑫^[12]基于中国剩余定理实现素数搜索的算法，研究了素数在多维空间的分布规律，减少在某个区间搜索的整数数量，从而提高了素数搜索的效率。

本文是对改进的增量素数生成算法^[2]进行改进，改进的增量素数生成算法中，起始状态是选取一个与小素数乘积互素的奇数，每次素性测试失败后，重新随机选取奇数，并将其与小素数的乘积求和。改进的增量素数生成算法在生成较短长度(512 bit)的素数时有更好的性能，但是在生成1 024 bit以上长度的素数时的性能较弱。为了得到一个可拓展长度的快速素数生成算法，本文基于中国剩余定理与门限的理念，设计了基于中国剩余定理的门限素数生成算法(TCPG)。具体地说，TCPG算法通过中国剩余定理求解小素数数组的同余方程组，从而获得初始状态；然后，在素性测试失败后，采用门限思想生成门限值个随机数，再求解同余方程组，从而提高素数生成的效率。

1.   TCPG算法

1.1   改进的增量素数生成算法

增量素数生成算法由BRANDT等^[5]提出，后来被抽象成算法1^[2]的形式。两者的区别是：(1)算法1的初始化变量p与小素数乘积μ互素，小素数乘积通常为2×3×5×…×…≤p，其中p表示p的比特长度；(2)增量过程从p=p+2变成了p=p+μ。

表  算法1  改进的增量素数生成算法^[2]

Input：所需素数的比特位数n和小素数乘积$\mu=\prod_{i=1}^{r(n)} p_i$
Output：素数pend while
取与μ互素、长度为n bit的随机奇数p
while T(p)==false do
p=p+μ
返回p

下载: 导出CSV 

| 显示表格

1.2   中国剩余定理素数生成算法

中国剩余定理又称为“孙子定理”，是求解一次同余方程组的方法。设m₁, m₂, …, m_n是两两互素的正整数，有$M=\prod_{i=1}^n m_i$，则同余方程组可表示为:

此方程有唯一解：

其中，M_i=M/m_i, M_i^-1M_i≡1 mod m_i。

中国剩余定理提供了求解同余方程组的方法^[12]，同时还提供了一种数值映射的方法：选取n个两两互素的正整数m₁, m₂, …, m_n，然后求解同余方程组，得到1个与n个小素数互素的准素数。中国剩余定理素数生成算法(算法2)的核心思想是利用这种数值映射方法寻找素数。

表  算法2  中国剩余定理素数生成算法

Input：所需素数比特位数n和小素数乘数$\mu=\prod_{i=1}^{r(n)} p_i$
Output：素数p
预计算:
for i=1 to r(n)do
$\theta_i=\left(\frac{\mu}{p_i}\right)\left[\left(\frac{\mu}{p_i}\right)^{-1} \bmod p_i\right]$
end
主运算: p=0
while T(p)==false do
for i=0 to r(n)do
p=p+x×θi
end end 返回p

下载: 导出CSV 

| 显示表格

1.3   TCPG算法

中国剩余定理素数生成算法在素性测试失败后，需要更新全部随机数后才求解同余方程，导致消耗过多的时间。为了解决此问题，TCPG算法根据素数比特长度选取合适的小素数数组，然后寻找该数组中最优的门限值k(门限值k代表需要更新随机数的个数)；在素性测试失败后仅更新k个随机数，降低随机数的生成个数，从而提高素数生成效率。由于随机数是通过中国剩余定理在小素数数组中计算得到的，因此在素性测试中可以减少小素数擦拭次数，提高素性测试执行效率。为了生成给定区间[q_min, q_max]或其间隔中均匀分布的素数p，由式(1)可知$x=\sum_{i=1}^n r_i M_i M_i^{-1}$。当r_i=1时，$x=\sum_{i=1}^n M_i M_i^{-1}$, 为最小值；当r_i=p_i时，$x=\sum_{i=1}^n p_i M_i M_i^{-1}$，为最大值。则x∈$\left[\sum_{i=1}^n M_i M_i^{-1}, \sum_{i=1}^n p_i M_i M_i^{-1}\right] \in\left[q_{\min }, q_{\max }\right]$(如图 1所示)，其中r(n)是一个关于n的整数函数，满足2×p₂×…×p_r(n)+1≥n。

图  1  x的值域

Figure  1.  Range of x

下载: 全尺寸图片 幻灯片

TCPG算法可以先通过预计算同余方程中的M_iM_i^-1来减少每轮的计算量，然后通过更新门限个随机数来重构素数p，具体如算法3所示。

表  算法3  TCPG算法

Input：所需素数比特位数n、Π、门限值t
Output：素数p
预计算:
for i=1 to r(n)do
$\theta_i=\left(\frac{\Pi}{p_i}\right)\left[\left(\frac{\Pi}{p_i}\right)^{-1} \bmod p_i\right]$
end
主运算:
c=0, p=0
for i=1 to r(n)-t do
c=c+x×θi
end
while T(p)==false do
p←c
for i=r(n)-t to r(n)do
p=p+x×θi
end
end
返回p

下载: 导出CSV 

| 显示表格

2.   实验结果与性能分析

本节将首先探究TCPG算法的门限值k对素数生成平均时长的影响，然后基于Miller-Rabin概率素性测试算法^[3]，将TCPG算法与原生素数生成算法、增量素数生成算法^[5]、改进的增量算法^[2]、M-J特例算法^[7]、改进的M-J算法^[8]和中国剩余定理素数生成算法^[12](简称CRT)进行对比实验。

2.1   门限值对TCPG算法的性能影响

首先，分析不同门限值k对TCPG算法的性能影响。为了寻找小素数数组中的最优门限值k，研究当TCPG算法生成不同长度的素数时，不同门限值对素数生成平均时长的影响。实验环境为Go语言编程，运行在Intel i3-8350K@4.00 GHz处理器上，对每个k进行10 000次实验。

由图 2可知随机数的更新个数和素数生成平均时长没有明显的线性关系，因此，不同小素数的组合都需要通过实验来确定该数组的最优门限值k。本文采用的小素数数组在TCPG算法中生成1个长度为512 bit的素数的最优门限值k为6，所需平均时长为7.80 ms；生成1个长度为1 024 bit的素数的最优门限值k为3，所需平均时长为53.30 ms；生成1个长度为2 048 bit的素数的最优门限值k为18，所需平均时长为505.78 ms。

图  2  TCPG算法的不同k值性能分析图

Figure  2.  Performance analysis diagram of different k values of TCPG algorithm

下载: 全尺寸图片 幻灯片

2.2   素数生成算法性能分析

测试环境为Go语言编程, 运行在Intel i3-8350K@4.00 GHz处理器上；TCPG算法在生成长度分别为512、1 024、2 048 bit的素数的门限值均为2.1节得到的最优门限值。

由平均时长和平均素性判定次数(表 1)可知TCPG算法生成1个长度为512 bit的素数的平均时长略多于改进的增量算法所需时长，但是，在生成长度为1 024 bit和2 048 bit的素数的平均时长最短：TCPG算法生成1个长度为512 bit的素数的平均时长为7.80 ms，比CRT算法降低了18.6%；生成1个长度为1 024 bit的素数的平均时长为53.30 ms, 比CRT素数降低了7%；生成1个长度为2 048 bit的素数的平均时长为505.78 ms, 比CRT算法降低了5%。

表  1  素数生成算法性能分析

Table  1.  Performance analysis of prime number generation algorithm

素数长度	平均时长/ms
	原生素数生成算法	增量素数生成算法	改进的增量算法	M-J特例算法	改进的M-J算法	CRT算法	TCPG算法
512	9.64	9.57	7.73	18.70	9.97	9.26	7.80
1 024	76.78	75.97	58.80	996.72	56.00	57.33	53.30
2 048	827.12	830.57	611.81	4 028.00	560.32	532.20	505.78
素数长度	平均素数判定次数
	原生素数生成算法	增量素数生成算法	改进的增量算法	M-J特例算法	改进的M-J算法	CRT算法	TCPG算法
512	176	174	32	190	112	49	50
1 024	354	351	66	709	120	59	58
2 048	705	710	134	1 062	240	108	109

下载: 导出CSV 

| 显示表格

另外，实验算法统一进行30次Miller-Rabin概率素性测试，每个算法生成的素数可信度为(1-(1/4)³⁰)*100%≈100%，也就是说，实验在生成十万个大素数的情况下，最多只有0个假素数，因此实验的结果是可信的。

3.   结论

为了提高大素数生成的效率，本文基于中国剩余定理对改进的增量素数生成算法进行了改进，设计了基于中国剩余定理的门限素数生成算法(TCPG)。然后基于Miller-Rabin素性测试算法，将TCPG算法与原生素数生成算法、增量素数生成算法、改进的增量算法、M-J特例算法、改进的M-J算法和中国剩余定理素数生成算法(简称CRT)进行对比实验。实验结果表明TCPG算法生成1个长度为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。

本文仅给出了TCPG算法的实现和性能分析，实际应用时需考虑侧信道信息的泄露^[13]和算法的安全性问题^[14]；若要用于RSA方案，则还需要保证使用的是强素数^[15]。