跳至內容

整數分解記錄

維基百科，自由的百科全書

整數分解是給出一個正整數，將其寫成幾個質數的乘積的過程。在密碼學中應用到了快速進行整數分解的技術。分解的難度取決於給定數字的大小、形式以及其質因子。目前，大的半素數一般都難以分解（實際上，大多數沒有小因子的數字都很難分解）。

一般形式的數字

[編輯]

首次進行大規模分布式分解的整數是RSA-129。1977年《科學美國人》中首次提出了這個挑戰，並首次普及了RSA密碼系統。1993年9月至1994年4月間，基於二次篩選法實現了分解。分解過程中有約600人通過網際網路參與了貢獻，並最終在貝爾實驗室的MasPar超級計算機上完成了分解。

RSA公司提出的另一個的155位挑戰數字RSA-155，在1999年1月至8月間被分解完成。這次分解基於普通數域篩選法，並再次由一個大團隊參與貢獻。最後的計算是由在阿姆斯特丹學術計算中心基金會（英語：Stichting Academisch Rekencentrum Amsterdam）（SARA）的克雷C916超級計算機完成的，僅用時9天多。

在2002年1月，Franke等人在波恩大學花費了大約幾個月的時間用25台PC，成功分解出2953 + 1的158位共因子，最後階段的計算在六台Pentium-III PC組成的集群完成。

在2003年4月，Franke團隊使用德國聯邦信息安全辦公室（BSI）約100個CPU對160位的RSA-160進行了因子分解，最後階段的計算在SGI Origin超級計算機的25個處理器完成。

在2003年12月，Franke、Kleinjung以及NFSNET合作夥伴的成員利用德國聯邦信息安全辦公室（BSI）和波恩大學的資源成功分解了576位（174位數字的）RSA-576；隨後不久，Aoki、Kida、Shimoyama、Sonoda和Ueda宣布他們已經成功分解出了21826 + 1的164位共因子。

在2005年2月至5月期間，Aoki、Kida、Shimoyama和Ueda利用日本NTT和立教大學的計算機成功分解出11281 + 1的176位共因子。 [1]

根據2005年5月9日宣布的消息[2]，在2003年12月至2005年5月期間，663位（200位數字的）RSA-200數字的分解挑戰由Franke、Kleinjung等人使用德國聯邦信息安全辦公室（BSI）中由80個Opteron處理器構成的集群完成，後來，他們在2005年11月成功完成了分解稍小的RSA-640的挑戰。

在2009年12月12日，一個由CWI、EPFL、INRIA、NTT的研究人員和之前記錄的作者組成的團隊，成功分解了一個232位的半質數（RSA-768）[3]。如果這個數字在單個2.2 GHz AMD Opteron核心計算需要進行2000年以上的時間。

在2019年11月，Fabrice Boudot、Pierrick Gaudry、Aurore Guillevic、Nadia Heninger、Emmanuel Thomé和Paul Zimmermann成功分解了795位（240位數字的）RSA-240。 [4][5] 2020年2月，完成829位（250位） 的RSA-250分解。 [6]

特殊形式的數字

[編輯]

1993年4月至7月，12151 − 1，共542位（163位數字）被CWI和俄勒岡州立大學的一個團隊成功分解。[7]

2000年4月至11月，2773 + 1，共774位（233位數字），被「The Cabal」團隊在矩陣步驟在Cray超級計算機上花費了250小時成功分解，該計算機還被用於RSA-155的分解。 [8]

2003年初，2809 − 1，共809位（244位數字），其分解宣布完成。篩選工作在CWI、波恩大學科學計算研究所和純數學系進行，同時利用了J. Franke、T. Kleinjung和F. Bahr家族的私人資源。線性代數步驟由P. Montgomery在阿姆斯特丹的SARA完成。 [9]

2005年9月至2006年1月，6353 − 1，共911位（275位數字），由Aoki、Kida、Shimoyama和Ueda使用SNFS完成分解。 [10]

2006年9月至2007年5月，21039 − 1,共1039位（313位數字）（儘管已知一個23位的因子），由包括K. Aoki、J. Franke、T. Kleinjung、A. K. Lenstra和D. A. Osvik在內的一個團隊使用NTT、EPFL和波恩大學的計算機成功分解。 [11] [12]

2011年初至2012年8月4日，21061 − 1，共1061位（320位數字），由Greg Childers領導的一個團隊完成分解，他們使用nfs@home BOINC項目進行約300個CPU年的篩選；線性代數階段在SDSC的Trestles集群和TACC Lonestar的CPU集群上額外運行了35年 [13]

所有2n − 1（其中n介於1000和1200之間）的未因子分解部分，從2010年開始，由T. Kleinjung、J. Bos和A. K. Lenstra等人組成的團隊通過多數篩法（多數篩法使得多個數字可以同時進行大部分篩選步驟。）的方法進行因子分解，[14]

具體而言：

n = 1081（326位數字）於2013年3月11日完成；

n = 1111（335位數字）於2013年6月13日完成；

n = 1129（340位數字）於2013年9月20日完成；

n = 1153（348位數字）於2013年10月28日完成；

n = 1159（349位數字）於2014年2月9日完成；

n = 1177（355位數字）於2014年5月29日完成；

n = 1193（360位數字）於2014年8月22日完成；

n = 1199（361位數字）於2014年12月11日完成；

首次詳細公告於2014年8月底發布。整個項目如果採用2.2 GHz Opteron處理器，總計算工作量約為7500 年，其中大約5700年用於篩選，1800年用於線性代數。

個人記錄

[編輯]

截至2007年底，得益於內存技術發展，成本持續下降，多核64位計算機更容易獲取，加上ggnfs[15]和在後期msieve [16]等穩定的開源軟體發布。一個甚至不需要任何專業的數學經驗的人就可以幾個月內就在幾台個人計算機上分解最多750位（226位數字）的特殊形式的數字，或者約520位（157位數字）的一般形式的數字 [17]。如果能夠在篩選階段就有幾十台計算機的協助，上限將增加到約950位（286位數字）特殊形式的數字[18] 和600位（181位數字）一般形式的數字[19]。目前，單台計算機在後期階段的內存和CPU性能是主要障礙。

2009年，Benjamin Moody使用在網際網路上找到的軟體，成功分解了用於簽名TI-83圖形計算器的512位（155位數字）RSA密鑰；這最終導致了德州儀器簽名密鑰爭議。

2013年9月，Ryan Propper [20]使用機構資源成功分解了696位（210位數字）的RSA-210；

2013年3月至2014年10月期間，另一個210位數字（以49開頭的家庭素數序列的第117個術語）由一個名為WraithX的用戶 [21]完成；他花費了7600美元租貿Amazon EC2機器的時長來進行篩選工作，並在擁有雙路Xeon E5-2687W v1處理器的機器上花費了四個月進行線性代數計算[22]

量子計算機的新記錄

[編輯]

Shor's算法可靠因子分解的最大數字是21，該數字於2012年被分解[23] 。之前，一些實驗室已經對15進行了因子分解。

在2012年4月，由彭新華領導的一個團隊報告了在室溫（300K）下使用NMR絕熱量子計算機對143進行的因子分解，得到了13 × 11的結果 [24] 。

2014年11月，發現2012年的實驗實際上已經對更大的數字進行了因子分解 [25] [26]

2016年4月，使用D-Wave 2X量子處理器上的量子退火對18位數字200,099進行了因子分解[27]不久之後，利用高於室溫的NMR對291,311進行了因子分解 [28]。

2019年末，Zapata computing聲稱已經因子分解了1,099,551,473,989 [29] ，並在2021年發布了描述該計算的論文 [30] .

2024年，Samer Rahmeh運用絕熱量子計算（AQC）成功地使用Dynex神經形態計算平台對201位（666位）質數進行了因子分解[31] [32]。

因此，關於使用量子計算機進行因子分解的聲明受到批評，因為這很大程度上依賴於經典計算來減少所需量子比特的數量 [33] [34]例如，對1,099,551,473,989的因子分解依賴於經典預處理，將問題減少為一個三比特的量子電路 [30]此外，本文中對三個數字（200,099、291,311和1,099,551,473,989）的因子分解可以輕鬆使用費馬的因子分解方法進行，分別只需3、1和1次迭代。

參見

[編輯]

參考文獻

[編輯]
  1. ^ K. Aoki; Y. Kida; T. Shimoyama; H. Ueda. Factorization of 176-digit number. [2007-05-23]. （原始內容存檔於2012-03-11）. 
  2. ^ F. Bahr; M. Boehm; J. Franke; T. Kleinjung. RSA200. [2007-05-23]. （原始內容存檔於2016-03-04）. 
  3. ^ T. Kleinjung; K. Aoki; J. Franke; A. K. Lenstra; E. Thomé; J. W. Bos; P. Gaudry; A. Kruppa; P. L. Montgomery; D. A. Osvik; H. te Riele; A. Timofeev; P. Zimmermann. Factorization of a 768-bit RSA modulus (PDF). [2013-04-11]. （原始內容存檔 (PDF)於2010-03-31）. 
  4. ^ [Cado-NFS-discuss] 795-bit factoring and discrete logarithms. [2019-12-03]. （原始內容存檔於2019-12-02）. 
  5. ^ F. Boudot et al, "Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment," （頁面存檔備份，存於網際網路檔案館） June 10, 2020.
  6. ^ LISTSERV - NMBRTHRY Archives - LISTSERV.NODAK.EDU. [2024-02-12]. （原始內容存檔於2024-08-16）. 
  7. ^ P. L. Montgomery. Record Number Field Sieve Factorisations. [2007-11-23]. （原始內容存檔於2024-01-07）. 
  8. ^ The Cabal. 233-digit SNFS factorization. [2007-11-23]. （原始內容存檔於2007-11-28）. 
  9. ^ J. Franke. M809. [2007-11-23]. （原始內容存檔於2007-08-23）. 
  10. ^ K. Aoki; Y. Kida; T. Shimoyama; H. Ueda. SNFS274. [2007-05-23]. 
  11. ^ K. Aoki; J. Franke; T. Kleinjung; A. K. Lenstra; D. A. Osvik. Factorization of the 1039th Mersenne number. [2007-05-23]. （原始內容存檔於2024-07-21）. 
  12. ^ Kazumaro Aoki; Jens Franke; Thorsten Kleinjung; Arjen Lenstra; Dag Arne Osvik. A kilobit special number field sieve factorization. [2007-12-19]. （原始內容存檔於2024-01-07）. 
  13. ^ Greg Childers. Factorization of a 1061-bit number by the Special Number Field Sieve. Cryptology ePrint Archive. 2012 [2024-02-12]. （原始內容存檔於2024-01-07）. 
  14. ^ Thorsten Kleinjung; Joppe W Bos; Arjen K Lenstra. Mersenne Factorization Factory. [2015-01-18]. （原始內容存檔於2024-04-20）. 
  15. ^ Archived copy. [2007-11-23]. （原始內容存檔於2007-12-13）. 
  16. ^ mersenneforum.org – View Single Post – 2LM Table. www.mersenneforum.org. 
  17. ^ mersenneforum.org – View Single Post – A computation worthy of the name. www.mersenneforum.org. 
  18. ^ mersenneforum.org – View Single Post – 5^421-1 sieving (reservations closed). www.mersenneforum.org. [2024-02-12]. （原始內容存檔於2024-01-07）. 
  19. ^ mersenneforum.org – View Single Post – 5^421-1 sieving (reservations closed). www.mersenneforum.org. [2024-02-12]. （原始內容存檔於2024-01-07）. 
  20. ^ RSA-210 factored – mersenneforum.org. mersenneforum.org. [2024-02-12]. （原始內容存檔於2024-01-07）. 
  21. ^ mersenneforum.org – View Single Post – HP49(119).... www.mersenneforum.org. [2024-02-12]. （原始內容存檔於2024-01-07）. 
  22. ^ Archived copy. [2020-03-04]. （原始內容存檔於2021-04-16）. 
  23. ^ Martín-López, Enrique; Enrique Martín-López; Anthony Laing; Thomas Lawson; Roberto Alvarez; Xiao-Qi Zhou; Jeremy L. O'Brien. Experimental realization of Shor's quantum factoring algorithm using qubit recycling. Nature Photonics. 12 October 2012, 6 (11): 773–776. Bibcode:2012NaPho...6..773M. S2CID 46546101. arXiv:1111.4147 可免費查閱. doi:10.1038/nphoton.2012.259. 
  24. ^ 143 is largest number yet to be factored by a quantum algorithm. [2024-02-12]. （原始內容存檔於2023-11-28）. 
  25. ^ New largest number factored on a quantum device is 56,153. [2024-02-12]. （原始內容存檔於2017-12-11）. 
  26. ^ The Mathematical Trick That Helped Smash The Record For The Largest Number Ever Factorised By A.... 2 December 2014 [2024-02-12]. （原始內容存檔於2024-04-16）. 
  27. ^ Dridi, Raouf; Alghassi, Hedayat. Prime factorization using quantum annealing and computational algebraic geometry. Scientific Reports. 21 February 2017, 7: 43048. Bibcode:2017NatSR...743048D. PMC 5318873 可免費查閱. PMID 28220854. arXiv:1604.05796 可免費查閱. doi:10.1038/srep43048. 
  28. ^ Li, Zhaokai; Dattani, Nike. High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spin system: Application to the experimental factorization of 291311. 25 June 2017. arXiv:1706.08061 可免費查閱 [quant-ph]. 
  29. ^ Crane, Leah. Quantum computer sets new record for finding prime number factors. New Scientist. [2020-10-02]. （原始內容存檔於2024-05-26） （美國英語）. 
  30. ^ 30.0 30.1 Karamlou, Amir; Simon, William. Analyzing the performance of variational quantum factoring on a superconducting quantum processor. npj Quantum Information. 28 October 2021, 7: 156 [2024-02-12]. Bibcode:2021npjQI...7..156K. S2CID 229156747. arXiv:2012.07825 可免費查閱. doi:10.1038/s41534-021-00478-z. （原始內容存檔於2024-01-15）. 
  31. ^ Rahmeh, Sam. HUBO & QUBO and Prime Factorization. Academia. [2024-02-11]. （原始內容存檔於2024-06-14） （美國英語）. 
  32. ^ Rahmeh, Sam. HUBO & QUBO 质因数分解（Rumony译—知乎平台）. [2024-01-04] （中文（中國大陸））. 
  33. ^ Gidney, Craig. Factoring the largest number ever with a quantum computer. Blog. [2022-07-18]. （原始內容存檔於2023-12-06） （美國英語）. 
  34. ^ Smolin, John A. Oversimplifying quantum factoring. Nature. 2013, 499 (7457): 163–165. Bibcode:2013Natur.499..163S. PMID 23846653. S2CID 118613892. arXiv:1301.7007 可免費查閱. doi:10.1038/nature12290 （美國英語）. 
取自「https://zh.wikipedia.org/w/index.php?title=整数分解记录&oldid=84029778」