पूर्णांक गुणनखंडन रिकॉर्ड

From Vigyanwiki
Revision as of 16:36, 12 August 2023 by alpha>Artiverma

पूर्णांक गुणनखंडन यह निर्धारित करने की प्रक्रिया है कि कौन सी अभाज्य संख्याएँ किसी दिए गए धनात्मक पूर्णांक को विभाजित करती हैं। इसे शीघ्रता से करने से क्रिप्टोग्राफी में अनुप्रयोग होते हैं। कठिनाई, संख्या और उसके अभाज्य कारकों के आकार और रूप दोनों पर निर्भर करती है; वर्तमान में बड़े सेमीप्राइम्स (और, वास्तव में, अधिकांश संख्याएँ जिनमें कोई छोटा कारक नहीं है) का गुणनखंड करना अधिक कठिन है।

सामान्य रूप की संख्याएँ

प्रथम विशाल वितरित कारकीकरण आरएसए-129 था, जो 1977 के साइंटिफिक अमेरिकन लेख में वर्णित 129-अंकीय चुनौती संख्या थी जिसने प्रथम बार आरएसए क्रिप्टोसिस्टम को लोकप्रिय बनाया था। इसे सितंबर 1993 और अप्रैल 1994 के मध्य एमपीक्यूएस का उपयोग करके गुणनखंडित किया गया था, जिसमें इंटरनेट के माध्यम से लगभग 600 लोगों ने योगदान दिया था, और गणना के अंतिम चरण बेल लैब्स में मासपार सुपरकंप्यूटर पर किए गए थे।

जनवरी और अगस्त 1999 के मध्य, आरएसए-155, आरएसए कंपनी द्वारा तैयार किया गया 155-अंकीय चुनौती नंबर, बड़े समूह द्वारा पुनः योगदान किए गए संबंधों के साथ जीएनएफएस का उपयोग करके गुणनखंडित किया गया था, और गणना के अंतिम चरण केवल नौ दिनों में सारा एम्स्टर्डम अकादमिक कंप्यूटर सेंटर में क्रे C90 सुपर कंप्यूटर पर पूर्ण किए गए थे।

जनवरी 2002 में, फ्रांके एट अल ने बॉन विश्वविद्यालय में लगभग 25 पीसी पर कुछ महीनों का उपयोग करके, 2953+1 के 158-अंकीय सहकारक के गुणनखंडन की घोषणा की, जिसमें अंतिम चरण छह पेंटियम-III पीसी के क्लस्टर का उपयोग करके पूर्ण किया गया था।

अप्रैल 2003 में, उसी टीम ने बीएसआई में लगभग सौ सीपीयू का उपयोग करके 160-अंकीय आरएसए-160 का फैक्टरिंग किया, जिसमें एसजीआई ओरिजिन सुपरकंप्यूटर के 25 प्रोसेसर का उपयोग करके गणना के अंतिम चरण किए गए थे।

576-बिट (174-अंकीय) आरएसए-576 को बीएसआई और बॉन विश्वविद्यालय के संसाधनों का उपयोग करके दिसंबर 2003 में फ्रेंक, क्लेनजंग और एनएफएसएनईटी सहयोग के सदस्यों द्वारा तैयार किया गया था; इसके शीघ्र पश्चात, आओकी, किडा, शिमोयामा, सोनोदा और उएदा ने घोषणा की कि उन्होंने 21826+1 का 164-अंकीय सहकारक तैयार कर लिया है।

11281+1 का 176-अंकीय सहकारक को फरवरी और मई 2005 के मध्य जापान में निप्पॉन टेलीग्राफ और टेलीफोन और रिक्क्यो विश्वविद्यालय की मशीनों का उपयोग करके एओकी, किडा, शिमोयामा और उएदा द्वारा फैक्टर किया गया था।[1]663-बिट (200-अंकीय) आरएसए-200 चुनौती संख्या को फ्रांके, क्लेनजंग एट अल द्वारा फैक्टर किया गया था। दिसंबर 2003 और मई 2005 के मध्य, जर्मनी में बीएसआई में 80 ओपर्टन प्रोसेसर के क्लस्टर का उपयोग करते हुए; घोषणा 9 मई 2005 को की गई थी।[2] पश्चात में उन्होंने (नवंबर 2005) छोटी आरएसए-640 चुनौती संख्या पर विचार किया गया था।

12 दिसंबर, 2009 को, पूर्व रिकॉर्ड के लेखकों के अतिरिक्त सेंट्रम विस्कुंडे और इंफॉर्मेटिका, ईपीएफएल, आईएनआरआईए और एनटीटी के शोधकर्ताओं सहित टीम ने आरएसए-768, 232-अंकों का सेमीप्राइम तैयार किया।[3] उन्होंने सिंगल कोर 2.2 गीगाहर्ट्ज एएमडी ओपर्टन पर लगभग 2000 वर्षों की कंप्यूटिंग के समान का उपयोग किया।

नवंबर 2019 में, 795-बिट (240-अंक) आरएसए-240 को फैब्रिस बौडोट, पियरिक गौड्री, ऑरोर गुइलेविक, नादिया हेनिंगर, इमैनुएल थॉम और पॉल ज़िम्मरमैन द्वारा तैयार किया गया था।[4][5]फरवरी 2020 में, 829-बिट (250-अंकीय) आरएसए-250 का गुणनखंड पूर्ण हो गया था।[6]

विशेष रूप की संख्याएँ

12151- 542 बिट्स (163 अंक) में से 1, अप्रैल और जुलाई 1993 के मध्य सेंट्रम विस्कुंडे एंड इंफॉर्मेटिका और ओरेगन स्टेट यूनिवर्सिटी की टीम द्वारा फैक्टर किया गया था।[7] 774 बिट्स (233 अंक) में से 2773+1, अप्रैल और नवंबर 2000 के मध्य 'द कैबल' द्वारा फैक्टर किया गया था, क्रे पर 250 घंटों से अधिक समय तक किए गए मैट्रिक्स चरण का उपयोग आरएसए-155 के लिए भी किया गया था।[8]2809-- 809 बिट्स (244 अंक) में से 1, के गुणनखंडन की घोषणा जनवरी 2003 की शुरुआत में की गई थी। सीडब्ल्यूआई, वैज्ञानिक कंप्यूटिंग संस्थान और बॉन विश्वविद्यालय के शुद्ध गणित विभाग में जे. फ्रांके, टी. क्लेनजंग और एफ. बह्र के सदस्य के निजी संसाधन का उपयोग करके छानने का काम किया गया था। रैखिक बीजगणित का चरण एम्स्टर्डम में सारा में पी. मोंटगोमरी द्वारा किया गया था।[9]6353- 1, 911 बिट्स (275 अंक) में से 1 को सितंबर 2005 और जनवरी 2006 के मध्य एओकी, किडा, शिमोयामा और उएडा द्वारा फैक्टर किया गया था।[10]21039-- 1039 बिट्स (313 अंक) में से 1 (चूँकि 23 बिट्स का कारक पूर्व से ही ज्ञात था) को सितंबर 2006 और मई 2007 के मध्य के. आओकी, जे. फ्रांके, टी. क्लेनजंग सहित ओस्विक, एनटीटी, ईपीएफएल के समूह द्वारा बॉन विश्वविद्यालय में कंप्यूटर का उपयोग करके फैक्टर किया गया था। [11][12]21061 - 1, 1061 बिट्स (320 अंक) में से 1 को 2011 की शुरुआत और 4 अगस्त 2012 के मध्य सीएसयू फुलर्टन में ग्रेग चाइल्डर्स की अध्यक्षता वाले समूह द्वारा लगभग 300 सीपीयू-वर्षों की छंटाई के लिए एनएफएस@होम बीओआईएनसी प्रोजेक्ट का उपयोग करके फैक्टर किया गया था। रैखिक बीजगणित एसडीएससी में ट्रेस्टल्स क्लस्टर और टीएसीसी में लोनस्टार क्लस्टर में चलाया गया था और अतिरिक्त 35 सीपीयू-वर्ष की आवश्यकता थी।[13] संख्या 2 के सभी अकारक भागn − 1000 और 1200 के मध्य n के साथ 1 को बहु-संख्या-छलनी दृष्टिकोण द्वारा गुणनखंडित किया गया था जिसमें टी. क्लेनजंग, जे. बोस और समूह द्वारा कई संख्याओं के लिए साथ अधिक सारे छानने का काम किया जा सकता था। ए.के. लेनस्ट्रा, 2010 में शुरू।[14] सटीक होने के लिए, n=1081 (326 अंक) 11 मार्च 2013 को पूर्ण हुआ; n=1111 (335 अंक) 13 जून 2013 को; n=1129 (340 अंक) 20 सितंबर 2013 को; 28 अक्टूबर 2013 को n=1153 (348 अंक); n=1159 (349 अंक) 9 फरवरी 2014 को; 29 मई 2014 को n=1177 (355 अंक), 22 अगस्त 2014 को n=1193 (360 अंक), और 11 दिसंबर 2014 को n=1199 (361 अंक); प्रथम विस्तृत घोषणा अगस्त 2014 के अंत में की गई थी। परियोजना के लिए कुल प्रयास 2.2 गीगाहर्ट्ज़ ओप्टेरॉन पर 7500 सीपीयू-वर्षों के क्रम का है, जिसमें लगभग 5700 वर्ष छानने और रैखिक बीजगणित पर 1800 वर्ष व्यतीत हुए हैं।

व्यक्तियों के प्रयासों की तुलना

2007 के अंत तक, मेमोरी की कीमतों में लगातार गिरावट, मल्टी-कोर 64-बिट कंप्यूटर की तैयार उपलब्धता और जीजीएनएफएस के माध्यम से कुशल सिविंग कोड (बॉन समूह के थॉर्स्टन क्लेनजंग द्वारा विकसित) की उपलब्धता के लिए धन्यवाद।[15] और msieve जैसे मजबूत ओपन-सोर्स सॉफ़्टवेयर का[16] अंतिम चरणों के लिए, 750 बिट्स (226 अंक) तक की विशेष-रूप संख्याओं और लगभग 520 बिट्स (157 अंकों) तक की सामान्य-रूप संख्याओं को कुछ महीनों में ही व्यक्ति द्वारा कुछ पीसी पर फैक्टर किया जा सकता है। विशेष गणितीय अनुभव.[17] ये सीमाएँ लगभग 950 बिट्स (286 अंक) तक बढ़ जाती हैं[18] और 600 बिट्स (181 अंक)[19] यदि छानने के लिए कुछ दर्जन पीसी का सहयोग सुनिश्चित करना संभव होता; वर्तमान में फिनिशिंग चरण के लिए मशीन की मेमोरी की मात्रा और सीपीयू शक्ति प्रगति में समान बाधाएं हैं।

2009 में, बेंजामिन मूडी ने इंटरनेट पर पाए जाने वाले सॉफ़्टवेयर का उपयोग करके TI-83 श्रृंखला|TI-83 ग्राफ़िंग कैलकुलेटर पर हस्ताक्षर करने के लिए 512-बिट (155-अंकीय) आरएसए कुंजी का उपयोग किया; इसने अंततः टेक्सास इंस्ट्रूमेंट्स को प्रमुख विवाद पर हस्ताक्षर करने के लिए प्रेरित किया।

सितंबर 2013 में, 696-बिट (210-अंकीय) आरएसए नंबर#आरएसए-210|आरएसए-210 को रयान प्रॉपर द्वारा फैक्टर किया गया था[20] संस्थागत संसाधनों का उपयोग करना; मार्च 2013 और अक्टूबर 2014 के मध्य, और 210-अंकीय संख्या (होम प्राइम अनुक्रम में 49 से शुरू होने वाला 117 वां पद) WraithX नामक उपयोगकर्ता द्वारा पूर्ण किया गया था,[21] Amazon EC2 मशीनों पर $7600 मूल्य के प्रसंस्करण समय का उपयोग करना[22] छानने के लिए, और रैखिक बीजगणित के लिए दोहरी Xeon E5-2687W v1 पर चार महीने।

क्वांटम कंप्यूटर द्वारा प्रयासों के रिकॉर्ड

शोर के एल्गोरिदम द्वारा विश्वसनीय रूप से फैक्टर की गई सबसे बड़ी संख्या 21 है जिसे 2012 में फैक्टर किया गया था।[23] 15 को पूर्व कई प्रयोगशालाओं द्वारा फैक्टर किया गया था।

अप्रैल 2012 में, का गुणनखंडन कमरे के तापमान (300K) द्वारा NMR एडियाबैटिक क्वांटम गणना की रिपोर्ट शिन्हुआ पेंग के नेतृत्व वाले समूह द्वारा की गई थी।[24] नवंबर 2014 में इसकी खोज हुई थी 2012 के प्रयोग ने वास्तव में बिना जाने-समझे अधिक बड़ी संख्याओं को शामिल कर लिया था। [25][26] अप्रैल 2016 में 18-बिट संख्या 200,099 को डी-वेव 2X क्वांटम प्रोसेसर पर क्वांटम एनीलिंग का उपयोग करके फैक्टर किया गया था।[27] कुछ ही समय पश्चात, 291 311 को कमरे के तापमान से अधिक पर एनएमआर का उपयोग करके फैक्टर किया गया।[28] 2019 के अंत में, ज़पाटा कंप्यूटिंग ने 1,099,551,473,989 फ़ैक्टर करने का दावा किया,[29] और 2021 में इस गणना का वर्णन करने वाला पेपर जारी किया।[30] दिसंबर 2022 में, 48-बिट फ़ैक्टराइज़ेशन चीन में टीम द्वारा 10-क्यूबिट फ्लिप-चिप सुपरकंडक्टिंग क्वांटम कंप्यूटिंग का उपयोग करके पूर्ण किया गया था।[31] टीम ने क्रमशः 3 और 5 सुपरकंडक्टिंग क्वैबिट के साथ 11-बिट पूर्णांक 1961 और 26-बिट पूर्णांक 48567227 को भी फैक्टर किया। हालाँकि, टीम द्वारा इस दृष्टिकोण को शास्त्रीय-क्वांटम हाइब्रिड के रूप में वर्णित किया गया था, जिसमें श्नोर के फैक्टरिंग एल्गोरिदम में उपयोग की जाने वाली समय लेने वाली एसआर-जोड़ी पीढ़ी को अनुकूलित करने के लिए क्वांटम अनुकूलन एल्गोरिदम#क्वांटम अनुमानित अनुकूलन एल्गोरिदम का उपयोग किया गया था।[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". Retrieved 2007-05-23.
  2. ↑ F. Bahr; M. Boehm; J. Franke; T. Kleinjung. "RSA200". Retrieved 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). Retrieved 2013-04-11.
  4. ↑ "[Cado-NFS-discuss] 795-bit factoring and discrete logarithms". Archived from the original on 2019-12-02. Retrieved 2019-12-03.
  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. "रिकॉर्ड संख्या फ़ील्ड चलनी फ़ैक्टराइज़ेशन". Retrieved 2007-11-23.
  8. ↑ The Cabal. "233-digit SNFS factorization". Archived from the original on 2007-11-28. Retrieved 2007-11-23.
  9. ↑ J. Franke. "M809". Archived from the original on 2007-08-23. Retrieved 2007-11-23.
  10. ↑ K. Aoki; Y. Kida; T. Shimoyama; H. Ueda. "SNFS274". Retrieved 2007-05-23.
  11. ↑ K. Aoki; J. Franke; T. Kleinjung; A. K. Lenstra; D. A. Osvik. "Factorization of the 1039th Mersenne number". Retrieved 2007-05-23.
  12. ↑ Kazumaro Aoki; Jens Franke; Thorsten Kleinjung; Arjen Lenstra; Dag Arne Osvik. "A kilobit special number field sieve factorization". Retrieved 2007-12-19.
  13. ↑ Greg Childers (2012). "Factorization of a 1061-bit number by the Special Number Field Sieve". Cryptology ePrint Archive.
  14. ↑ Thorsten Kleinjung; Joppe W Bos; Arjen K Lenstra. "मेर्सन फ़ैक्टराइज़ेशन फ़ैक्टरी". Retrieved 2015-01-18.
  15. ↑ "जीजीएनएफएस सुइट - सोर्सफोर्ज.नेट पर फ़ाइलें ब्राउज़ करें". sourceforge.net.
  16. ↑ "संग्रहीत प्रति". Archived from the original on 2007-12-13. Retrieved 2007-11-23.
  17. ↑ "mersenneforum.org - View Single Post - 2LM Table". www.mersenneforum.org.
  18. ↑ "mersenneforum.org - एकल पोस्ट देखें - नाम के योग्य एक गणना". 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 from the original on 2021-04-16. Retrieved 2020-03-04.
  23. ↑ Martín-López, Enrique; Enrique Martín-López; Anthony Laing; Thomas Lawson; Roberto Alvarez; Xiao-Qi Zhou; Jeremy L. O'Brien (12 October 2012). "क्वबिट रीसाइक्लिंग का उपयोग करके शोर के क्वांटम फैक्टरिंग एल्गोरिदम का प्रायोगिक कार्यान्वयन". Nature Photonics. 6 (11): 773–776. arXiv:1111.4147. Bibcode:2012NaPho...6..773M. doi:10.1038/nphoton.2012.259. S2CID 46546101.
  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. ↑ "वह गणितीय युक्ति जिसने किसी द्वारा गुणनखंडित अब तक की सबसे बड़ी संख्या का रिकॉर्ड तोड़ने में मदद की..." 2 December 2014.
  27. ↑ Dridi, Raouf; Alghassi, Hedayat (21 February 2017). "क्वांटम एनीलिंग और कम्प्यूटेशनल बीजगणितीय ज्यामिति का उपयोग करके प्राइम फ़ैक्टराइज़ेशन". Scientific Reports. 7: 43048. arXiv:1604.05796. Bibcode:2017NatSR...743048D. doi:10.1038/srep43048. PMC 5318873. PMID 28220854.
  28. ↑ Li, Zhaokai; Dattani, Nike; Chen, Xi; Liu, Xiaomei; Wang, Hengyan; Tanburn, Richard; Chen, Hongwei; Peng, Xinhua; Du, Jiangfeng (25 June 2017). "High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spin system: Application to the experimental factorization of 291311". arXiv:1706.08061 [quant-ph].
  29. ↑ Crane, Leah. "क्वांटम कंप्यूटर ने अभाज्य संख्या गुणनखंड खोजने में नया कीर्तिमान स्थापित किया". New Scientist (in English). Retrieved 2020-10-02.
  30. ↑ 30.0 30.1 Karamlou, Amir; Simon, William (28 October 2021). "सुपरकंडक्टिंग क्वांटम प्रोसेसर पर वैरिएबल क्वांटम फैक्टरिंग के प्रदर्शन का विश्लेषण". npj Quantum Information. 7: 156. arXiv:2012.07825. Bibcode:2021npjQI...7..156K. doi:10.1038/s41534-021-00478-z. S2CID 229156747.
  31. ↑ Yan, Bao; Tan, Ziqi; Wei, Shijie; Jiang, Haocong; Wang, Weilong; Wang, Hong; Luo, Lan; Duan, Qianheng; Liu, Yiting; Shi, Wenhao; Fei, Yangyang; Meng, Xiangdong; Han, Yu; Shan, Zheng; Chen, Jiachen; Zhu, Xuhao; Zhang, Chuanyu; Jin, Feitong; Li, Hekang; Song, Chao; Wang, Zhen; Ma, Zhi; Wang, H.; Long, Gui-Lu (2022). "सुपरकंडक्टिंग क्वांटम प्रोसेसर पर सबलीनियर संसाधनों के साथ पूर्णांकों का फैक्टरिंग". arXiv:2212.12372 [quant-ph].
  32. ↑ Schnorr, Claus (2021), "Fast Factoring Integers by SVP Algorithms, corrected", Cryptology ePrint Archive
  33. ↑ Gidney, Craig. "क्वांटम कंप्यूटर के साथ अब तक की सबसे बड़ी संख्या का गुणनखंडन". Blog (in English). Retrieved 2022-07-18.
  34. ↑ Smolin, John A. (2013). "क्वांटम फैक्टरिंग का अत्यधिक सरलीकरण". Nature (in English). 499 (7457): 163–165. arXiv:1301.7007. Bibcode:2013Natur.499..163S. doi:10.1038/nature12290. PMID 23846653. S2CID 118613892.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=पूर्णांक_गुणनखंडन_रिकॉर्ड&oldid=281282’