劉鶯迎

（河南牧業(yè)經(jīng)濟學院信息工程學院，河南 鄭州450000）

1 整數(shù)分解理論

1.1 試除法

對于一般的合數(shù)而言，試除是非常有效的，因為大部分數(shù)都含有小的素因子。有88%的正整數(shù)有小于100 的素因子，有92%的素因子有小于1000 的素因子。所以在實際的應用中，如果不知道關于n 的因子的任何信息，通常會先用小規(guī)模的試除找出可能存在的小因子。

試除法先建立一個素數(shù)表，然后從小到大，依次用素數(shù)試除，直到p 出現(xiàn)時，n 將會被分解，此時一共做了π（p）（π（p）是不大于p 的素數(shù)個數(shù)）次試除。由于π（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 是一個光滑數(shù)時，使用這種方法比較有效。

1.4 橢圓曲線分解算法

橢圓曲線分解算法（Lenstra elliptic-curve factorization，ECM）是在1985 年由Lenstra 提出的[4]，目前通常用來尋找1010到1060之間的素因子。

表1 算法時間復雜度比較

表2 算法的優(yōu)缺點

1.5 數(shù)域篩法

數(shù)域篩法涉及到較為深刻的數(shù)學理論，同時又是一個耗資巨大的計算工程項目。GNFS 分為五個主要步驟：多項式選擇、篩取關系、數(shù)據(jù)過濾、解大型稀疏線性方程組和代數(shù)平方根求解。

1.6 算法優(yōu)缺點比較

根據(jù)對大數(shù)分解算法的總結，我們將各算法的時間復雜度、適用范圍以及優(yōu)缺點[5]進行比較，為下一階段分解策略和算法選擇提供依據(jù)。

2 整數(shù)分解實踐

2.1 1434 比特整數(shù)分解

已知一個無平方因子的正整數(shù)N，求N 的素因子，即求整除N 的素數(shù)。N=298777079680636209728926753957151534560 921684339894725163656346441015377896041311169310959917 171700706622085676826928556518363105076218043402519861 108884785655277921109447616047979259115290265284384151 036883100749922693173993355808366922676333229835998998 497712492287847117477480037575980851247778265980034106 283555720558204023500207676048578837876927418180945214 920194972851554780233917446851793705191199191708506603 506807978474027

在分解之前，首先使用Magma 編寫P-1 算法，對有光滑性的因子進行檢測；接著使用Yafu 工具對其進行自動化地分解，分解出規(guī)模較小的因子；

在Yafu 效率不高之時，使用ECM-GMP 選擇合適的參數(shù)對中等規(guī)模的因子進行分解，最后使用Cado-nfs 使用數(shù)域篩法分解較大的因子，實現(xiàn)完成分解。

我們將所求解到的14 個素因子按規(guī)模從小到大的順序進行編號，依次為N1、N2、N3到N14，分解詳細流程如表3 所示。

表3 分解過程記錄

至此，大數(shù)N 分解為14 個素數(shù)因子，其十進制表示及比特長度如表4 所示。

表4 分解結果公示

2.2 Cado-nfs 并行化

總所周知，大數(shù)分解是一個需要耗費大量計算資源和時間的工程。在2009 年被分解出來的RSA-768 數(shù)，通過并行計算機所花費的CPU 時間大約相當于在基于單核2.2 GHz 的計算機上近2000 年的計算時間。因此對分解算法并行化是提高分解速度的一種可行的方式。

目前，常見的并行化方式有多線程、多進程以及異構加速等多種方式。Cado-nfs 提供了多核多線程以及多處理器多進程的加速方式，在數(shù)域篩法的不同階段都進行了并行處理，比如多項式選擇、篩法、解線性方程組等。

使用Cado-nfs-2.3.0 版本，我們在一個CPU 為Intel Xeon E5-2620 v4 @2.1GHz，16cores 的服務器上對最后383bit 的數(shù)進行多線程的分解，最后耗時大約2 小時20 分鐘成功將其分解，加速比約為9.2。

通過多線程并行的方法，在數(shù)域篩法中耗時較多的格篩和解線性方程組等步驟都有顯著的效率提升，大大縮短了分解的時間。

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

在數(shù)學中，RSA 數(shù)是一組大的半素數(shù)（正好有兩個素因子的數(shù)）。RSA 分解挑戰(zhàn)是RSA 實驗室在1991 年3 月18 日提出的一個挑戰(zhàn)，旨在鼓勵研究計算數(shù)論，以及分解大整數(shù)和破解密碼學中使用的RSA 密鑰。RSA-155 即RSA 數(shù)的十進制規(guī)模為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 天，可見并行化對于數(shù)域篩法分解RSA 數(shù)具有重要的作用。

表5 RSA-155 的因子

3 結論

本文工作在大數(shù)分解理論與實踐的研究有一定的參考與借鑒作用，在前人理論的基礎上，結合目前現(xiàn)有的實現(xiàn)技術，探索并總結出了一套整數(shù)分解的策略與方法，并且將整數(shù)分解與并行計算相結合，有效地促進學科的交叉融合。