楊晨鶴　王周寧馨　張禎

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

關鍵詞：大整數分解 平方整數分解 多項式分解 RSA

中圖分類號：TP338.8 文獻標識碼：A 文章編號：1672-3791（2015）03（a）-0243-02

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

1 二進制下的素數0與1比例探索

1.1 基本原理

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

1.2 的性質

二進制下研究素數的分布的考察點是，先觀察的性質。

1.2.1 有界性

，其中是一個關于的復雜函數，它與素分布有關。

1.2.2 存在性

每一個所對應的都是一個確定的數。

1.3 算法實現

：設置邊界數T （T 不宜太大）。

：從0到T計算，計算到之間所有素數在二進制下1的個數，記為，及為其間0的個數，并用數組儲存對應的比值，對應輸出。

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

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

1.4 圖像結果（測試T=24以內素數比值）

1.4.1 數據表（用C++編程測試）

舍去第一項無效的結果后，用MATLAB繪制圖像，如圖1所示。

1.4.2 圖像

（1）未擬合圖像；

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

1.5 小結

比值在目前測試結果中，比值趨于1.05這表明二進制下素數1與0的比值研究可能會是比較困難的，說明了素數的分布有一定的隨機性，但卻提供了一種獨特視角觀察素數特征。

2 平方數法分解因式

2.1 基本原理

此方法基于“費馬分解大整數”的方法，通過逐步改進平方數的尋找方法，使平方數的差值為待分解數，從而達到分解大整數的目的。

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

2.2 分解中S2與T2的存在性

若是完全平方數則可以通過第一步開根號運算結果進行判斷；若是非完全平方整數，且只有兩個素因子的情況下一定可以通過（2.1.1）來構造S2與T2，而（2.1.2）式又可以通過高斯求和方式遍歷平方數，故上述算法是可實現的。

2.3 算法描述（算法）

：初始化求和存儲變量，

：對給定的做初始判斷，若為整數，則算法結束；若非，則進行。

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

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

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

3 結語

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

參考文獻

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

[2] 許小勇，鐘太勇.三次樣條插值函數的構造與Matlab實現[J].兵工自動化，2006，25（11）：76-78.

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