大整數(shù)分解算法的設(shè)計(jì)與實(shí)現(xiàn)

劉鶯迎

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

1 整數(shù)分解理論

1.1 試除法

對(duì)于一般的合數(shù)而言，試除是非常有效的，因?yàn)榇蟛糠謹(jǐn)?shù)都含有小的素因子。有88%的正整數(shù)有小于100 的素因子，有92%的素因子有小于1000 的素因子。所以在實(shí)際的應(yīng)用中，如果不知道關(guān)于n 的因子的任何信息，通常會(huì)先用小規(guī)模的試除找出可能存在的小因子。

試除法先建立一個(gè)素?cái)?shù)表，然后從小到大，依次用素?cái)?shù)試除，直到p 出現(xiàn)時(shí)，n 將會(huì)被分解，此時(shí)一共做了π（p）（π（p）是不大于p 的素?cái)?shù)個(gè)數(shù)）次試除。由于π（p）≈p/1np，尋找到素因子大約需要π（p）次試除。

1.2 Pollard rho 方法

Pollard rho 方法[1，2]，也叫蒙特卡羅方法，是Pollard 于1975年提出的一種分解算法，Brent 于1980 年對(duì)其進(jìn)行了改進(jìn)，該算法適用于分解10-20digit 的n 的素因子。

1.3 P-1 方法

Pollard 在提出了Pollard rho 方法之后不久，還提出了另一種方法，稱為P-1 方法[2，3]。假設(shè)當(dāng)n 有素因子p，并且p-1 是一個(gè)光滑數(shù)時(shí)，使用這種方法比較有效。

1.4 橢圓曲線分解算法

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

表1 算法時(shí)間復(fù)雜度比較

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

1.5 數(shù)域篩法

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

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

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

2 整數(shù)分解實(shí)踐

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

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

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

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

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

表3 分解過(guò)程記錄

至此，大數(shù)N 分解為14 個(gè)素?cái)?shù)因子，其十進(jìn)制表示及比特長(zhǎng)度如表4 所示。

表4 分解結(jié)果公示

2.2 Cado-nfs 并行化

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

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

使用Cado-nfs-2.3.0 版本，我們?cè)谝粋€(gè)CPU 為Intel Xeon E5-2620 v4 @2.1GHz，16cores 的服務(wù)器上對(duì)最后383bit 的數(shù)進(jìn)行多線程的分解，最后耗時(shí)大約2 小時(shí)20 分鐘成功將其分解，加速比約為9.2。

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

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

在數(shù)學(xué)中，RSA 數(shù)是一組大的半素?cái)?shù)（正好有兩個(gè)素因子的數(shù)）。RSA 分解挑戰(zhàn)是RSA 實(shí)驗(yàn)室在1991 年3 月18 日提出的一個(gè)挑戰(zhàn)，旨在鼓勵(lì)研究計(jì)算數(shù)論，以及分解大整數(shù)和破解密碼學(xué)中使用的RSA 密鑰。RSA-155 即RSA 數(shù)的十進(jìn)制規(guī)模為155 位（2 進(jìn)制為512 位）。

RSA-155 的值如下所示。

RSA155=1094173864157052742180970732204035761200373 294544920599091384213147634998428893478471799725789126 733249762575289978183379707653724402714674353159335433 3897

我們使用Cado-nfs 嘗試對(duì)RSA-155 進(jìn)行分解，最終耗時(shí)7天6 小時(shí)。目前使用Cado-nfs 串行分解RSA-155 大約需要83天，而在Intel Xeon E5-2620 v4 @2.1GHz，16cores 上并行分解僅需要7 天，可見(jiàn)并行化對(duì)于數(shù)域篩法分解RSA 數(shù)具有重要的作用。

表5 RSA-155 的因子

3 結(jié)論

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