關(guān)于大整數(shù)分解的方法探究

楊晨鶴　王周寧馨　張禎

摘 要：RSA是目前被廣泛應(yīng)用的公鑰密碼加密體制之一，其核心等同于大整數(shù)分解。文章對大整數(shù)分解問題提出新想法。分別就探索素?cái)?shù)在二進(jìn)制下的0與1的個(gè)數(shù)比例、平方整數(shù)分解方法、多項(xiàng)式分解方法三個(gè)方面，展開探究，給出可實(shí)現(xiàn)的算法，對每種方法的可行性進(jìn)行分析，并結(jié)合簡單例子，予以實(shí)踐驗(yàn)證。研究0-1比例運(yùn)用三次樣條差值的擬合，說明了素?cái)?shù)分布規(guī)律有一定的隨機(jī)性；平方整數(shù)分解是費(fèi)馬經(jīng)典算法的延伸，巧妙利用Lasvegas算法逼近分解所需的平方數(shù)；多項(xiàng)式分解方法則是將問題對應(yīng)到一元高次多項(xiàng)式的分解問題上，其解決依賴于已有的多項(xiàng)式分解的理論。

關(guān)鍵詞：大整數(shù)分解 平方整數(shù)分解 多項(xiàng)式分解 RSA

中圖分類號(hào)：TP338.8 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2015）03（a）-0243-02

因子分解從其誕生到現(xiàn)在已有數(shù)百年的歷史，然而真正引起數(shù)學(xué)家、密碼學(xué)家及計(jì)算機(jī)科學(xué)家的極大關(guān)注卻是近十幾年的事，最直接的原因是因?yàn)橐恍┬碌拿艽a體系及簽名格式的安全性被認(rèn)為是基于大整數(shù)因子分解的難解性。而對RSA中大整數(shù)的攻擊有以下兩個(gè)方面：（1）計(jì)算機(jī)革新，運(yùn)算型攻擊。量子計(jì)算機(jī)的誕生使RSA受到了一定的威脅；（2）算法的革新，從古老的費(fèi)馬算法到連分?jǐn)?shù)攻擊，二次篩因子法，以及橢圓曲線法，也逐漸有效地縮短了攻擊RSA的時(shí)間。該文將立足于算法，對大整數(shù)分解提出一些新的思路，并解釋幾類容易被破解的大整數(shù)的原因。

1 二進(jìn)制下的素?cái)?shù)0與1比例探索

1.1 基本原理

這個(gè)思路來源于《素?cái)?shù)分布——素?cái)?shù)硬幣的拋擲運(yùn)動(dòng)》這篇文章，分解一個(gè)大整數(shù)，需尋找其素因子（N=p×q）。這個(gè)過程是由一個(gè)已知數(shù)去尋找兩個(gè)未知數(shù)，構(gòu)成了較大的困難性。故從問題的反面考慮，通過運(yùn)算、比較一定數(shù)量的已知素因子，尋找其乘法規(guī)律。下設(shè)兩個(gè)素因子在十進(jìn)制下分別有位與位，有位，即有如下的乘法關(guān)系式：

1.2 的性質(zhì)

二進(jìn)制下研究素?cái)?shù)的分布的考察點(diǎn)是，先觀察的性質(zhì)。

1.2.1 有界性

，其中是一個(gè)關(guān)于的復(fù)雜函數(shù)，它與素分布有關(guān)。

1.2.2 存在性

每一個(gè)所對應(yīng)的都是一個(gè)確定的數(shù)。

1.3 算法實(shí)現(xiàn)

：設(shè)置邊界數(shù)T （T 不宜太大）。

：從0到T計(jì)算，計(jì)算到之間所有素?cái)?shù)在二進(jìn)制下1的個(gè)數(shù)，記為，及為其間0的個(gè)數(shù)，并用數(shù)組儲(chǔ)存對應(yīng)的比值，對應(yīng)輸出。

：繪制“”圖像，并用MATLAB擬合。

：從數(shù)列中尋找收斂子列，并嘗試找出其極限。

1.4 圖像結(jié)果（測試T=24以內(nèi)素?cái)?shù)比值）

1.4.1 數(shù)據(jù)表（用C++編程測試）

舍去第一項(xiàng)無效的結(jié)果后，用MATLAB繪制圖像，如圖1所示。

1.4.2 圖像

（1）未擬合圖像；

（2）三次樣條差值擬合圖像，如圖2所示。

1.5 小結(jié)

比值在目前測試結(jié)果中，比值趨于1.05這表明二進(jìn)制下素?cái)?shù)1與0的比值研究可能會(huì)是比較困難的，說明了素?cái)?shù)的分布有一定的隨機(jī)性，但卻提供了一種獨(dú)特視角觀察素?cái)?shù)特征。

2 平方數(shù)法分解因式

2.1 基本原理

此方法基于“費(fèi)馬分解大整數(shù)”的方法，通過逐步改進(jìn)平方數(shù)的尋找方法，使平方數(shù)的差值為待分解數(shù)，從而達(dá)到分解大整數(shù)的目的。

具體思路如下：令代分解的大整數(shù)為 ，假設(shè)其并非是完全平方數(shù)（在后續(xù)程序中第一步進(jìn)行開根號(hào)運(yùn)算，若得非整數(shù)結(jié)果才會(huì)繼續(xù)下面的程序，從而避免算法尋找失?。敲此梢苑纸鉃閮蓚€(gè)素因子p，q 即，取整數(shù)滿足下列關(guān)系式：

2.2 分解中S2與T2的存在性

若是完全平方數(shù)則可以通過第一步開根號(hào)運(yùn)算結(jié)果進(jìn)行判斷；若是非完全平方整數(shù)，且只有兩個(gè)素因子的情況下一定可以通過（2.1.1）來構(gòu)造S2與T2，而（2.1.2）式又可以通過高斯求和方式遍歷平方數(shù)，故上述算法是可實(shí)現(xiàn)的。

2.3 算法描述（算法）

：初始化求和存儲(chǔ)變量，

：對給定的做初始判斷，若為整數(shù)，則算法結(jié)束；若非，則進(jìn)行。

：，若，則繼續(xù)執(zhí)行，否則執(zhí)行。

：，若，則繼續(xù)執(zhí)行，否則執(zhí)行。

：，若，則輸出算法結(jié)束；若則原有執(zhí)行；若，，執(zhí)行。

3 結(jié)語

以上介紹了一種探索素?cái)?shù)分布的思路和兩種大整數(shù)分解在計(jì)算機(jī)下實(shí)現(xiàn)的算法。首先，探究的素?cái)?shù)規(guī)律，通過計(jì)算素?cái)?shù)在二進(jìn)制下0-1個(gè)數(shù)比例，模擬圖像，觀察素?cái)?shù)特征。其次，建立在費(fèi)馬算法上的平方整數(shù)分解方法，旨在用奇數(shù)和表示平方數(shù)，以遍歷算法逼近用以表示所拆分大整數(shù)的平方數(shù)。最后，將大整數(shù)分解轉(zhuǎn)移至已有較完備算法的多項(xiàng)式分解問題上。通過找尋多項(xiàng)式分解的因式，來突破整數(shù)分解的問題。而現(xiàn)在一定范圍內(nèi)的多項(xiàng)式分解是可以在計(jì)算機(jī)上實(shí)現(xiàn)分解的，從而說明了其有效性。

參考文獻(xiàn)

[1] 曾泳泓.大整數(shù)因子分解算法綜述[J].國防科技大學(xué)，1991（4）：21-32.

[2] 許小勇，鐘太勇.三次樣條插值函數(shù)的構(gòu)造與Matlab實(shí)現(xiàn)[J].兵工自動(dòng)化，2006，25（11）：76-78.

[3] 百度百科.拉斯維加斯算法.http：//baike.baidu.com/link.url=NwHY9 w5CTv9kGLBTld8Ln-wHLM6Yle5 usyS59Q3trDUC7DswnOf9EOLue 46NQXrS6P4UZshup0ZHQIRGfN-r_2014.12.5.