एक बड़ी अभाज्य संख्या कैसे बनाएं | क्वांटा पत्रिका

अभाज्य संख्याएँ पेचीदा चीज़ें हैं। हम स्कूल में सीखते हैं कि वे संख्याएँ हैं जिनमें 1 और स्वयं के अलावा कोई कारक नहीं है, और गणितज्ञ हजारों वर्षों से जानते हैं कि उनकी अनंत संख्या मौजूद है। कमांड पर किसी का उत्पादन करना ऐसा प्रतीत नहीं होता कि यह कठिन होना चाहिए।

लेकिन यह है। मनमाने ढंग से बड़ी अभाज्य संख्याएँ बनाना उल्लेखनीय रूप से जटिल है। आपके पास मूल रूप से दो कम्प्यूटेशनल विकल्प हैं, दोनों में कमियां हैं। आप यादृच्छिकता का उपयोग कर सकते हैं और अनुमान लगाकर किसी एक को ढूंढ सकते हैं, लेकिन यह विधि असंगत है - आप हर बार एक अलग अभाज्य उत्पन्न करने का जोखिम उठाते हैं। या आप अधिक विश्वसनीय, नियतात्मक एल्गोरिदम का उपयोग कर सकते हैं, लेकिन भारी कम्प्यूटेशनल लागत पर।

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

उन्होंने कहा, "उन्होंने प्रयासों का एक क्रम तैयार किया, उनमें से प्रत्येक ने एक अलग लंबाई की अभाज्य संख्या बनाने की कोशिश की और दिखाया कि उनमें से एक प्रयास काम करता है।" रोई बताओ, इंस्टीट्यूट फॉर एडवांस्ड स्टडी के एक सैद्धांतिक कंप्यूटर वैज्ञानिक जो इस काम में शामिल नहीं थे। "यह एक ऐसा निर्माण है जो नियतात्मक रूप से चुने गए प्राइम को आउटपुट करता है, लेकिन आपको इस प्रक्रिया में सिक्के उछालने और यादृच्छिक विकल्प बनाने की अनुमति देता है।"

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

समय के साथ, शोधकर्ताओं ने उपरोक्त दृष्टिकोण विकसित किए। सबसे आसान तरीका सिर्फ अनुमान लगाना है। उदाहरण के लिए, यदि आप 1,000 अंकों वाला अभाज्य संख्या चाहते हैं, तो आप यादृच्छिक रूप से 1,000 अंकों की संख्या चुन सकते हैं और फिर उसकी जांच कर सकते हैं। "यदि यह प्राइम नहीं है, तो आप बस एक और प्रयास करें, और दूसरा, और इसी तरह जब तक आपको एक न मिल जाए," कहा राहुल संथानमऑक्सफ़ोर्ड विश्वविद्यालय में एक कंप्यूटर वैज्ञानिक और नए पेपर के सह-लेखक। "क्योंकि कई अभाज्य संख्याएं हैं, यह एल्गोरिदम आपको अपेक्षाकृत कम संख्या में पुनरावृत्तियों के बाद कुछ ऐसी संख्या देगा जो उच्च संभावना के साथ अभाज्य है।" लेकिन यादृच्छिकता का उपयोग करने का मतलब है कि आपको हर बार एक अलग संख्या मिलेगी, उन्होंने कहा। यदि आपको निरंतरता की आवश्यकता है तो यह एक समस्या हो सकती है - यदि, मान लीजिए, आप सुरक्षा की एक क्रिप्टोग्राफ़िक पद्धति को नियोजित कर रहे हैं जो बड़े प्राइम की उपलब्धता पर निर्भर करती है।

दूसरा दृष्टिकोण एक नियतात्मक एल्गोरिदम के साथ जाना है। आप प्रारंभिक बिंदु चुन सकते हैं और प्रारंभिकता के लिए क्रमिक रूप से संख्याओं का परीक्षण शुरू कर सकते हैं। आख़िरकार आपकी नियति एक ढूंढने की है, और आपका एल्गोरिदम लगातार आपके द्वारा खोजे गए पहले को आउटपुट करेगा। लेकिन इसमें कुछ समय लग सकता है: यदि आप 1,000 अंकों वाली एक अभाज्य संख्या की तलाश कर रहे हैं, तो 2 वाली गणना भी।⁵⁰⁰ चरण - जिसमें ब्रह्मांड की आयु से अधिक समय लगेगा - सफलता की गारंटी के लिए पर्याप्त नहीं है।

2009 में, गणितज्ञ और फील्ड्स पदक विजेता टेरेंस ताओ बेहतर करना चाहते थे। उन्होंने गणितज्ञों को कम्प्यूटेशनल समय सीमा के भीतर किसी दिए गए आकार का अभाज्य खोजने के लिए एक नियतात्मक एल्गोरिदम के साथ आने की चुनौती दी।

उस समय सीमा को बहुपद समय के नाम से जाना जाता है। एक एल्गोरिथ्म बहुपद समय में एक समस्या का समाधान करता है यदि उसके द्वारा उठाए गए चरणों की संख्या बहुपद फ़ंक्शन से अधिक नहीं है n, इनपुट का आकार। (एक बहुपद फलन में ऐसे पद शामिल होते हैं जिनमें चर को सकारात्मक पूर्णांक घातों तक बढ़ा दिया जाता है, जैसे n² या 4n³.) अभाज्य संख्या निर्माण के संदर्भ में, n प्राइम में आपके इच्छित अंकों की संख्या को संदर्भित करता है। कम्प्यूटेशनल रूप से कहें तो, इसकी लागत अधिक नहीं है: कंप्यूटर वैज्ञानिक उन समस्याओं का वर्णन करते हैं जिन्हें बहुपद समय में एल्गोरिदम द्वारा हल किया जा सकता है। इसके विपरीत, एक कठिन समस्या में घातांकीय समय लगता है, जिसका अर्थ है कि इसमें घातीय फलन द्वारा अनुमानित कई चरणों की आवश्यकता होती है (जिसमें 2 जैसे पद शामिल होते हैं)ⁿ).

दशकों से, शोधकर्ताओं ने यादृच्छिकता और कठोरता के बीच संबंध की जांच की है। यदि आप यादृच्छिकता की अनुमति देते हैं तो अभाज्य संख्या निर्माण समस्या को आसान माना जाता है - और हर बार एक अलग संख्या प्राप्त करने से संतुष्ट होते हैं - और यदि आप नियतिवाद पर जोर देते हैं तो कठिन माना जाता है।

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

शोधकर्ता तब से छद्म नियतिवादी एल्गोरिदम की खोज कर रहे हैं। 2017 में, वारविक विश्वविद्यालय के संथानम और इगोर ओलिवेरा (जिन्होंने नए काम में भी योगदान दिया) वर्णित अभाज्य संख्याओं के निर्माण के लिए एक छद्म नियतिवादी दृष्टिकोण जो यादृच्छिकता का उपयोग करता था और निश्चित रूप से नियतात्मक दिखता था, लेकिन यह "उपघातांकीय" समय में काम करता था - घातीय से तेज़, लेकिन बहुपद समय से धीमा। फिर 2021 में बताएं और लिजी चेनकैलिफोर्निया विश्वविद्यालय, बर्कले में एक कंप्यूटर वैज्ञानिक, पता लगाया छद्म यादृच्छिक संख्या जनरेटर (एक एल्गोरिदम जो यादृच्छिक आउटपुट से अप्रभेद्य संख्याओं की एक स्ट्रिंग उत्पन्न करता है) बनाने के लिए एक कठिन समस्या का उपयोग कैसे करें। "[हमने] कठोरता और छद्म यादृच्छिकता के बीच एक नया संबंध पाया," चेन ने कहा।

आख़िरकार टुकड़े 2023 के वसंत में एक साथ आए कम्प्यूटेशनल जटिलता पर एक बूटकैंप बर्कले में कंप्यूटिंग के सिद्धांत के लिए सिमंस इंस्टीट्यूट में, जब शोधकर्ताओं ने पिछले परिणामों को एक साथ जोड़ते हुए समस्या पर एक साथ काम करना शुरू किया। चेन ने कहा, नए काम के लिए, ऑक्सफोर्ड के एक कंप्यूटर वैज्ञानिक और सह-लेखक हैनलिन रेन के पास चेन-टेल परिणाम को संथानम-ओलिवेरा दृष्टिकोण के साथ एक नए तरीके से संयोजित करने के शुरुआती विचार थे। फिर पूरी टीम ने नया पेपर तैयार करने के लिए विचारों को पूरी तरह से विकसित किया।

संथानम ने कहा, परिणामी छद्म नियतिवादी एल्गोरिदम ने बहुपद समय में अभाज्य संख्याएँ उत्पन्न करने के लिए पिछले काम को देखने के नए तरीकों का इस्तेमाल किया। इसने एक विशिष्ट लंबाई की अभाज्य संख्या को आउटपुट करने के लिए यादृच्छिकता का उपयोग किया है, और यह उपकरण यादृच्छिक अनुमान लगाने की तुलना में अधिक सटीक है और नियतात्मक क्रंचिंग की तुलना में अधिक कम्प्यूटेशनल रूप से कुशल है।

संथानम ने कहा, नया एल्गोरिदम भी उल्लेखनीय रूप से सरल है, और इसे खोज समस्याओं की एक विस्तृत श्रृंखला पर लागू किया जा सकता है - वास्तव में, संख्याओं के किसी भी घने उपसमूह, जैसे अभाज्य संख्या, जिसके लिए सदस्यता बहुपद समय में निर्धारित की जा सकती है। लेकिन यह पूर्ण नहीं है. एल्गोरिदम अनंत इनपुट लंबाई के लिए काम करता है, लेकिन यह अंकों की सभी लंबाई को कवर नहीं करता है। के कुछ मूल्य अभी भी हो सकते हैं n वहाँ जिसके लिए एल्गोरिथ्म निश्चित रूप से एक अभाज्य उत्पन्न नहीं करता है।

ग्रॉसमैन ने कहा, "उस छोटी चेतावनी से छुटकारा पाना अच्छा होगा।"

संथानम ने कहा, अंतिम लक्ष्य एक ऐसा एल्गोरिदम ढूंढना है जिसमें यादृच्छिकता की बिल्कुल भी आवश्यकता न हो। लेकिन वह तलाश अभी भी खुली हुई है. "नियतिवाद वह है जिसका हम उपयोग करना चाहेंगे," उन्होंने कहा।

लेकिन उन्होंने यह भी बताया कि छद्म यादृच्छिक प्रक्रियाएं शक्तिशाली उपकरण हैं, और अभाज्य संख्याओं के निर्माण जैसी परियोजनाएं गणित, कंप्यूटर विज्ञान, सूचना सिद्धांत और अन्य क्षेत्रों से विचारों को जोड़ने के लिए उनका उपयोग करने का एक तरीका है।

टेल ने कहा, "यह कोशिश करना और सोचना रोमांचक है कि ये शानदार अवलोकन और कहां ले जाएंगे।"