整数分解记录：修订间差异

维基百科，自由的百科全书
下一版本→
删除的内容 添加的内容
可视化wikitext
Rumony CN（留言 | 贡献）
35次编辑
通过翻译页面“Integer factorization records”创建
（没有差异）

2024年2月12日 (一) 09:25的版本

整数因子分解是确定哪些质数能够整除给定正整数的过程。快速进行这个过程在密码学中有应用。难度取决于数字的大小和形式以及其质数因子；目前很难对大的半质数进行因子分解（实际上，对大多数没有小因子的数字都很困难）。

一般形式

第一次大型的分布式因子分解是RSA-129，这是一串129位的挑战数字，1977年的一篇《科学美国人》文章首次推广了RSA密码系统。它在1993年9月至1994年4月之间被因子分解，使用了MPQS（多项式整数四平方算法），通过大约600人通过互联网贡献关系，最后的计算阶段在贝尔实验室的MasPar超级计算机上完成。

在1999年1月至8月期间，RSA-155，一串由RSA公司准备的155位挑战数字，使用GNFS进行因子分解，关系再次由一个庞大的群体贡献，最后的计算阶段在SARA阿姆斯特丹学术计算机中心的Cray C916超级计算机上用了九天多完成。

在2002年1月，Franke等人宣布因子分解了2953 + 1的158位共因子，使用了大约25台PC在波恩大学花费了几个月的时间，最后的阶段使用了一个由六台Pentium-III PC组成的集群完成。

在2003年4月，同一团队使用德国联邦信息安全办公室（BSI）的约100个CPU对160位的RSA-160进行了因子分解，最后的计算阶段使用了SGI Origin超级计算机的25个处理器完成。

在2003年12月，Franke、Kleinjung以及NFSNET合作伙伴的成员因子分解了576位（174位数字的）RSA-576，利用了德国联邦信息安全办公室（BSI）和波恩大学的资源；随后不久，Aoki、Kida、Shimoyama、Sonoda和Ueda宣布他们已经因子分解了21826 + 1的164位共因子。

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

663位（200位数字的）RSA-200挑战数字在2003年12月至2005年5月期间由Franke、Kleinjung等人因子分解，使用了德国联邦信息安全办公室（BSI）的80个Opteron处理器构成的集群；该消息于2005年5月9日宣布[2]。后来，他们在2005年11月成功因子分解了稍小的RSA-640挑战数字。

在2009年12月12日，一个团队，包括CWI、EPFL、INRIA和NTT的研究人员，以及之前记录的作者，成功因子分解了RSA-768，这是一个232位的半质数[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]

特殊形式的数字

12151 − 1，共542位（163位数字），于1993年4月至7月间由CWI和俄勒冈州立大学的一个团队因子分解。[7]

2773 + 1，共774位（233位数字），于2000年4月至11月间由'The Cabal'团队因子分解，矩阵步骤在Cray超级计算机上花费了250小时，该计算机还用于RSA-155。 [8]

2809 − 1，共809位（244位数字），其因子分解在2003年初宣布。筛选工作在CWI、波恩大学科学计算研究所和纯数学系进行，同时利用了J. Franke、T. Kleinjung和F. Bahr家族的私人资源。线性代数步骤由P. Montgomery在阿姆斯特丹的SARA完成。 [9]

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

21039 − 1,共1039位（313位数字）（尽管已知一个23位的因子），由包括K. Aoki、J. Franke、T. Kleinjung、A. K. Lenstra和D. A. Osvik在内的一个团队于2006年9月至2007年5月间使用NTT、EPFL和波恩大学的计算机因子分解。 [11] [12]

21061 − 1，共1061位（320位数字），于2011年初至2012年8月4日由Greg Childers领导的一个团队因子分解，使用了nfs@home BOINC项目进行约300 CPU年的筛选；线性代数阶段在SDSC的Trestles集群和TACC的Lonestar集群上运行，并需要额外的35 CPU年 [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月底发布。整个项目的总计算工作量约为7500 CPU年，采用2.2 GHz Opteron处理器，其中大约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]完成，他在Amazon EC2机器上花费了7600美元的处理时间进行筛选，并在双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] . 22024年，Samer Rahmeh运用绝热量子计算（AQC）成功地对使用Dynex神经形态计算云计算出的201位（666位）质数进行了因子分解[31] 。

因此，关于使用量子计算机进行因子分解的声明受到批评，因为这很大程度上依赖于经典计算来减少所需量子比特的数量 [32] [33]例如，对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]. 
  2. ^ F. Bahr; M. Boehm; J. Franke; T. Kleinjung. RSA200. [2007-05-23]. 
  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]. 
  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. 
  7. ^ P. L. Montgomery. Record Number Field Sieve Factorisations. [2007-11-23]. 
  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]. 
  12. ^ Kazumaro Aoki; Jens Franke; Thorsten Kleinjung; Arjen Lenstra; Dag Arne Osvik. A kilobit special number field sieve factorization. [2007-12-19]. 
  13. ^ Greg Childers. Factorization of a 1061-bit number by the Special Number Field Sieve. Cryptology ePrint Archive. 2012. 
  14. ^ Thorsten Kleinjung; Joppe W Bos; Arjen K Lenstra. Mersenne Factorization Factory. [2015-01-18]. 
  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. 
  19. ^ mersenneforum.org – View Single Post – 5^421-1 sieving (reservations closed). www.mersenneforum.org. 
  20. ^ RSA-210 factored – mersenneforum.org. mersenneforum.org. 
  21. ^ mersenneforum.org – View Single Post – HP49(119).... www.mersenneforum.org. 
  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. 
  25. ^ New largest number factored on a quantum device is 56,153. 
  26. ^ The Mathematical Trick That Helped Smash The Record For The Largest Number Ever Factorised By A.... 2 December 2014. 
  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] （美国英语）. 
  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. Bibcode:2021npjQI...7..156K. S2CID 229156747. arXiv:2012.07825 可免费查阅. doi:10.1038/s41534-021-00478-z.  引用错误：带有name属性“zapata”的<ref>标签用不同内容定义了多次
  31. ^ Rahmeh, Sam. HUBO & QUBO and Prime Factorization. Academia. [2024-02-11] （美国英语）. 
  32. ^ Gidney, Craig. Factoring the largest number ever with a quantum computer. Blog. [2022-07-18] （美国英语）. 
  33. ^ 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=80941465”