大整数分解算法的设计与实现

2020-12-15刘莺迎

科学技术创新 2020年36期

刘莺迎

（河南牧业经济学院信息工程学院，河南郑州450000）

1 整数分解理论

1.1 试除法

对于一般的合数而言，试除是非常有效的，因为大部分数都含有小的素因子。有88%的正整数有小于100 的素因子，有92%的素因子有小于1000 的素因子。所以在实际的应用中，如果不知道关于n 的因子的任何信息，通常会先用小规模的试除找出可能存在的小因子。

试除法先建立一个素数表，然后从小到大，依次用素数试除，直到p 出现时，n 将会被分解，此时一共做了π（p）（π（p）是不大于p 的素数个数）次试除。由于π（p）≈p/1np，寻找到素因子大约需要π（p）次试除。

1.2 Pollard rho 方法

Pollard rho 方法[1，2]，也叫蒙特卡罗方法，是Pollard 于1975年提出的一种分解算法，Brent 于1980 年对其进行了改进，该算法适用于分解10-20digit 的n 的素因子。

1.3 P-1 方法

Pollard 在提出了Pollard rho 方法之后不久，还提出了另一种方法，称为P-1 方法[2，3]。假设当n 有素因子p，并且p-1 是一个光滑数时，使用这种方法比较有效。

1.4 椭圆曲线分解算法

椭圆曲线分解算法（Lenstra elliptic-curve factorization，ECM）是在1985 年由Lenstra 提出的[4]，目前通常用来寻找1010到1060之间的素因子。

表1 算法时间复杂度比较

表2 算法的优缺点

1.5 数域筛法

数域筛法涉及到较为深刻的数学理论，同时又是一个耗资巨大的计算工程项目。GNFS 分为五个主要步骤：多项式选择、筛取关系、数据过滤、解大型稀疏线性方程组和代数平方根求解。

1.6 算法优缺点比较

根据对大数分解算法的总结，我们将各算法的时间复杂度、适用范围以及优缺点[5]进行比较，为下一阶段分解策略和算法选择提供依据。

2 整数分解实践

2.1 1434 比特整数分解

已知一个无平方因子的正整数N，求N 的素因子，即求整除N 的素数。N=298777079680636209728926753957151534560 921684339894725163656346441015377896041311169310959917 171700706622085676826928556518363105076218043402519861 108884785655277921109447616047979259115290265284384151 036883100749922693173993355808366922676333229835998998 497712492287847117477480037575980851247778265980034106 283555720558204023500207676048578837876927418180945214 920194972851554780233917446851793705191199191708506603 506807978474027

在分解之前，首先使用Magma 编写P-1 算法，对有光滑性的因子进行检测；接着使用Yafu 工具对其进行自动化地分解，分解出规模较小的因子；

在Yafu 效率不高之时，使用ECM-GMP 选择合适的参数对中等规模的因子进行分解，最后使用Cado-nfs 使用数域筛法分解较大的因子，实现完成分解。

我们将所求解到的14 个素因子按规模从小到大的顺序进行编号，依次为N1、N2、N3到N14，分解详细流程如表3 所示。

表3 分解过程记录

至此，大数N 分解为14 个素数因子，其十进制表示及比特长度如表4 所示。

表4 分解结果公示

2.2 Cado-nfs 并行化

总所周知，大数分解是一个需要耗费大量计算资源和时间的工程。在2009 年被分解出来的RSA-768 数，通过并行计算机所花费的CPU 时间大约相当于在基于单核2.2 GHz 的计算机上近2000 年的计算时间。因此对分解算法并行化是提高分解速度的一种可行的方式。

目前，常见的并行化方式有多线程、多进程以及异构加速等多种方式。Cado-nfs 提供了多核多线程以及多处理器多进程的加速方式，在数域筛法的不同阶段都进行了并行处理，比如多项式选择、筛法、解线性方程组等。

使用Cado-nfs-2.3.0 版本，我们在一个CPU 为Intel Xeon E5-2620 v4 @2.1GHz，16cores 的服务器上对最后383bit 的数进行多线程的分解，最后耗时大约2 小时20 分钟成功将其分解，加速比约为9.2。

通过多线程并行的方法，在数域筛法中耗时较多的格筛和解线性方程组等步骤都有显著的效率提升，大大缩短了分解的时间。

2.3 Caod-nfs 多线程分解RSA-155

在数学中，RSA 数是一组大的半素数（正好有两个素因子的数）。RSA 分解挑战是RSA 实验室在1991 年3 月18 日提出的一个挑战，旨在鼓励研究计算数论，以及分解大整数和破解密码学中使用的RSA 密钥。RSA-155 即RSA 数的十进制规模为155 位（2 进制为512 位）。

RSA-155 的值如下所示。

RSA155=1094173864157052742180970732204035761200373 294544920599091384213147634998428893478471799725789126 733249762575289978183379707653724402714674353159335433 3897

我们使用Cado-nfs 尝试对RSA-155 进行分解，最终耗时7天6 小时。目前使用Cado-nfs 串行分解RSA-155 大约需要83天，而在Intel Xeon E5-2620 v4 @2.1GHz，16cores 上并行分解仅需要7 天，可见并行化对于数域筛法分解RSA 数具有重要的作用。