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

From Vigyanwiki

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

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

प्रथम विशाल वितरित कारकीकरण आरएसए-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]1000 और 1200 के मध्य n के साथ संख्या 2n − 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] और एमसीव जैसे सशक्त ओपन-सोर्स सॉफ़्टवेयर से,[16] अंतिम चरणों के लिए, 750 बिट्स (226 अंक) तक की विशेष-रूप संख्याओं और लगभग 520 बिट्स (157 अंकों) तक की सामान्य-रूप संख्याओं का बिना किसी विशेष गणितीय अनुभव के व्यक्ति द्वारा कुछ पीसी पर कुछ महीनों में गुणनखंडन किया जा सकता है। [17] यदि सीव के लिए कुछ दर्जन पीसी का सहयोग सुनिश्चित करना संभव होता तो ये सीमाएँ लगभग 950 बिट्स (286 अंक) और 600 बिट्स (181 अंक तक बढ़ जाती हैं,[18]वर्तमान में फिनिशिंग चरण के लिए मशीन की मेमोरी की मात्रा और सीपीयू शक्ति प्रगति में समान बाधाएं हैं।

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

सितंबर 2013 में, 696-बिट (210-अंकीय) आरएसए-210 को रयान प्रॉपर द्वारा गुणनखंडन किया गया था[19]संस्थागत संसाधनों का उपयोग करना; मार्च 2013 और अक्टूबर 2014 के मध्य, 210-अंकीय संख्या (होम प्राइम अनुक्रम में 49 से प्रारम्भ होने वाला 117 पद) व्रेथएक्स नामक उपयोगकर्ता द्वारा पूर्ण किया गया था,[20] जिसमें सीव के लिए ऐमजॉन ईसी2 मशीनों पर $7600 मूल्य के प्रसंस्करण समय [21] और रैखिक बीजगणित के लिए दोहरी जिऑन E5-2687W v1 का उपयोग किया गया था।

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

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

अप्रैल 2012 में, का गुणनखंडन कमरे के तापमान (300K) द्वारा NMR एडियाबैटिक क्वांटम गणना की रिपोर्ट शिन्हुआ पेंग के नेतृत्व वाले समूह द्वारा की गई थी।[23] नवंबर 2014 में यह ज्ञात हुआ कि 2012 के प्रयोग ने वास्तव में बिना विचार किए अधिक बड़ी संख्याओं को सम्मिलित कर लिया था। [24][25] अप्रैल 2016 में 18-बिट संख्या 200,099 को डी-वेव 2X क्वांटम प्रोसेसर पर क्वांटम एनीलिंग का उपयोग करके गुणनखंडन किया गया था।[26] कुछ ही समय पश्चात, 291 311 को कमरे के तापमान से अधिक पर एनएमआर का उपयोग करके गुणनखंडन किया गया।[27] 2019 के अंत में, ज़पाटा कंप्यूटिंग ने 1,099,551,473,989 गुणनखंडन करने का दावा किया,[28] और 2021 में इस गणना का वर्णन करने पेपर प्रस्तुत किया गया था।[29]दिसंबर 2022 में, 48-बिट गुणनखंडन चीन में समूह द्वारा 10-क्यूबिट फ्लिप-चिप सुपरकंडक्टिंग क्वांटम कंप्यूटिंग का उपयोग करके पूर्ण किया गया था।[30] समूह ने क्रमशः 3 और 5 सुपरकंडक्टिंग क्वैबिट के साथ 11-बिट पूर्णांक 1961 और 26-बिट पूर्णांक 48567227 का भी गुणनखंडन किया था। चूँकि, समूह द्वारा इस दृष्टिकोण को श्रेष्ठ-क्वांटम हाइब्रिड के रूप में वर्णित किया गया था, जिसमें श्नोर के गुणनखंडन एल्गोरिदम में उपयोग की जाने वाली समय लेने वाली एसआर-जोड़ी पीढ़ी को अनुकूलित करने के लिए क्वांटम अनुमानित अनुकूलन एल्गोरिदम का[31] और परिणामी रैखिक समीकरणों का निवारण करने के लिए क्लासिकल कंप्यूटर उपयोग किया गया था।

इस प्रकार, क्वांटम कंप्यूटरों के साथ गुणनखंडन के वर्णन की आवश्यक क्वैबिट की संख्या को कम करने के लिए श्रेष्ठ गणना पर अधिक निर्भरता के लिए आलोचना की गई है।[32] उदाहरण के लिए, 1,099,551,473,989 का गुणनखंडीकरण समस्या को तीन-क्विबिट क्वांटम परिपथ तक कम करने के लिए श्रेष्ठ प्री-प्रोसेसिंग पर निर्भर करता है।[29] इसके अतिरिक्त, इस पेपर में सम्मिलित तीन संख्याओं (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. ↑ "RSA-210 factored - mersenneforum.org". mersenneforum.org.
  20. ↑ "mersenneforum.org - View Single Post - HP49(119)..." www.mersenneforum.org.
  21. ↑ "संग्रहीत प्रति". Archived from the original on 2021-04-16. Retrieved 2020-03-04.
  22. ↑ 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.
  23. ↑ "143 is largest number yet to be factored by a quantum algorithm".
  24. ↑ "New largest number factored on a quantum device is 56,153".
  25. ↑ "वह गणितीय युक्ति जिसने किसी द्वारा गुणनखंडित अब तक की सबसे बड़ी संख्या का रिकॉर्ड तोड़ने में मदद की..." 2 December 2014.
  26. ↑ 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.
  27. ↑ 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].
  28. ↑ Crane, Leah. "क्वांटम कंप्यूटर ने अभाज्य संख्या गुणनखंड खोजने में नया कीर्तिमान स्थापित किया". New Scientist (in English). Retrieved 2020-10-02.
  29. ↑ 29.0 29.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.
  30. ↑ 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].
  31. ↑ Schnorr, Claus (2021), "Fast Factoring Integers by SVP Algorithms, corrected", Cryptology ePrint Archive
  32. ↑ Gidney, Craig. "क्वांटम कंप्यूटर के साथ अब तक की सबसे बड़ी संख्या का गुणनखंडन". Blog (in English). Retrieved 2022-07-18.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=पूर्णांक_गुणनखंडन_रिकॉर्ड&oldid=281292’