改进的整数因子分解方法：顺序与并行算法 Ehab T. Alnfrawy, Hazem M. Bahig, Hatem M. Bahig 以及 Reda Elbarougy

《Symmetry》：Enhanced Integer Factorization Method: Sequential and Parallel Approaches Ehab T. Alnfrawy, Hazem M. Bahig, Hatem M. Bahig and Reda Elbarougy

　　摘要 整数分解在非对称密码系统中起着基础性作用，特别是在Rivest、Shamir和Adleman（RSA）密码系统中。本文从序列和并行计算的角度改进了整数分解算法。该算法基于多项式评估和最大公约数（GCD）的原理。这些改进的目的是减少寻找质因数过程中的执行时间和内存消耗。实验中，我们使用了不同的参数值：（1）位数n，（2）两个因子之间的差值，以及（3）并行模型中的处理器数量。实验结果表明，无论是序列方法还是并行方法，在两个因子之间的差值较大的情况下，都能显著提高运行时间和内存使用效率。平均而言，运行时间得到了提升，而内存消耗降低到了一个常数水平。这一特性对于资源有限的硬件设备非常重要。此外，所提出的并行方法展现了良好的可扩展性，并实现了亚线性加速。

1. 引言
整数分解（IF）是指将一个合数分解为较小的整数（理想情况下为质数）的乘积的问题。更正式地说，给定一个正整数N，目标是找到其质因数p1, p2, ..., pn，使得N = p1 * p2 * ... * pn。在经典计算机上，这是一个困难的问题，特别是当N是两个大质数的乘积时[1]，因为迄今为止还没有多项式算法可以解决这个问题。整数分解在多种公钥非对称密码系统的设计和安全性中起着核心作用，例如Rivest、Shamir和Adleman（RSA）系统[2]。RSA加密使用模指数运算和公钥e，而解密则需要利用私钥d，私钥d可以通过Euler的欧拉函数得到。由于在不分解N的情况下计算e是不可能的，只要整数分解在计算上是困难的，RSA就能保持安全[3]。找到私钥有助于分解模数N[4]。

几十年来，人们开发了多种基于不同方法的整数分解算法，包括：（1）确定性或概率性方法，（2）通用或专用方法，以及（3）序列或并行方法。试除法从2开始测试所有奇数，直到N被整除为止[5]。这种方法通过构建一个“轮子”（wheel factorization method）进行了优化，该轮子跳过了前几个质数的倍数[6,7]。Fermat的方法基于这样一个事实：任何合数都可以表示为两个平方数的差的形式，即N = a^2 - b^2。因此，算法从a开始，如果a是一个完全平方数，则尝试找到b；否则，将a增加1[8]。

Strassen分解（SF）方法利用批量GCD计算和快速多项式运算来检测N的质因数[9]。Pollard的Rho方法是一种适用于具有小质因数的数的概率性方法[10,11]。Pollard的方法[12]用于找到只有小质因数的数N的质因数p。椭圆曲线（EC）方法通过操作椭圆曲线来推广Pollard的方法[13,14]。在EC方法中，随机选择椭圆曲线和点，执行标量乘法，并使用GCD来提取因数。二次筛选（QS）方法基于寻找两个整数x和y使得x^2 mod N = y^2的想法，这种同余关系可以导致N的一个非平凡因数[15,16]。广义数域筛选（GNFS）通过在代数数域中工作而非仅限于整数来扩展QS方法的思想[17]。Lehman分解方法结合了试除法和受Fermat方法启发的平方检查策略[18]。Lehman方法的改进在于寻找一个平方等式，同时优化了k的选择方式，并结合了提前终止技术、筛选预处理和模运算过滤来排除无效候选者。

在本文中，我们提出了一种基于多项式评估函数和GCD的改进整数分解算法。此外，该算法还依赖于反向搜索质因数的方法。该算法的目标是将SF算法的内存复杂度降低到适合资源有限硬件设备的程度。所提出的算法能够分解位数为n的数N。我们将所提出的算法与SF算法进行了比较。该算法的思路受到了SF算法的启发，但不使用子产品树和多点评估。SF算法有几个优点：
(1) 它是一个确定性算法。
(2) Strassen方法是第一个突破确定性整数分解指数时间障碍的算法，实现了大约O(log^2 n)的亚指数运行时间，显著优于简单的试除法。
(3) 与启发式或随机方法（如EC、GNFS）不同，Strassen方法提供了可证明的最坏情况运行时间保证，这在理论密码学或形式分析中非常有价值。
(4) Strassen的方法启发了后续的理论改进。Hittmeir[20]引入了一种babystep–giantstep方法用于确定性整数分解，运行时间大约为O(log^3 n)，这是对长期以来由超多项式因子界定的Strassen/Pollard–Strassen类型的首次重大改进[21]。Hittmeir[9]为Lehman的确定性分解方法开发了时间和空间的权衡，得到了O(log^3 n * log(log n))的运行时间，这是对经典确定性界限的首次指数级改进。Harvey[22]将一般的确定性分解界限提高到O(log^3.5 n * log(log n))，超越了Hittmeir的结果，并建立了这一领域中已知的最佳通用确定性复杂度。Harvey和Hittmeir[23]通过改进次要因子并将主要指数保持不变，将结果进一步提高[24]。

另一方面，关于改变两个因子之间的差值对SF算法运行时间的影响尚未在实验中进行研究。据我们所知，也没有研究论文探讨过使用高性能系统来解决SF算法的问题。

本文包括引言和四个部分。第2节概述了与SF算法相关的基本概念。第3节详细解释了所提出算法的各个步骤。第4节讨论了将所提出算法与SF算法进行比较的实验研究。最后，第5节提出了结论并探讨了与所提解决方案相关的开放性问题。

2. SF算法
在本节中，我们简要介绍了作为所提算法基础的SF算法，并对其进行了一些修改。假设N是一个合数，p和q是满足p * q = N的两个质数。

由Volker Strassen（1977年）[24]提出的SF算法是一种确定性方法，用于分解合数N，它利用批量GCD计算和快速多项式运算来检测N的质因数[25]。与试除法不同，SF算法可以同时将大量候选因子编码到一个多项式中，从而显著降低计算复杂度。SF算法的主要步骤在算法1中给出。首先，SF算法生成两个集合B和S，满足以下条件：（1）这两个集合在模N下不相交；（2）这两个集合在模p或q下也不相交。Hittmeir[9]按照以下方式构造了这两个集合：

SF算法包括两个主要阶段。在第一阶段（算法1的第6-7行），算法使用多项式函数在模N下计算集合S中的元素：f(B) = ∑ a_i * b_i mod N，其中a_i是集合B的元素个数。计算S中元素的多项式函数的结果存储在辅助数组Y中。这个阶段可以使用子产品树算法来计算f，并采用多点评估技术来计算f(B)。

在第二阶段（算法1的第8-24行），算法计算GCD(f(B), N)。如果f(B) * N等于N，那么f(B)就是N的一个因数。如果f(B) * N不等于N，这意味着N存在非平凡因数，当f(B) * N大于1时可以确定这一点。在这种情况下，算法终止，无需再执行第8行的主循环。

3. 提出的解决方案
在本节中，我们从多个角度详细描述了一种改进的整数分解算法，包括内存和时间消耗。本节包括三个小节。在3.1节中，我们对SF算法的计算时间和内存使用情况提出五点评论。在3.2节中，我们对SF算法的评论提出了解决方案。在3.3节中，我们对所提出算法的复杂性进行了分析。

3.1. 对SF算法的评论
从内存消耗和计算时间的角度分析SF算法，我们发现了以下五个观察结果：
首先，随着n的增加，SF算法的内存消耗迅速增加。SF算法使用了四个辅助数组B、S、Y和G，每个数组的大小为d。每个数组的内存消耗量为d * n。图1展示了随着位数n的增加，内存消耗如何增加。在改进后的SF算法中，我们将内存需求降低到了一个常数级别。
其次，辅助数组G和Y中的元素只使用一次，这意味着在应用GCD函数之前和之后都不需要保留这些元素。此外，我们可以生成数组S和B中的元素，而不需要预先计算或生成，因为这些元素的结构简单，易于使用且无需预先计算。我们只需要两个变量来存储多项式函数和GCD的应用结果。这两个变量的值将在外层循环的每次迭代（算法1的第8行）中更新。
第三，在某些情况下，SF算法在计算所有S元素的多项式函数上花费了大量计算时间，尽管这些计算在测试过程中并未被使用。例如，如果数组S的开始处存在一个满足条件的元素，那么计算所有这些元素的时间就是浪费的。
另外，第一阶段的运行时间显著长于第二阶段的运行时间。例如，假设N = 70,919,611,552,003，第一阶段的运行时间为O(n * log(n))，而第二阶段（用于找到第一个因数）的运行时间为O(log(n) * log(log n))，其中n = √N。因此，我们不需要先计算所有S元素的多项式函数，然后逐一测试，而是先计算x和y的多项式函数，然后再测试结果。如果存在质因数，则算法终止；否则，算法会选取S中的另一个元素并重复该过程。
第四，在RSA密码系统中，模数N是两个质数p和q的乘积，每个质因数的大小为log(n)。这意味着在实际应用中，找到小的质因数并没有实际意义。因此，从数组S的末尾开始寻找解的概率比从开头开始搜索要高。这导致了从向前测试数组S的元素转变为采用向后策略。第五个观察结果是，可以对S的元素应用多项式函数f，然后对每次迭代的结果计算 gcd，这两个操作可以独立进行。这意味着如果我们有一个由t个线程组成的并行模型，我们可以同时测试t个元素。由于使用了并行计算，这显著提高了运行时间。如果并行模型包含大量线程，我们还可以在计算两个函数f和GCD时利用并行性。此外，我们还可以并行化算法1中的第15行的内循环。

3.2 算法
在本小节中，我们将解释如何解决与SF算法分解N相关的五个观察结果。对于前四个观察结果，我们提出了一个基于多项式评估函数和GCD的顺序改进算法，而最后一个观察结果代表了提出的并行算法。算法2展示了改进算法（ISF）的伪代码。该算法首先使用第1、2和3行中概述的方法计算d的值。在第4行，算法采用反向方法开始计算，从较大的j值（等于d）开始，逐步缩小到最小的值。反向循环用于克服第四个观察结果。此外，不需要像在算法1的第4和5行中那样构建集合B和S。在第5行，调用多项式函数f，并且不使用辅助数组S和B，也不将结果保存在辅助数组Y和G中。第6行将应用GCD函数的结果保存在一个大小为1的辅助变量y中，并且这个变量将在每次迭代中更新。这克服了第二个观察结果。此外，这一步还通过减少对未测试元素的时间消耗来克服了第三个观察结果。第7-11行与SF算法相似。在第13行，算法使用该值而不是使用两个辅助数组S和B。同样，应用GCD的结果保存在辅助变量y中，而不是保存在辅助数组G中，以测试找到质因数的可能性。元素属于集合S。因此，第一步是计算。如果GCD的结果大于1或小于N，算法返回，其中来自f的定义和集合B。否则。这意味着每一个质因数都整除乘积：注意到元素不属于集合B（非正整数）。因此，直接计算和不是任意的，而是由数论保证的，用于 expos N 的因子。

算法2 改进的整数分解（ISF）
要求：一个大小为n位的复合正整数N。
确保：N的两个因子p和q，或者没有找到因子。
1:
2:
3:
4:
for 下降到1 do
5:
...
6:
...
7:
if
then
8:
...
9:
...
10:
return p, q
11:
else if
then
12:
for 到d do
13:
...
14:
if
then
15:
...
16:
...
17:
return p, q
18:
end if
19:
end for
20:
end if
21: end for
22:
return "没有找到因子"
根据第五个观察结果，我们提出了两种ISF算法的并行实现。第一种提出的并行算法仅基于ISF的外循环的并行化；即一级并行化。第二种提出的并行算法基于多级并行化。第一级并行化是外循环，而第二级并行化使用外循环体中的并行性，包括并行化两个函数f和GCD以及内循环（ISF算法中的第13行）。

算法3 描述了并行化ISF算法的第一个方向，称为PISF。在这种算法中，t个线程同时工作，通过为每个线程分配一次迭代来并行化外循环。最初，线程i被分配给迭代，如第6行所示。然后每个线程按顺序工作，如ISF算法中的第8-23行所示。如果当前迭代没有找到质因数，线程i将j的值更新为，如第24行所示，并重复相同的过程，如第7行所示，直到某个线程找到质因数（found = true）或外循环终止且整数N为质数。

并行化ISF算法的第二个方向基于以下额外部分的并行化：
(1) 使用并行前缀乘积和并行乘法算法[26,27,28,29,30,31]来并行化函数f。
(2) 并行化函数GCD [32,33]。
(3) 使用m个线程并行化算法3中的第15行内循环。

算法3 并行改进的整数分解（PISF）
要求：一个大小为n位的复合数N，以及t个线程。
确保：N的两个因子p和q，或者没有找到因子。
1:
2:
3:
4:
found = false
5:
for 到t do parallel
6:
...
7:
while (found == false) and () do
8:
...
9:
...
10:
if
then
11:
...
12:
...
13:
found = true
14:
else if
then
15:
for 到d do
16:
...
17:
...
18:
...
19:
found = true
20:
end if
21:
end for
22:
end if
23:
end if
24:
end while
25:
end if
26:
if found == true then
28:
return p, q
29:
else
30:
return "没有找到因子"

3.3 复杂性分析
在本小节中，我们根据运行时间和内存消耗来衡量所提算法的复杂性。
对于算法2，时间复杂度由限定，其中d表示外循环的总迭代次数（第4行），而和分别是函数f和GCD的时间复杂度。假设是两个大小为位整数的乘法成本。因此，在计算中，我们将其视为d个每个大小为位的整数的乘法。由于的时间复杂度大于，ISF算法的时间复杂度为。在最佳情况下，ISF算法在外循环的几次迭代后找到质因数，因此ISF算法的时间复杂度降低到。相比之下，SF算法在最佳情况下的时间复杂度为位。

算法2的内存消耗为，因为该算法在计算过程中使用固定数量的辅助变量。

对于算法3，时间复杂度为，而内存消耗为。PISF算法减少了SF和ISF算法的时间复杂度和内存消耗。

4. 实验研究
在本节中，我们对三种算法：SF、ISF和PISF的时间和内存消耗进行了实验研究。此外，我们还研究了随着线程数量增加，提出的算法PISF的加速比和可扩展性。本节分为三个小节。第一个小节涵盖了评估三种算法——SF、ISF和PISF的实验性能的方法论。在第二小节中，我们展示了所提出的顺序算法ISF与其他算法相比的性能。在最后一个小节中，我们展示了并行算法PISF与顺序算法相比的性能。

4.1 方法论
我们有两种测量所提算法性能的方向。
第一个方向与顺序计算相关，我们根据运行时间和内存消耗来比较两种算法SF和ISF。ISF算法的运行时间改进百分比等于。
第二个方向与并行计算相关，我们使用多个标准来评估所提出的并行算法PISF，包括运行时间、加速比、效率以及可扩展性。并行解决方案的加速比是顺序算法ISF的运行时间与并行解决方案PISF的运行时间的比率。如果加速比为，则加速比为线性的；如果加速比为，则加速比为亚线性的。并行算法的效率是其加速比与处理器数量的比率。
对于这两种方向，我们使用C语言实现所有算法，并使用一个名为GNU Multiple Precision (GMP) [34]的库来处理大整数。我们还利用Open Multi-Processing (OpenMP) [35]来实现PISF中的并行区域。所有程序都在一台配备了2.5 GHz处理器的机器上运行，并在Linux操作系统下工作。对于并行程序，系统可以同时运行16个线程。此外，计算机具有15 MB的缓存内存和32 GB的RAM。
对于所有实验研究，我们生成了一个测试数据集，该数据集验证了以下属性：
1. 每个质因数的大小为，因为在实际应用（如RSA）中，模数N的大小n是两个相同大小的质数的乘积。此外，如果质因数的大小较小，试除法和轮询方法是找到它的有效策略。
2. 两个质因数之间的差异被d限制。
因此，通过生成一个大小为的随机质数p来构造一个大小为n位的随机整数N。然后我们生成另一个大小为的质数q，使得的大小为，其中。对于从到开始的固定n和值，我们生成50个实例来验证测试数据集的属性。
用于比较各种算法的主要指标是运行时间。对于固定的n和，通过取50个实例的运行时间的平均值来测量每种算法的运行时间。对于第一个方向（顺序计算），我们对两种算法SF和ISF都只使用一个线程。对于第二个方向（并行性），我们在相同的数据上使用不同数量的线程（2、4、8和16）运行PISF。此外，在第二个方向中，我们计算其他指标，例如（1）加速比测量，即ISF的运行时间除以PISF的运行时间；（2）效率测量，即ISF的运行时间除以PISF的运行时间与线程数量的乘积。n的值分别为和88。

4.2 ISF的性能
为了测量所提算法ISF的性能，我们将其与SF算法进行比较。表1显示了两种算法SF和ISF在不同n值上的运行时间。结果表明以下观察结果：
表1. SF和ISF算法在不同n和值上的运行时间。对于每个n和，SF和ISF算法的运行时间之间存在显著差异；见表3和4列。例如，当位且两个质因数之间的差异为16位时，SF和ISF算法的运行时间分别为0.521秒和11.358秒。
对于所有研究的案例，ISF算法相对于SF算法的平均改进百分比为，这比SF算法有显著改进。
对于小于64位的固定n值，原始算法SF的运行时间是可接受的，因为它最多只需要几分钟。另一方面，当位时，SF的运行时间迅速增加。
图2展示了当的50个实例的ISF算法执行时间。图2. 对于和，ISF算法的50个实例的运行时间。对于小于64位的固定n值，ISF的运行时间非常快。对于位，SF的运行时间相当长（超过一小时），因此我们忽略了对其的测量。在测量PISF的性能时将测量ISF的运行时间。

4.3 PISF的性能
为了测量PISF算法的性能，我们在上一节中使用相同的数据，用不同数量的线程运行它，n的值分别为72、80和88，因为当n的值低于这个数量时，ISF算法的运行时间较短。此外，为了测量PISF算法的加速效果，我们在相同的数据集上使用一个线程运行ISF算法。图3展示了不同线程数下PISF算法与ISF算法的性能比较。从图3中我们可以观察到以下几点：

图3. 使用不同线程数运行ISF和PISF算法的所需时间。随着线程数的增加，并发性显著降低了ISF的运行时间。PISF具有可扩展性，这意味着增加线程数可以减少其运行时间。例如，当线程数为1时，ISF的运行时间为166.22秒，而使用2、4、8和16个线程时，PISF的运行时间分别为...（具体数值在原文中未给出）。在使用两个线程的情况中，ISF算法的平均运行时间改善百分比约为...（具体百分比在原文中未给出）；当使用四个线程时，这一百分比增加到...；使用八个和十六个线程时，PISF分别将ISF的运行时间改善了...和...。使用2、4、8和16个线程时，PISF的平均加速比分别为1.78、3.64、7.1和12.9，这意味着PISF的加速效果几乎是线性的。使用2、4、8和16个线程时，PISF的平均效率分别为0.89、0.91、0.88和0.81。

5. 结论与未来工作
我们讨论了如何使用多项式评估函数和最大公约数将一个数分解为两个质因数。所提出的算法采用了反向策略来寻找因子。为了减少内存使用和提高运行速度，我们提出了两种算法：顺序算法和并行算法。实验研究表明，这些算法在内存使用和运行时间方面优于其他算法。此外，并行解决方案具有亚线性加速比且具有可扩展性。

未来研究的方向包括：
（1）如何减小集合S和B的大小？
（2）如何实现所提出算法的第二级并行化？
（3）如何使用图形处理单元（GPU）来实现所提出的并行算法？