公鑰密碼體制中大整數(shù)分解算法研究

王興波 唐春明 李建輝

摘? 要：通過對文獻資料的歸類分析，結(jié)合大整數(shù)分解理論和實踐的具體發(fā)展，從宏觀層面將大整數(shù)分解的歷程劃分為四個階段并歸納出了每個階段的基本特征，同時結(jié)合國內(nèi)研究情況總結(jié)出了國內(nèi)研究的特點，指出了國內(nèi)外研究的差別以及國內(nèi)研究的某些局限性。文章最后還介紹了最近幾年新發(fā)現(xiàn)的基于二叉樹研究方法的特色及其取得的成果，展示了一些算例并揭示了未來的相關(guān)研究方向和內(nèi)容。文章可作為研究大整數(shù)分解算法的參考。

關(guān)鍵詞：計算數(shù)論;密碼學;整數(shù)分解;算法

中圖分類號：TN918? ? ? 文獻標識碼：A 文章編號：2096-4706（2020）16-0125-09

Study on Algorithms of Big Integer Factorization in Public-key Cryptosystem

WANG Xingbo1，TANG Chunming2，LI Jianhui3

（1.Foshan University，F(xiàn)oshan? 528225，China;2.Guangzhou University，Guangzhou? 510006，China;

3.Foshan Polytechnic，F(xiàn)oshan? 528137，China）

Abstract：Based on the classification and analysis of literature，combined with the specific development of the theory and practice of large integer decomposition，the process of large integer decomposition is divided into four stages from the macro level，and the basic characteristics of each stage are summarized. At the same time，the characteristics of domestic research are summarized based on the domestic research situation，and the differences between domestic and foreign research and some limitations of domestic research are pointed out. At the end of the paper，the characteristics and achievements of the new research method based on binary tree in recent years are introduced，and some examples are presented，and the related research directions and contents in the future are revealed. This paper can be used as a reference for studying large integer factorization algorithm.

Keywords：computational number theory;cryptography;integer factorization;algorithm

0? 引? 言

大整數(shù)分解問題是數(shù)論的困難問題之一，也是人類尚未完全解決的科學問題之一，一直受到世界各國眾多數(shù)學和信息安全工作者的關(guān)注。近百年來，人類對于破解這個難題的努力一直未有間斷，其間有興奮、失落，亦有努力和希望并行，構(gòu)成了解決這個難題的艱難歷程。

近50年來，學者們主要在大整數(shù)分解基礎(chǔ)理論方法與分解實踐兩方面開展研究。分解理論主要在尋找高效的分解算法方面，而分解實踐則主要集中在RSA實驗室1991年公布的系列RSA模數(shù)及數(shù)論里懸疑的一些特殊數(shù)如梅森數(shù)、費馬數(shù)等。

1975年到1995年近20年的時間，大整數(shù)分解理論從技術(shù)層面產(chǎn)生了一些優(yōu)秀的算法，如Pollard Rho算法、連分數(shù)法（Continued fraction，CFRAC）、二次篩法（Quadratic Sieve，QS）、平方型分解法（SQUare FOrm Factorization，SQUFOF）、橢圓曲線法（ECM）和數(shù)域篩法（Number Field Sieve，NFS）等。1996年12月美國數(shù)學協(xié)會通訊（NOTICES OF THE AMS）發(fā)表了一篇題為《兩個篩法的故事》（“A Tale of Two Sieves”）的長文。作者Carl Pomerance是二次篩法的創(chuàng)始人，通過該文介紹了當時理論與實踐的各種成就，成功與期盼之情躍然紙上。然而自該文后25年過去了，大整數(shù)分解的問題依然沒有解決。

筆者早在上大學之時就對這個問題充滿憧憬，還給數(shù)學大師陳景潤寫信，信誓旦旦地要解決這個問題。后來參加研究生復試時，導師說：“這個問題留待你退休后研究吧！”時至今日，退休之日近在咫尺，回想幾十年對這個問題的了解和研究，模仿Carl Pomerance講故事的方式，向讀者回顧近30年來人類辛苦探索該問題的歷程，同時也介紹筆者及其團隊對這個問題的研究結(jié)果。

1? 國內(nèi)外研究概況

高效分解整數(shù)的算法無疑是解決大整數(shù)分解難題的關(guān)鍵。近50年來，國內(nèi)外都有學者在不停地耕耘，其間也取得了令人欣慰的成就，從技術(shù)層面產(chǎn)生了很多優(yōu)秀的算法。很多文獻已經(jīng)對這些算法的技術(shù)特點、理論價值做了介紹，故本文在這里不再贅述。本文主要關(guān)注大整數(shù)分解的發(fā)展歷程和每個時期的特點，從宏觀層面總結(jié)這個辛酸與期望并存的求索過程。

1.1? 國外研究

根據(jù)國內(nèi)外的文獻綜述情況，國外對于整數(shù)分解的研究成果可分為四個階段：

（1）無“計”可施階段：持續(xù)數(shù)百年的試除法和Fermat方法;

（2）“眾說紛紜”階段：1975年前后到1995年前后20年左右;

（3）“計窮力竭”階段：1995年到2010年前后15年左右;

（4）“再入迷茫”階段：2010年至今。

以下分別簡述各階段的主要成果及特點。

1.1.1? 1975年以前“無計可施”的數(shù)百年

歷史上人類對于整數(shù)分解的問題除了試除（試除法）以外，可謂無“計”可施，直到17世紀業(yè)余數(shù)學家Pierre de Fermat提出了Fermat法以后才算有一個基本解決方法。試除法和Fermat法在所有因數(shù)分解的教科書里都有介紹。它們直觀易懂，分解大整數(shù)的效率很低，適合分解小整數(shù)，是1970年以前分解整數(shù)的主要方法。對于分解大整數(shù)而言，這兩個方法都“無計可施”。文獻[1]將此稱為“束手無策”（參見文獻[1]第19頁）。

1.1.2? 1975年—1995年“眾說紛紜”的20年

國內(nèi)外文獻記錄和相關(guān)綜述表明[1-6]，20世紀70年代中至90年代中是人類研究整數(shù)分解的高峰時期，也是相關(guān)成果出現(xiàn)的密集期，堪稱整數(shù)分解算法研究的“眾說紛紜”時代。綜合各種綜述文獻，可發(fā)現(xiàn)這個階段產(chǎn)生了各有所長的10多種分解算法。表1列舉了一些有影響的算法。

1.1.3? 1995年—2010年“計窮力竭”的15年

1974年后密集出現(xiàn)的各種算法，讓數(shù)學家對解決分解整數(shù)的難題充滿了希望。各種先進計算機的研制成功，甚至讓一些人認為分解大整數(shù)已經(jīng)不是什么問題了。但是RSA實驗室向世人展示了一個嚴酷的事實——大整數(shù)分解依然困難。1991年3月，RSA實驗室公布了一組RSA模數(shù)并為每個模數(shù)設置了獎金——分解了所公布任何模數(shù)都能獲得對應的獎金。由此開辟了應用與檢驗當時各種分解算法的階段，并且分解RSA模數(shù)成為計算數(shù)論與密碼學界檢驗分解算法成效的標志性指標。

隨著高性能計算機的問世，并行計算自然成為研究和采用的基本手段。各種算法的并行化是該階段的研究特征。1990年，Brent R P就研究了整數(shù)分解并行計算的可能性。在文獻[7]中，Brent指出Pollard Rho算法在并行計算時效率并沒有明顯提高，認為該算法的并行計算意義不大;他同時指出ECM和QS的并行計算效果較好。1999年，Brent總結(jié)了當時的并行計算成果并發(fā)表了文獻[8]。2000年Wolski E的團隊給出了ECM的并行計算法[9];同年，Brynielsson J發(fā)表了二次篩法的并行計算方法[10]。2005年—2007年，Mcmath S S及其團隊先后發(fā)表了二次型法與連分數(shù)法的并行計算特征[11，12]。隨后幾年，如文獻[13][14]所述，NFS并行化得到廣泛關(guān)注并取得了不菲成就。到目前為止，NFS被認為是效率最高的分解算法。從表2所列已分解的RSA模數(shù)及其分解方法可知，幾乎每個被分解的模數(shù)都能用NFS分解。

NFS在分解RSA模數(shù)方面的成功運用似乎抑制了人們繼續(xù)挖掘更好算法的欲望。相比1975年—1995年的20年期間產(chǎn)生了近10種算法，在1995年—2010年的15年期間，沒有比NFS更有影響力的算法出現(xiàn)。目前，并行NFS在分解大的RSA模數(shù)方面幾乎是不二的選項。正因為如此，筆者稱這個時期是“計窮力竭”階段。

1.1.4? 2010年以來“再入迷?！钡哪甏?/p>

從前面2小節(jié)的歷史陳述可以看出，到目前為止所有常規(guī)算法（串行或并行）在分解具有小因數(shù)的整數(shù)方面都很成功，但是在分解大整數(shù)方面仍然不盡人意。人們不得不面臨一個殘酷的現(xiàn)實問題：效率最高的NFS需要通過并行計算系統(tǒng)或超級計算機耗費巨量計算資源來實現(xiàn)[15]。例如，著名的RSA-768就是基于80個2.2 GHz AMD皓龍（Opteron）四核心CPU的并行計算歷經(jīng)半年得到分解的[16]。Bruce Schneier于2019年12月分解RSA-240時用了800個物理核做篩子外加100個物理核做矩陣。文獻[17]統(tǒng)計，NFS分解768位（二進制）目標時，因子基需要240 MB內(nèi)存、篩子需要10 GB、矩陣計算需要160 GB，分解1 024位目標則分別需要7.5 GB、256 GB和10 TB的內(nèi)存。目前只有擁有大計算資源的國家和地區(qū)，才有條件開展相應的研究[18]。正因為如此，有網(wǎng)友戲謔預測：在天河二號上跑半年也許能夠分解RSA-232。事實上，Bruce Schneier在分解RSA-240時，采用Intel Xeon Gold 6130 CPU共花了4 000核年的計算量，折算在天河二號上，大概需要1 000個天河節(jié)點及24 000個天河計算核，持續(xù)運行300天（費用開銷估算在1 728萬元人民幣左右）。

鑒于這樣的現(xiàn)實，印度學者近年來開展了較為活躍的研究，如文獻[19]到文獻[23]，得到了? 甚至? 級別確定性時間復雜度的算法，但這些算法對于大整數(shù)而言仍然意味著冗長的計算。也有印度學者進行Fermat方法優(yōu)化、甚至有人將離散優(yōu)化的粒子算法引入到整數(shù)分解計算（相關(guān)文獻在researchgate可查，部分處在preprint狀態(tài)故未列入文獻清單），但總體來說印度學者仍未展示系統(tǒng)性解決方案的成果。有學者試圖在GPU上實施RSA模數(shù)分解[24];但據(jù)筆者與該文作者本人的交流，他的研究沒有取得實質(zhì)性的進展，僅僅是一個設想、發(fā)表了一篇論文而已。有部分其它學者在2003年—2008年間也做過有條件的確定性時間復雜度分解RSA數(shù)的算法研究，如文獻[25]、[26]，但正如文獻[6]所陳述的，這些算法的效率低于隨機化算法的效率，且這些研究均未見實證結(jié)果。

截至目前為止，RSA公布的待分解模數(shù)中，尚有RSA-232、RSA-250、RSA-260、RSA-896、RSA-1024、RSA-1536、RSA-2048等多個未被分解。筆者認為，除非有新的革命性算法，否則大整數(shù)分解依然是繼續(xù)挑戰(zhàn)人類智力極限的一個數(shù)學難題。

1.2? 國內(nèi)研究

國內(nèi)對于整數(shù)分解的研究由來已久，例如《九章算術(shù)》就記錄了很多整數(shù)分解的例子，這些例子展示的方法比國外要早很多年。但是遺憾的是，在現(xiàn)代研究方面，國內(nèi)主要以借鑒國外方法為主，鮮有超越國外的獨立研究報道。

筆者分別以“整數(shù)分解”“大數(shù)分解”“RSA分解”“整數(shù)+因子+分解”“整數(shù)+因數(shù)+分解”及“RSA攻擊”為關(guān)鍵詞，在CNKI檢索1991年1月至2020年1月的文獻情況如表3所示。

經(jīng)篩選，真正與分解算法研究相關(guān)的文獻按照時間先后順序排列見文獻[1]、[3]、[5]及文獻[27]到文獻[54]，涉及的研究內(nèi)容如表4所示。

基于表3、表4的數(shù)據(jù)，筆者總結(jié)出“綜述學習”“局部探索”和“頂天不立地”三個特征來描述。

1.2.1? 綜述學習

該類主要集中在碩、博士研究生群體的研究，也有知名學者的啟蒙教育，成果多以學位論文或教材等讀物表現(xiàn)，特點是綜述國外的方法，從中獲取一定的知識，比如文獻[1]、[3]、[5]、[32]、[40]、[46]及[48]都屬于這樣的研究。

文獻[1]屬于教材式文獻，原本是寫給中學生的讀物，但文中綜述了相關(guān)方法的進展，是非常不錯的啟蒙讀物。

文獻[3]、[5]屬于綜述型文獻，回顧了當時主流的大數(shù)因子分解算法，介紹了這些算法的基本原理和實現(xiàn)步驟，對比分析了現(xiàn)有大數(shù)因子分解技術(shù)在實現(xiàn)和應用上的優(yōu)缺點并展望了大整數(shù)分解未來的研究趨勢。

文獻[32]綜述了各種大整數(shù)因子分解算法，討論了QS和NFS的優(yōu)化問題。

文獻[40]通過對已有的因子分解算法的分析、總結(jié)、比較，提出了一個新的因子分解算法和一個因子分解方法的新研究方向。但是根據(jù)筆者對所提方法的剖析，發(fā)現(xiàn)該方法采用了類似試除法的搜索過程，其效率并不高。

文獻[46]考察了中國古代數(shù)學中所蘊含的整除理論、探究了西方數(shù)學中的數(shù)論起源、考察了素數(shù)基本理論、探討了整數(shù)分解的幾種經(jīng)典算法、論述了密碼學發(fā)展的三個階段：古典密碼、近代密碼和現(xiàn)代密碼。筆者認為，該文仍處在啟蒙階段。

文獻[48]屬于一般轉(zhuǎn)抄、拼湊型綜述。

1.2.2? 局部探索

該類研究基于相關(guān)的數(shù)學理論與計算機算法，針對RSA算法的特征，進行了局部問題的建設性研究或者探索性研究，如文獻[29]、[31]、[34]、[35]、[36]、[37]、[42]、[43]、[44]、[45]、[49]及[54]均屬于此類。

文獻[29]在分解大整數(shù)小因子算法的基礎(chǔ)上，提出的優(yōu)化分解樹算法，利用樹型數(shù)據(jù)結(jié)構(gòu)和相應的構(gòu)造算法與回溯算法，配合以作者提出的分解表截支方法和優(yōu)化分組策略，可以將分解大整數(shù)小因子的速度提高50%以上，但該文無數(shù)據(jù)對比，且構(gòu)造樹本身需要時間。筆者認為此法還有待挖掘。

文獻[31]對一大類大整數(shù)的因子分解構(gòu)造了分解算法，通過求解模數(shù)的小因數(shù)來實現(xiàn)分解，其本質(zhì)是特殊Pollard p-1方法。

文獻[34]闡述了大數(shù)分解法二次篩選法優(yōu)化，提出了參數(shù)、硬件等多個優(yōu)化方案，但缺少實施的措施，屬于一般性描述。

文獻[35]介紹了詳細闡述了大數(shù)分解法QS以及它的改進算法MPQS和PPMPQS的理論基礎(chǔ)。文中宣稱設計了一種快速尋找PP關(guān)系的方法并利用VC6實現(xiàn)了PPMPQS，成功分解了十進制70位的大數(shù)，但文中未見分解實例。事實上，單純利用VC6而不借用大數(shù)運算工具包，如gmp大數(shù)庫、NTL大數(shù)庫或者MIRAC大數(shù)庫，是很難表示70位十進制大數(shù)的。

文獻[36]證明了：若丟番圖方程ax+by=z（（a，b）=1）的整數(shù)解（x0，y0，z0）滿足x0=O（log2ab），y0=O（log2ab）且

z0=O（log2ab）;那么存在一個多項式時間的算法分解n=ab并時間不超過 。該文是筆者所看過國內(nèi)文獻中較有參考價值的一個。但考慮到從丟番圖方程的解集中尋找符合分解因子的過程也需要時間，其算法效率未免要打折扣。事實上，利用筆者的方法僅搜索了4步就分解了該文所述案例，計算時間僅數(shù)毫秒。

文獻[37]對試除法進行了改進，減少試除次數(shù)提高了試除法運算效率，在算法上并無新的創(chuàng)意。

文獻[42]提出了一種整數(shù)分解的判定算法，本質(zhì)是將計算中間過程中的素數(shù)判定去除，仍然屬于改進Fermat算法的類別，其計算效率為O（plogN），低于Pollard Rho的效率。

文獻[43]提出了一種用于求解大整數(shù)因數(shù)分解問題的尾數(shù)多相位粒子群搜索算法MMPPSO。但數(shù)值實驗表明該文大多數(shù)算例的結(jié)果是錯誤的，少數(shù)正確的結(jié)果中還有與文獻[36]中的算例雷同的。

文獻[44]根據(jù)RSA數(shù)的特性及Euclid算法的特點，給出了一種析出分解算法，并進行了算法的數(shù)學證明和相關(guān)分析。筆者發(fā)現(xiàn)，該算法的效率與Fermat法相當，也存在需要完善的地方。

文獻[45]是一篇博士論文，從理論上探討了構(gòu)造一類橢圓曲線，就該類橢圓曲線的非扭有理點x-坐標與曲線方程系數(shù)D的分解進行研究，并嘗試將有理數(shù)域上橢圓曲線分解整數(shù)的方法推廣到虛二次域K上，涉及較深奧的橢圓曲線知識。鑒于筆者對此方面不甚了解，不敢貿(mào)然評價，但顯而易見的是該文最后沒有給出具體解決方案。

文獻[49]將分解整數(shù)因子的費馬法迭代過程分為兩個階段，采用合適的算法加快平方和開方運算，避免無效運算，使總體計算量大大減少。該文沒有與其他方法進行比較，難以確定其提高效率的有效性。

文獻[54]通過變換隨機序列產(chǎn)生式，對Pollard Rho算法在計算離散對數(shù)方面進行了改進，提高Pollard Rho算法的效率。考慮到離散對數(shù)計算與整數(shù)分解之間的本質(zhì)關(guān)系[55]，鑒于Pollard Rho算法對于大整數(shù)分解的局限性，筆者認為對于大整數(shù)分解，還需配合它法。

1.2.3? 頂天不立地

該類研究的特點是接觸非常規(guī)計算技術(shù)的時代前沿，提出一個時期時尚的概念和一段時間難以驗證的方法，如文獻[28]、[33]、[38]、[39]、[30]、[41]、[50]、[51]、[52]及[47]屬于此類。

文獻[28]、[33]、[38]給出整數(shù)分解的并行或分布式計算實現(xiàn)原理，但未見具體計算方案，此后至今未見后續(xù)的相關(guān)報道。其實分布式計算取決于對解空間的劃分，如比特幣的挖礦算法，網(wǎng)格計算等。小規(guī)模（幾臺或幾十臺計算機）有可能，大規(guī)模異構(gòu)分布式并行計算本身就是一個復雜的研究課題。

文獻[39]提出了Pollard p-1因子分解的DNA計算機算法，以Pollard p-1算法為基礎(chǔ)，利用DNA分子生物操作完成加，減，乘，除運算，實現(xiàn)平方-乘以及歐幾里德算法，其本質(zhì)是對歐幾里德運算中的算術(shù)運算進行變換，在分解方法上面，沒有實質(zhì)性的發(fā)展。該文也沒有具體有說服力的算例。

文獻[30]、[41]、[50]、[51]、[52]給出新的量子算法。但到目前為止，國內(nèi)尚無法驗證，國際上也缺乏所需驗證條件。人們可以從科學的角度去研究未來的科學產(chǎn)出，但是大整數(shù)分解是與信息安全密切相關(guān)、科學與工程一體的科學技術(shù)共生體，既需要頂天的科學理論又需要立地的務實技術(shù)才能解決問題。

文獻[52]試圖實施Pollard p-1因子分解的DNA計算機算法，未見具體計算方案，也未見后續(xù)成果報道。

文獻[47]提出云計算的設想，沒有對大整數(shù)運算的環(huán)境作分析，也未見后續(xù)報道。其實基于云計算分解整數(shù)僅僅是網(wǎng)格計算的延伸，跟分布式并行計算一樣，需要很細致的策劃和方案乃至每個結(jié)點實現(xiàn)的算法，包括云上計算環(huán)境的配置等，需要細致的方案和措施。

1.3? 國內(nèi)外研究對比及目前辛酸的局面

通過前面幾小節(jié)對國內(nèi)外算法研究及實踐現(xiàn)狀的總結(jié)，不難得到如下結(jié)論：

（1）國外學者側(cè)重于提出系統(tǒng)的解決方案，尤其上世紀70年代中至90年代中產(chǎn)生了系列的解決方案，在整數(shù)分解方面取得了實質(zhì)性的成就;

（2）國內(nèi)主要以吸收國外研究為特征，到目前為止整數(shù)分解理論和方法都基本沒有產(chǎn)生超越國外水平的成果報道;

（3）在經(jīng)典計算機體系結(jié)構(gòu)下，NFS是目前應用最廣的方法。在量子計算機結(jié)構(gòu)下，量子算法是人們的希望所在。盡管如此，1995年以來，國內(nèi)外在分解大整數(shù)這一數(shù)學難題的方法學上，沒有超越NFS和量子算法的成果報道。由于量子算法受制于量子計算機的發(fā)展，NFS是目前在分解實踐中的主要方法;

（4）大整數(shù)分解至今仍然是挑戰(zhàn)人類智能水平的一個世界難題，等待人類的解決。

2? 二叉樹上的數(shù)論展現(xiàn)了新的希望

賦值二叉樹是王興波教授研究奇數(shù)時采用的一種方法[56]。該方法將大于1的奇數(shù)（注：后文所述奇數(shù)均指大于1的奇數(shù)）從上到下從左到右置于一棵二叉樹上來研究，揭示了奇數(shù)許多鮮為人知的性質(zhì)。例如子樹根的因數(shù)與后代之間存在近親回避律（若干層內(nèi)一定沒有根的倍數(shù)出現(xiàn)），子樹之間存在復制傳遞性以及子樹的根與后代結(jié)點的公因數(shù)存在對稱律等等[57-60]。最為重要的是，它揭示了奇數(shù)的遺傳特質(zhì)——在以奇數(shù)N為根的子樹中，N都以一種僅與其自身相關(guān)的遞歸方式分布在其子孫結(jié)點的因數(shù)中，并且可以通過基因結(jié)構(gòu)、基因圖與余基因圖等由奇數(shù)N的倍數(shù)組成的數(shù)據(jù)結(jié)構(gòu)來描述[61]。基因圖與余基因圖形成一幅遺傳圖譜，可演繹出整數(shù)分解的新方法。

2.1? 奇數(shù)的遺傳圖譜

奇數(shù)的遺傳特質(zhì)可用圖1直觀地說明。取以3為根的子樹T3為例：T3第三層首末兩個結(jié)點9、15具有因數(shù)3，以9、15為根的子樹在其第三層的首末兩個結(jié)點也含有因數(shù)3，此規(guī)律一直在T3中延續(xù)。以5為根的子樹T5在其第四層第2個和倒數(shù)第2個結(jié)點具有因數(shù)5，這種規(guī)律在T5中延續(xù)。更有意思的是，以15為根的子樹T15，分別繼承了T3和T5的前述屬性，在其第三層首末結(jié)點包含因數(shù)3、在第四層第2個和倒數(shù)第2個結(jié)點具有因數(shù)5，且這種規(guī)律在T15中延續(xù)。

記TN表示以大于1的奇數(shù)N為根的賦值二叉樹。文獻[56][61]證明了，TN中存在一個N的遺傳結(jié)構(gòu)g（N）（genetic structure），也存在一個由N的倍數(shù)組成的基因圖G（N）（genetic graph）和余基因圖G*（N）（complementary genetic graph）。若p是N的一個因數(shù)，G（p）與G*（p）是p的基因圖與余基因圖。G（N）與G*（N）合起來稱為N的遺傳圖譜或基因圖譜（genetic atlas），它也是TN的一棵子樹。

2.2? 遺傳圖譜與整數(shù)分解

奇數(shù)的遺傳圖譜對于整數(shù)分解具有重要意義，它能提供整數(shù)分解的一種新途徑。文獻[61]證明了：當N是含有因數(shù)p的奇合數(shù)時，TN上同層兩個G（N）結(jié)點之間一定存在G（p）或G*（p）的結(jié)點。這就意味著，一旦得到了G（N），就能在其上找到G（p）或G*（p）的結(jié)點。由于G（p）和G*（p）的結(jié)點都是p的倍數(shù)，因此p是這些結(jié)點與N之間的公約數(shù)。從而N的分解可以轉(zhuǎn)化為尋找在G（N）或G*（N）上尋找G（p）或G*（p）的結(jié)點。

設N=pq，1

2.3? 取得的成果

基于前述二叉樹上奇數(shù)的遺傳特征，近幾年的研究取得了以下研究成果。

2018年，分別找到了殆素數(shù)因數(shù)比對其小因數(shù)分布的影響關(guān)系[62]。李建輝教授據(jù)此設計了并行分解算法并成功分解了46位十進制殆素數(shù)[63]。試驗表明，在串行模式下分解22位以內(nèi)的十進制合數(shù)時明顯優(yōu)于Pollard Rho方法。與目前廣泛應用的數(shù)域篩法（NFS）或GNFS相比，新的算法占用極少內(nèi)存。2018年還研究了T3樹上結(jié)點與其平方根的關(guān)系[64]以及RSA模數(shù)的因數(shù)分布特征[65]。

2019年1月，證明了奇數(shù)的因子具有呈周期性分布在樹的邊界和圍欄上的規(guī)律，并藉此用新的方法再次演繹證明了p+1分解法[66]。如圖3所示，樹TN的邊界是樹上最左結(jié)點或最右結(jié)點組成的，而樹的圍欄則是由如 、 所示緊靠邊界的奇數(shù)組成的。

2019年年初還找到RSA模數(shù)的平方根與因數(shù)之間的分布規(guī)律[67]以及RSA模數(shù)在T3樹上的分布規(guī)律[68]。證明了：RSA模數(shù)N的兩個因數(shù)中或者處在T3樹的同一層、或者處在相鄰兩層，其中一定有一個與? 裹挾在同一層。

2019年4月證明了整數(shù)乘積的長度與因數(shù)長度的關(guān)系，特別證明了：因數(shù)比小于2的RSA模數(shù)之兩個因數(shù)都是等長的[69]。

2019年5月，藉由前述研究結(jié)果，證明了：若整數(shù)N= pq的兩個因子滿足1

2020年1月，證明了：若整數(shù)N=pq的兩個因子滿足q=2αu±1，1

2020年5月，證明了：若整數(shù)N=pq的兩個因子滿足1

結(jié)合德國Wilfrid Keller教授對u的估值范圍[72]，如有合適的大費馬數(shù)計算工具，每個大費馬數(shù)Fm（m>100 001）能在普通計算機上瞬間分解。讀者可向王興波教授索取Maple源程序進行測試。

2.4? 未來研究

遺傳特征主要是根結(jié)點在其子孫結(jié)點之間的因數(shù)傳遞規(guī)律。兩棵不同的子樹之間也存在傳遞規(guī)律，稱之為過渡（transition）。研究發(fā)現(xiàn)，這個過渡可通過在兩棵子樹之間建立聯(lián)絡（connection）來完成。例如圖4中的65可以通過25計算出來。但是25不是T5的結(jié)點而屬于另外一棵樹的結(jié)點（注意：這不是通過觀察得知而是根據(jù)文獻[61]推論8的結(jié)論演繹的）。

樹的域外的結(jié)點屬于另外一棵子樹，因此聯(lián)絡也是樹際間結(jié)點的關(guān)系的描述，其解析計算關(guān)系無疑是樹際間因數(shù)倍數(shù)傳遞的最直接表現(xiàn)，也是整個整數(shù)遺傳圖譜結(jié)構(gòu)中不可忽視的關(guān)系。例如N=pq可視N是Tp樹與Tq樹的聯(lián)絡轉(zhuǎn)換點。最近研究發(fā)現(xiàn)，在Tp樹與Tq樹里分別存在一個X與Y，在TN樹里面有一個m滿足m=qX=pY，如圖5所示。顯然，通過m找到X或Y的任何一個，就能找到p或者q了，其計算的時間復雜度都是對數(shù)級的。樹際間的聯(lián)絡關(guān)系，不僅是子樹之間的連接紐帶，而且可能提供分解整數(shù)的一般法則。目前，筆者及團隊正在努力研究出新的結(jié)果。

在樹上一層尋找某個目標結(jié)點是一個與搜索有關(guān)的問題。事實上，整數(shù)分解算法大都表現(xiàn)為在某些集合里面尋找一些特定目標。比如，Pollard Rho算法本質(zhì)上是一種隨機化搜索算法。每個算法針對的潛在目標集合不同，導致搜索效率各異。前期研究所發(fā)現(xiàn)可將殆素數(shù)的因數(shù)定位于某個區(qū)間內(nèi)的結(jié)果，最后也只有設計出有效的搜索算法才能實現(xiàn)分解。通過判斷某特征數(shù)是否在某區(qū)間[73]、將目標區(qū)間進行有效分劃以便實現(xiàn)隨機化算法設計和并行計算[74]、采用區(qū)間樹方式減少搜索量[75，76]等研究，發(fā)現(xiàn)樹上樹上搜索與各種進化算法（智能算法）關(guān)系密切，或許是一粒開門的“芝麻”。目前，筆者和團隊也在進行相關(guān)的探索。

3? 結(jié)? 論

大整數(shù)的分解是一個歷史難題，也是一個現(xiàn)實的難題。人類對這個難題的研究和探索是一個充滿辛酸與希望的，面向晨曦在泥濘中跋涉的歷程。相對于國外學者提出的種種系統(tǒng)性解決方案，國內(nèi)研究尚需要在系統(tǒng)性和原創(chuàng)性方面努力。筆者和團隊近年來基于二叉樹開展的整數(shù)研究新方法，有望成為一個原創(chuàng)性可系統(tǒng)解決整數(shù)分解問題的研究方法。筆者希望廣大讀者通過本文的介紹，能夠了解、理解和認同探索者們的努力與付出，加入到這個艱難的研究活動中，一起變夢想為現(xiàn)實。

參考文獻：

[1] 顏松遠.整數(shù)分解 [M].北京：科學出版社，2009.

[2] SURHONE L M，TENNOE M T，HENSSONOW S F. RSA [M].Beau Bassin：Betascript Publishing，2013.

[3] 董青，吳楠.整數(shù)質(zhì)因子分解算法新進展與傳統(tǒng)密碼學面臨的挑戰(zhàn) [J].計算機科學，2008（8）：17-20.

[4] SARNAIK S，GADEKAR D，GAIKWAD U. An Overview to Integer Factorization and RSA in Cryptography [J].International Journal For Advance Research In Engineering And Technology，2014，2（9）：21-27.

[5] 劉新星，鄒瀟湘，譚建龍.大數(shù)因子分解算法綜述 [J].計算機應用研究，2014，31（11）：3201-3207.

[6] WANAMBISI A W，AYWA S，MAENDE C，et al. Factorization of Large Composite Integer [J].International Journal of Mathematics and Statistics Studies，2013，1（1）：39-44.

[7] BRENT R P. Vector and parallel algorithms for integer factorization [C]//Proc Third Australian Supercomputer Conference.1990.

[8] BRENT R P. Some Parallel Algorithms for Integer Factorisation [C]//Euro-Par99 Parallel Processing. Heidelberg：Springer，1990： 1-22.

[9] WOLSKI E，F(xiàn)ILHO J G S，DANTAS M A R. Parallel Implementation of Elliptic Curve Method for Integer Factorization Using Message-Passing Interface （MPI） [EB/OL].（2017-02-18）http：//www.lbd.dcc.ufmg.br/colecoes/sbac-pad/2001/007.pdf

[10] ?SBRINK O，BRYNIELSSON J. Factoring large integers using parallel Quadratic Sieve [EB/OL].（2000-04-14）.http：//citeseerx.ist.psu.edu/viewdoc/summary？doi=10.1.1.96.3685.

[11] MCMATH S S. Parallel Integer Factorization Using Quadratic Forms：U.S.N.A-trident Scholar Project Report：No.339 [R/OL].（2005-05-09）.http：//cadigweb.ew.usna.edu/～wdj/mcmath/.

[12] MCMATH S S，CRABBE F，JOYNER D. Continued fractions and Parallel SQUFOF [J].International Journal of Pure and Applied Mathematics，2007，34（1）：19-38.

[13] YANG L T，XU L，LIN M. Integer Factorization by a Parallel GNFS Algorithm for Public Key Cryptosystems [C]//Embedded Software and Systems，ICESS 2005.Heidelberg：Springer，2005：683-695.

[14] DAOUD S，GAD I. A parallel line sieve for the GNFS Algorithm [J].International Journal of Advanced Computer Science and Applications，2014，5（7）：178-185.

[15] YEH Y S，HUANG T Y，LIN H Y，et al. A Study on Parallel RSA Factorization [J].Journal of Computers，2009，4（2）：112-118.

[16] AOKI K. Advances in Integer Factoring Technique——The Way to Factor RSA-768 [J].IPSJ Magazine，2010，51（8）：1030-1038.

[17] SONALKER A A. Asymmetric Key Distribution [D].Raleigh：North Carolina State University，2002.

[18] WANG Q，F(xiàn)AN X B，ZANG H Y，et al. The Space Complexity Analysis in the General Number Field Sieve Integer Factorization [J].Theoretical Computer Science，2016，630：76-94.

[19] COSTA E，HARVEY D. Faster deterministic integer factorization [J].Mathematics of Computation，2014，83（285）：339-345.

[20] CARELLA N A. Deterministic Integer Factorization Algorithms [J/OL].arXiv：1308.2891 [cs.DS].（2013-08-05）.https：//arxiv.org/abs/1308.2891.

[21] SHIPILEVSKY Y. Polynomial Time Integer Factorization [J/OL].viXra：1407.0063.（2014-07-08）.https：//vixra.org/abs/1407.0063.

[22] HIARY G A. A deterministic algorithm for integer factorization [J].Mathematics of Computation，2015，85（300）：2065-2069.

[23] HITTMEIR M. A babystep-giantstep method for faster deterministic integer factorization [J]. Mathematics of Computation，2018，87（314）：2915-2935.

[24] LIN C H，LIU J C，LI C C，et al. Parallel Modulus Operations in RSA Encryption by CPU/GPU Hybrid Computation [C]//2014 Ninth Asia Joint Conference on Information Security.Wuhan：IEEE，2015：71-75.

[25] ABOUD S J，ABU-TAIEH E M. A new deterministic RSA-factoring algorithm [J].Journal of Apply Science.2006，8（1）：54-66.

[26] CORON J S，MAY A. Deterministic Polynomial-Time Equivalence of Computing the RSA Secret Key and Factoring [J].Journal of Cryptology，2007，20（1）：39-50.

[27] 隆永紅.用L～3算法分解RSA的模 [J].湘潭大學自然科學學報，1993，15（3）：128-132.

[28] 蔣增榮，曾泳泓，成禮智.大整數(shù)分解算法及其并行實現(xiàn) [J].中山大學學報論叢，1996（5）：6-12.

[29] 崔競松，彭蓉，張煥國，等.一種快速分解大整數(shù)的小因子的優(yōu)化分解樹OFT算法 [J].計算機學報，2003，26（11）：1435-1440.

[30] 霍紅衛(wèi)，潘征.大數(shù)質(zhì)因子分解的量子算法 [J].計算機工程與科學，2003，25（1）：23-25+41.

[31] 王澤輝.大整數(shù)因子分解新算法及對RSA密碼制的解密 [J].中山大學學報（自然科學版），2003，42（5）：15-18.

[32] 戴闊斌.大整數(shù)因子分解問題的研究 [D].湖北：武漢大學，2004.

[33] 李棟，鄒衡，王佐.一種新的基于分布式的RSA模數(shù)分解算法 [J].現(xiàn)代情報，2005（4）：220-221+223.

[34] 戴闊斌，陳建華.大整數(shù)因子分解中的二次篩法優(yōu)化 [J].數(shù)學雜志，2005，25（6）：659-663.

[35] 褚一平，陳勤.分解RSA模數(shù)算法研究 [J].微機發(fā)展，2005（6）：91-92+160.

[36] ZHANG S H，CHEN G L，QIN Z P，et al. An Method of Factoring Large Integers [J].信息安全與通信保密，2005（7）：108-109.

[37] 伍傳敏，孟金濤，劉俊芳.兩類整數(shù)分解算法的分析與改進 [J].計算機工程與設計，2007，28（17）：4094-4095+4104.

[38] 李駿.分布式計算環(huán)境下大整數(shù)分解的研究 [D].上海：上海交通大學，2007.

[39] 王靜，李肯立，許進.Pollard p-1因子分解的DNA計算機算法 [J].計算機研究與發(fā)展，2008，45（Sl）：67-71.

[40] 陳笑偉.關(guān)于大數(shù)分解問題的研究 [D].西寧：青海師范大學，2009.

[41] 付向群，鮑皖蘇，周淳.Shor整數(shù)分解量子算法的加速實現(xiàn) [J].科學通報，2010，55（Z1）：322-327.

[42] 孫克泉.RSA密碼分析中分解大整數(shù)的判定算法 [J].計算機工程，2010，36（15）：142-144.

[43] 張淑梅，宋維堂，宋萬里.一種用于大整數(shù)因數(shù)分解的多相位粒子群算法 [J].計算機工程與應用，2010，46（25）：105-108.

[44] 孫克泉.分解大整數(shù)為兩個素因子乘積的析出算法 [J].天津職業(yè)院校聯(lián)合學報，2011，13（8）：37-42.

[45] 李修美.數(shù)域上的橢圓曲線與整數(shù)分解 [D].北京：清華大學，2013.

[46] 楊莉莉.大數(shù)分解的若干歷史問題研究 [D].臨汾：山西師范大學，2014.

[47] 劉倩，范安東，許凌云，等.云計算在RSA密碼體制分析中的應用 [J].數(shù)學的實踐與認識，2014，44（3）：108-114.

[48] 楊晨鶴，王周寧馨，張禎.關(guān)于大整數(shù)分解的方法探究 [J].科技資訊，2015，13（7）：243-244.

[49] 徐明毅.整數(shù)因子分解的費馬法改進 [J].洛陽師范學院學報，2016，35（8）：1-5.

[50] 王亞輝，顏松遠.一種新的攻擊RSA的量子算法 [J].計算機科學，2016，43（4）：24-27.

[51] 王亞輝，張煥國，吳萬青，等.基于方程求解與相位估計攻擊RSA的量子算法 [J].計算機學報，2017，40（12）：2688-2699.

[52] 王平平，陸正福，楊春堯，等.Shor量子算法的分析及優(yōu)化 [J].通信技術(shù)，2017，50（4）：775-778.

[53] 楊江帥.大整數(shù)分解算法綜述 [J].信息技術(shù)與網(wǎng)絡安全，2018，37（11）：12-15.

[54] 胡建軍，王偉，李恒杰.Pollard ρ算法改進 [J].計算機應用研究，2018，35（7）：2153-2155.

[55] 櫻井幸一，陳治中.密碼·數(shù)論·計算理論的未解決問題 [J].數(shù)學譯林，2002，21（3）：198-204.

[56] WANG X B. Valuated Binary Tree：A New Approach in Study of Integers [J].International Journal of Scientific and Innovative Mathematical Research，2016，4（3）：63-67.

[57] WANG X B. Amusing Properties of Odd Numbers Derived From Valuated Binary Tree [J].IOSR Journal of Mathematics，2016，12（6）：53-57.

[58] WANG X B. Two More Symmetric Properties of Odd Numbers [J].IOSR Journal of Mathematics，2017，13（3）：37-40.

[59] WANG X B. Some More New Properties of Consecutive Odd Numbers [J].Journal of Mathematics Research，2017，9（5）：61-70.

[60] WANG X B. T3 Tree and Its Traits in Understanding Integers [J].Advances in Pure Mathematics，2018，8（5）：494-507.

[61] WANG X B. Genetic Traits of Odd Numbers With Applications in Factorization of Integers [J]. Global Journal of Pure and Applied Mathematics，2017，13（2）：493-517.

[62] WANG X B. Influence of Divisor-ratio to Distribution of Semiprimes Divisor [J].Journal of Mathematics Research，2018，10（4）：54-61.

[63] LI J H. A Parallel Probabilistic Approach to Factorize a Semiprime [J].American Journal of Computational Mathematics，2018，8（2）：175-183.

[64] WANG X B. More on Square and Square Root of a Node on T3 Tree [J].International Journal of Mathematics and Statistics Study，2018，6（3）：1-7.

[65] WANG X B，SHEN Z. Traits of a RSA Modulus on T3 Tree [J].Journal of Mathematics Research，2018，10（6）：15-29.

[66] WANG X B，GUO H Q. Some Divisibility Traits on Valuated Binary Trees [J].International Journal of Applied Physics and Mathematics，2019，9（1）：1-15.

[67] WANG X B，MIAO Y J. Relationship between Divisors Distribution and Square Root of a RSA Modulus [J].International Journal of Information and Electronics Engineering，2019，9（1）：7-11.

[68] WANG X B，GUO H Q. Distribution of RSA Numbers Divisor on T3 Tree [J].International Journal of Information and Electronics Engineering，2019，9（1）：23-29.

[69] WANG X B. Number of Digits in Two Integers and Their Multiplication [J].Journal of Advances in Applied Mathematics，2019，4（2）：69-74.

[70] WANG X B，ZHONG J J. Fast Approach to Factorize Odd Integers with Special Divisors [J].Journal of Mathematics and Statistics，2020，16（1）：24-34.

[71] WANG X B. Algorithm Available for Factoring Big Fermat Numbers [J].Journal of Software，2020，15（3）：86-97.

[72] WILFRID K. Prime factors k·2n+1 of Fermat numbers Fm and complete factoring status [EB/OL].（2020-07-01）.http：//www.prothsearch.com/fermat.html.

[73] WANG X B. Two Number-guessing Problems Plus Applications in Cryptography [J].International Journal of Network Security，2019，21（3）：494-500.

[74] WANG X B，GUO J X. Deterministic-Embedded Monte Carlo Approach to Find out an Objective Item in a Large Number of Data Sets [J].International Journal of Applied Physics and Mathematics，2019，9（4）：173-181.

[75] WANG X B. Interval Tree and Its Application in Integer Factorization [J].Journal of Mathematics Research，2019，11（2）：103-113.

[76] WANG X B，WU J C. Traits of Interval Tree in Solving Blind Search Problems of Finding a Term in an Ordered Data Set [J].International Journal of Information and Education Technoloy，2020，10（7）：516-522.

作者簡介：王興波（1963—），男，漢族，湖北安陸人，教授，工學博士，主要研究方向：先進制造與計算機應用相關(guān)的教學科研工作;通訊作者：李建輝（1974—），男，漢族，湖南岳陽人，教授，博士，研究方向：信息安全、多重分形和網(wǎng)絡優(yōu)化。