跳转到内容

整数分解记录

维基百科，自由的百科全书

整数分解是给出一个正整数，将其写成几个质数的乘积的过程。在密码学中应用到了快速进行整数分解的技术。分解的难度取决于给定数字的大小、形式以及其质因子。目前，大的半素数一般都难以分解（实际上，大多数没有小因子的数字都很难分解）。

一般形式的数字

[编辑]

首次进行大规模分布式分解的整数是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”