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

王興波 唐春明 李建輝

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

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

中圖分類(lèi)號(hào)：TN918? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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ù)分解問(wèn)題是數(shù)論的困難問(wèn)題之一，也是人類(lèi)尚未完全解決的科學(xué)問(wèn)題之一，一直受到世界各國(guó)眾多數(shù)學(xué)和信息安全工作者的關(guān)注。近百年來(lái)，人類(lèi)對(duì)于破解這個(gè)難題的努力一直未有間斷，其間有興奮、失落，亦有努力和希望并行，構(gòu)成了解決這個(gè)難題的艱難歷程。

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

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

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

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

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

1.1? 國(guó)外研究

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

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

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

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

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

以下分別簡(jiǎn)述各階段的主要成果及特點(diǎn)。

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

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

1.1.2? 1975年—1995年“眾說(shuō)紛紜”的20年

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

1.1.3? 1995年—2010年“計(jì)窮力竭”的15年

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

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

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

1.1.4? 2010年以來(lái)“再入迷茫”的年代

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

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

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

1.2? 國(guó)內(nèi)研究

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

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

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

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

1.2.1? 綜述學(xué)習(xí)

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

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

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

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

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

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

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

1.2.2? 局部探索

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2.3? 頂天不立地

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

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

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

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

文獻(xiàn)[52]試圖實(shí)施Pollard p-1因子分解的DNA計(jì)算機(jī)算法，未見(jiàn)具體計(jì)算方案，也未見(jiàn)后續(xù)成果報(bào)道。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

設(shè)N=pq，1

2.3? 取得的成果

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

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

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

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

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

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

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

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

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

2.4? 未來(lái)研究

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

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

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

3? 結(jié)? 論

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

參考文獻(xiàn)：

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

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

[3] 董青，吳楠.整數(shù)質(zhì)因子分解算法新進(jìn)展與傳統(tǒng)密碼學(xué)面臨的挑戰(zhàn) [J].計(jì)算機(jī)科學(xué)，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].計(jì)算機(jī)應(yīng)用研究，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].湘潭大學(xué)自然科學(xué)學(xué)報(bào)，1993，15（3）：128-132.

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

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

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

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

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

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

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

[35] 褚一平，陳勤.分解RSA模數(shù)算法研究 [J].微機(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] 伍傳敏，孟金濤，劉俊芳.兩類(lèi)整數(shù)分解算法的分析與改進(jìn) [J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，28（17）：4094-4095+4104.

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

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

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

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

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

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

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

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

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

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

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

[49] 徐明毅.整數(shù)因子分解的費(fèi)馬法改進(jìn) [J].洛陽(yáng)師范學(xué)院學(xué)報(bào)，2016，35（8）：1-5.

[50] 王亞輝，顏松遠(yuǎn).一種新的攻擊RSA的量子算法 [J].計(jì)算機(jī)科學(xué)，2016，43（4）：24-27.

[51] 王亞輝，張煥國(guó)，吳萬(wàn)青，等.基于方程求解與相位估計(jì)攻擊RSA的量子算法 [J].計(jì)算機(jī)學(xué)報(bào)，2017，40（12）：2688-2699.

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

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

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

[55] 櫻井幸一，陳治中.密碼·數(shù)論·計(jì)算理論的未解決問(wèn)題 [J].數(shù)學(xué)譯林，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.

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