GPU-Accelerated Graph-Colored Simulated Annealing for Integer Factorization

आधुनिक डिजिटल दुनिया की बहुत सी सुरक्षा एक सरल गणितीय युक्ति पर टिकी है: दो बड़ी अभाज्य संख्याओं (prime numbers) को आपस में गुणा करना अविश्वसनीय रूप से आसान है, लेकिन परिणाम को देखकर यह पता लगाना बेहद कठिन है कि किन दो संख्याओं का उपयोग किया गया था। यह एकतरफा रास्ता RSA एन्क्रिप्शन की नींव है, वह प्रणाली जो ऑनलाइन बैंकिंग, निजी संदेशों और सुरक्षित संचार की रक्षा करती है। दशकों तक, इस कोड को तोड़ने का एकमात्र ज्ञात तरीका संख्याओं के हर संभावित संयोजन को तब तक आज़माना था जब तक कि सही जोड़ी न मिल जाए, एक ऐसा कार्य जो इतना विशाल है कि सबसे शक्तिशाली सुपरकंप्यूटरों को भी बड़े कुंजियों (keys) के लिए समाधान खोजने में ब्रह्मांड की आयु से अधिक समय लगेगा। हालांकि क्वांटम कंप्यूटर एक दिन इस कोड को तुरंत तोड़ देने का वादा करते हैं, लेकिन वे अभी इस काम के लिए तैयार नहीं हैं। यह एक ऐसा अंतराल छोड़ देता है जहाँ क्लासिकल कंप्यूटरों को समस्या को हल करने का एक नया तरीका खोजना होगा, न कि ब्रूट फोर्स (brute force) द्वारा, बल्कि छिपी हुई संख्याओं की खोज को ऊर्जा और संतुलन के एक पहेली के रूप में मानकर।

इंडियन इंस्टीट्यूट ऑफ टेक्नोलॉजी मद्रास के शोधकर्ताओं ने एक उच्च श्रेणी के कंप्यूटरों में पाए जाने वाले ग्राफिक्स प्रोसेसिंग यूनिट (GPU), जैसे कि गेमिंग और वीडियो रेंडरिंग के लिए उपयोग होने वाले चिप का उपयोग करके इस चुनौती से निपटने के लिए एक नई विधि विकसित की है। संख्याओं का सीधे अनुमान लगाने के बजाय, उन्होंने इस समस्या को पहाड़ियों और घाटियों के एक परिदृश्य (landscape) में बदल दिया, जहाँ समाधान सबसे गहरी घाटी के बिल्कुल निचले हिस्से में स्थित है। उन्होंने दो छिपी हुई अभाज्य संख्याओं के बिट्स को छोटे स्विचों के एक ग्रिड पर मैप किया, जिनमें से प्रत्येक दो अवस्थाओं में से एक में हो सकता है। लक्ष्य उन स्विचों की विशिष्ट व्यवस्था को खोजना था जो निम्नतम ऊर्जा अवस्था (lowest energy state) बनाता है, एक ऐसी संरचना जो गणितीय रूप से दो सही अभाज्य गुणनखंडों (prime factors) को एनकोड करती है।

इसे हल करने के लिए, टीम ने 'सिमुलेटेड एनीलिंग' (simulated annealing) नामक तकनीक का उपयोग किया, जो धातु के दोषों को दूर करने के लिए उसे ठंडा करने की भौतिक प्रक्रिया की नकल करती है। उनके डिजिटल संस्करण में, सिस्टम स्विचों की एक यादृच्छिक (random) व्यवस्था और "गर्मी" के उच्च स्तर के साथ शुरू होता है, जिससे स्विच स्वतंत्र रूप से घूम सकते हैं। जैसे-जैसे सिस्टम ठंडा होता है, स्विच एक अधिक स्थिर पैटर्न में व्यवस्थित होते हैं। शोधकर्ताओं ने अपने सॉफ्टवेयर को एक शक्तिशाली ग्राफिक्स चिप, NVIDIA GH200 पर चलाने के लिए डिज़ाइन किया, जो एक साथ हजारों गणनाएं कर सकता है। क्योंकि उनके द्वारा बनाया गया गणितीय मानचित्र काफी खाली है—जिसका अर्थ है कि अधिकांश स्विच एक-दूसरे के साथ परस्पर क्रिया (interact) नहीं करते हैं—उन्होंने काम को इस तरह व्यवस्थित किया कि कंप्यूटर केवल उन्हीं कनेक्शनों पर ध्यान केंद्रित करे जो वास्तव में मौजूद थे। इसने उन्हें बिना किसी त्रुटि के कई स्विचों को एक साथ अपडेट करने की अनुमति दी, जो एक ऐसी उपलब्धि थी जिसके लिए एक चतुर सॉर्टिंग पद्धति की आवश्यकता थी ताकि यह सुनिश्चित किया जा सके कि कोई भी दो परस्पर क्रिया करने वाले स्विच एक ही क्षण में न बदलें।

सिस्टम हमेशा तुरंत सटीक उत्तर नहीं पाता था। अपने परीक्षणों में, एनीलर लगातार सही समाधान के बहुत करीब पहुँचा, जो अक्सर वास्तविक संख्याओं के कुछ प्रतिशत के भीतर होता है। इस अंतिम अंतर को पाटने के लिए, शोधकर्ताओं ने एक दूसरा चरण जोड़ा: एक निर्देशित खोज (guided search) जिसने उन संख्याओं की जाँच की जो कंप्यूटर के सर्वोत्तम अनुमान के पास थीं। उन्होंने उन संख्याओं को छोड़ने के लिए एक फ़िल्टरिंग विधि का उपयोग किया जो संभवतः अभाज्य नहीं हो सकती थीं, जिससे आवश्यक कार्य में भारी कमी आई। 100-बिट की संख्या के लिए, प्रारंभिक सेटअप से लेकर अंतिम गुणनखंड खोजने तक की पूरी प्रक्रिया एक एकल मशीन पर केवल छह मिनट से कुछ अधिक समय में पूरी हुई। यह पारंपरिक तरीकों की तुलना में काफी तेज़ है, जिन्हें समान कार्य के लिए घंटों लग जाते हैं।

शोधकर्ताओं ने 16 से 128 बिट तक की संख्याओं पर अपने पाइपलाइन का परीक्षण किया। जबकि उन्होंने मिनटों में 100-बिट की संख्याओं को सफलतापूर्वक फैक्टर किया, उन्होंने उल्लेख किया कि यह विधि अभी भी सटीक उत्तर खोजने के लिए अंतिम खोज चरण पर निर्भर करती है। इस अंतिम चरण की गति इस बात पर बहुत अधिक निर्भर करती है कि प्रारंभिक अनुमान सत्य के कितने करीब था। टीम ने पाया कि उनकी विधि पुराने, सरल अनुमानों की तुलना में लगातार बहुत बेहतर शुरुआती बिंदु प्रदान करती थी, जिससे अंतिम खोज के लिए आवश्यक समय में बड़ी गिरावट आई। उन्होंने यह भी प्रदर्शित किया कि 'कॉपर्समिथ विधि' (Coppersmith's method) नामक एक विशिष्ट गणितीय तकनीक का उपयोग करने से बड़ी संख्याओं के लिए प्रक्रिया को और तेज किया जा सकता है, जिससे 128-बिट नंबरों के लिए समय महीनों से घटकर दिनों में आ सकता है।

यह कार्य वर्तमान एन्क्रिप्शन मानकों को नहीं तोड़ता है, क्योंकि परीक्षण की गई संख्याएं वास्तविक दुनिया की सुरक्षा में उपयोग की जाने वाली संख्याओं की तुलना में बहुत छोटी हैं, जिनमें आमतौर पर सैकड़ों अंक होते हैं। हालांकि, यह सिद्ध करता है कि एक क्लासिकल कंप्यूटर, जब सही गणितीय संरचना और पैरेलल प्रोसेसिंग के लिए अनुकूलित हो, तो इस प्रकार की समस्या को पहले की तुलना में बहुत अधिक कुशलता से हल कर सकता है। अध्ययन बताता है कि बाधा अब कंप्यूटर की कच्ची गति नहीं है, बल्कि यह है कि प्रारंभिक अनुमान को कितनी अच्छी तरह से परिष्कृत किया जा सकता है। यदि भविष्य के सुधार कंप्यूटर को समाधान के और भी करीब ला सकते हैं, तो अंतिम खोज चरण इतना छोटा हो सकता है कि पूरी प्रक्रिया एक दिन 'पॉलीनोमियल टाइम' (polynomial time) में चल सके, जो एक सैद्धांतिक गति है जो क्रिप्टोग्राफी के परिदृश्य को बदल देगी। फिलहाल, शोधकर्ताओं ने दिखाया है कि समस्या के अद्वितीय आकार का सम्मान करके और आधुनिक ग्राफिक्स चिप्स की विशाल पैरेलल पावर का उपयोग करके, एक प्रतीत होने वाली असंभव गणितीय ताले को एक हल करने योग्य पहेली में बदला जा सकता है।