Ours go to 211: Euler pseudoprimes to 47 prime bases (from Carmichael numbers)

यहाँ शोध पत्र "OURS GOES TO 211: EULER PSEUDOPRIMES TO 47 PRIME BASES" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र उन यूलर छद्म-अभाज्य संख्याओं (Euler pseudoprimes) के निर्माण की चुनौती को संबोधित करता है जो कई क्रमिक अभाज्य आधारों (consecutive prime bases) के लिए सोलोवे-स्ट्रैसन प्राइमलिटी टेस्ट (Solovay-Strassen primality test) में जीवित रहती हैं।

• संदर्भ: पब्लिक-की क्रिप्टोसिस्टम (जैसे RSA) बड़े अभाज्य संख्याओं को उत्पन्न करने पर निर्भर करते हैं। चूंकि नियतात्मक (deterministic) प्राइमलिटी परीक्षण गणनात्मक रूप से महंगे होते हैं, इसलिए सोलोवे-स्ट्रैसन या मिलर-रबिन जैसे संभाव्यता आधारित (probabilistic) परीक्षणों का उपयोग किया जाता है।
• खतरा: यदि कोई हमलावर एक ऐसी भाज्य संख्या (pseudoprime) उपलब्ध करा सकता है जो कई आधारों के लिए इन परीक्षणों को पास कर लेती है, तो वे सिस्टम से समझौता कर सकते हैं।
• लक्ष्य: लेखकों का लक्ष्य ऐसी भाज्य संख्याएँ $n$ खोजना है जो 2 से शुरू होने वाले अधिकतम संभव क्रमिक अभाज्य आधारों के लिए यूलर मानदंड $\left(\frac{a}{n}\right) \equiv a^{(n-1)/2} \pmod n$ को संतुष्ट करती हों।
• तुलना: जबकि मिलर-रबिन में प्रति आधार विफलता की संभावना अधिकतम $1/4$ होती है, सोलोवे-स्ट्रैसन में यह अधिकतम $1/2$ होती है। लेखक यह सीमा बढ़ाना चाहते हैं कि एक भाज्य संख्या सोलोवे-स्ट्रैसन परीक्षण में कितने आधारों को "धोखा" दे सकती है।

2. कार्यप्रणाली (Methodology)

लेखक सैद्धांतिक वर्गीकरण, फ़िल्टरिंग और पुनरावृत्त गुणन (iterative multiplication) को संयोजित करने वाला एक बहु-चरणीय दृष्टिकोण अपनाते हैं।

A. कारमाइकल संख्याओं का वर्गीकरण (Classification of Carmichael Numbers)

लेखक कारमाइकल संख्याओं (Carmichael numbers) को यूलर छद्म-अभाज्य संख्याओं के प्राथमिक उम्मीदवारों के रूप में पहचानते क्योंकि वे $n$ के सह-अभाज्य (coprime) सभी आधारों के लिए फर्माट छद्म-अभाज्य (Fermat pseudoprimes) होते हैं। वे कारमाइकल लैम्ब्डा फलन $\lambda(n)$ और इंडेक्स $i(n) = (n-1)/\lambda(n)$ के आधार पर एक वर्गीकरण प्रणाली पेश करते हैं:

• वर्ग A (Class A): $i(n)$ सम (even) है। इन संख्याओं में अधिकतम संभव यूलर लायर्स (liars) ($\frac{1}{2}\phi(n)$) होते हैं। सभी लायर्स का जैकोबी प्रतीक (Jacobi symbol) $+1$ होता है।
• वर्ग B (Class B): $i(n)$ विषम (odd) है। इन्हें अभाज्य कारकों के 2-एडिक मूल्यांकन (2-adic valuation) के आधार पर B1 और B2 में उप-विभाजित किया गया है। वर्ग B में आम तौर पर वर्ग A की तुलना में कम यूलर लायर्स होते हैं।
• मुख्य अंतर्दृष्टि: जीवित रहने वाले आधारों की संख्या को अधिकतम करने के लिए, लेखक लगभग विशेष रूप से वर्ग A की कारमाइकल संख्याओं पर ध्यान केंद्रित करते हैं।

B. गुणन रणनीति (The Multiplication Strategy)

मुख्य एल्गोरिदम जैकोबी प्रतीक के गुणधर्मों (multiplicative property) पर आधारित है।

• परमाणु छद्म-अभाज्य (Atomic Pseudoprimes): लेखक "परमाणु" कारमाइकल संख्याओं (वे जो अन्य कारमाइकल संख्याओं के गुणनफल से नहीं बनी हैं) से शुरुआत करते हैं जो एक निश्चित आधार $a$ (विशेष रूप से $a \ge 37$) तक जीवित रहती हैं और जिनके छोटे अभाज्य गुणनखंड नहीं होते (सबसे छोटा गुणनखंड $> 150$)।
• पुनरावृत्त निर्माण (Iterative Construction): वे दो मौजूदा यूलर छद्म-अभाज्य संख्याओं $n_1$ और $n_2$ को गुणा करके एक बड़ी भाज्य संख्या $n = n_1 n_2$ बनाते हैं।
• "समान आधार" ह्यूरिस्टिक (The "Same Base" Heuristic): लेखक सिद्ध करते हैं (लेम्मा 13) कि यदि $n_1$ और $n_2$ दोनों वर्ग A में हैं और एक ही अभाज्य आधार $a$ तक जीवित रहते हैं, तो उनका गुणनफल $n$ (यदि वह वर्ग A में कारमाइकल संख्या बना रहता है) स्वतः ही अगले अभाज्य आधार $b$ तक जीवित रहेगा।
  • तर्क: आधार $\le a$ के लिए, $n_1$ और $n_2$ दोनों का जैकोबी प्रतीक $+1$ है, इसलिए गुणनफल $+1$ है। अगले आधार $b$ के लिए, $n_1$ और $n_2$ दोनों का जैकोबी प्रतीक $-1$है (चूंकि वे व्यक्तिगत रूप से$b$पर विफल हो जाते हैं), इसलिए गुणनफल$(-1) \times (-1) = +1$ है, जिससे भाज्य संख्या पास हो जाती है।
• फ़िल्टरिंग (Filtering): दक्षता और शुद्धता सुनिश्चित करने के लिए, एल्गोरिदम निम्नलिखित की जाँच करता है:
  1. दोनों कारक वर्ग A में हों।
  2. गुणनफल यह सुनिश्चित करे कि वह वर्ग A में बना रहे ( $n-1$ और $\lambda(n)$ के 2-एडिक मूल्यांकन के आधार पर)।
  3. गुणनफल वर्ग-मुक्त (square-free) हो (कारमाइकल संख्याओं के लिए एक आवश्यकता)।
  4. सबसे छोटा अभाज्य गुणनखंड पर्याप्त बड़ा हो ताकि छोटे आधारों पर तत्काल विफलता से बचा जा सके।

C. एल्गोरिदम कार्यान्वयन (Algorithm Implementation)

लेखकों ने एल्गोरिदम 1 विकसित किया, जो:

1. दो इनपुट $epsp_{N_1}(a)$ और $epsp_{N_2}(a)$ (आधार $a$ तक जीवित रहने वाले छद्म-अभाज्य के सेट) से लेता है।
2. 2-एडिक मूल्यांकन स्थिति की जाँच करता है ताकि यह अनुमान लगाया जा सके कि क्या गुणनफल वर्ग A होगा।
3. सत्यापित करता है कि गुणनफल एक कारमाइकल संख्या है ($\lambda(n) | n-1$)।
4. नए उत्तरजीविता सीमा (survival limit) को निर्धारित करने के लिए अगले अभाज्य आधार के लिए जैकोबी प्रतीक की जाँच करता है।
5. बड़ी संख्याएँ बनाने के लिए (जैसे $epsp_4, epsp_8, epsp_{16}$) इस प्रक्रिया को दोहराता है।

3. मुख्य योगदान (Key Contributions)

1. सैद्धांतिक वर्गीकरण: कारमाइकल संख्याओं का उनके इंडेक्स की समता (parity) और 2-एडिक मूल्यांकन के आधार पर एक कठोर वर्गीकरण, जो प्रत्येक वर्ग के लिए यूलर लायर्स की सटीक संख्या प्रदान करता है। यह सिद्ध करता है कि इस विशिष्ट क्रिप्टोग्राफिक कमजोरी के लिए वर्ग A संख्याएँ सबसे उपयुक्त लक्ष्य हैं।
2. निर्माण एल्गोरिदम: मौजूदा यूलर छद्म-अ melaluiओं को गुणा करने के लिए एक तेज़, पुनरावृत्त एल्गोरिदम, जो जैकोबी प्रतीकों के "डबल नेगेटिव" गुण का लाभ उठाकर जीवित रहने वाले आधारों की सीमा को बढ़ाता है।
3. रिकॉर्ड-तोड़ परिणाम: एक ऐसा यूलर छद्म-अभाज्य संख्या बनाना जो पहले 47 अभाज्य आधारों (211 तक) तक जीवित रहती है।
4. सांख्यिकीय विश्लेषण: इन संख्याओं के वितरण पर व्यापक सांख्यिकी, जिसमें 120 के मॉड्युलो (modulo) में उनके अवशेष वर्ग (residue classes) शामिल हैं (जो $n \equiv 1 \pmod{120}$ की ओर एक मजबूत झुकाव दिखाते हैं) और $n-1$ के विभाज्यता गुण।

4. परिणाम (Results)

• रिकॉर्ड धारक: लेखकों ने 1230 बिट्स की एक भाज्य संख्या खोजी जो 2 से लेकर 211 तक के सभी अभाज्य आधारों के लिए सोलोवे-स्ट्रैसन परीक्षण में जीवित रहती है।
  • यह पहले 47 अभाज्य आधारों के अनुरूप है।
  • यह संख्या उनके एल्गोरिदम के माध्यम से निर्मित कई छोटी कारमाइकल संख्याओं का गुणनफल है।
• मध्यवर्ती रिकॉर्ड:
  • 2 परमाणु संख्याओं के उत्पादों ($epsp_2$) ने आधार 139 तक पहुँच प्राप्त की।
  • 4 परमाणु संख्याओं के उत्पादों ($epsp_4$) ने आधार 191 तक पहुँच प्राप्त की।
  • 8 परमाणु संख्याओं के उत्पादों ($epsp_8$) ने आधार 199 तक पहुँच प्राप्त की।
• विफलता विश्लेषण: लेखकों ने देखा कि जैसे-जैसे कारकों की संख्या बढ़ती है, परमाणु कारमाइकल संख्याओं में साझा अभाज्य गुणनखंडों के कारण गुणनफल के वर्ग-मुक्त (square-free) न होने की संभावना काफी बढ़ जाती है। इसने नए परमाणु इनपुट खोजे बिना और भी बड़ी संख्याएँ (जैसे $epsp_{32}$) बनाने की उनकी क्षमता को सीमित कर दिया।
• वैकल्पिक खोज: शोध पत्र संक्षिप्त में सोफी जर्मिनस छद्म-अभाज्य (Sophie Germinus pseudoprimes) ( $p$ और $2p-1$ का गुणनफल जहाँ दोनों अभाज्य हैं) को उच्च यूलर लायर्स ($\phi(n)/4$) वाली एक माध्यमिक श्रेणी के रूप में प्रस्तुत करता है, हालांकि इस अध्ययन में उन्हें वर्ग A कारमाइकल उत्पादों की तुलना में बेहतर परिणाम नहीं मिले।

5. महत्व (Significance)

• क्रिप्टोग्राफिक निहितार्थ: यह कार्य प्रदर्शित करता है कि संभाव्यता आधारित प्राइमलिटी परीक्षण, विशेष रूप से सोलोवे-स्ट्रैसन, सावधानीपूर्वक निर्मित भाज्य संख्याओं द्वारा आश्चर्यजनक रूप से कई आधारों के लिए धोखा खा सकते हैं। जबकि मिलर-रबिन (कम विफलता दर $1/4$ बनाम $1/2$ के कारण) को प्राथमिकता दी जाती है, यह शोध प्रतिकूल परिस्थितियों में संभाव्यता परीक्षणों की सैद्धांतिक सीमाओं को उजागर करता है।
• एल्गोरिदम दक्षता: शोध पत्र कुशलतापूर्वक "कठिन" छद्म-अभाज्य उत्पन्न करने के लिए एक ब्लूप्रिंट प्रदान करता है। मौजूदा छद्म-अभाज्य को गुणा करने की रणनीति, जो एक ही आधार पर विफल होती हैं, जीवित रहने वाले आधारों की सीमा बढ़ाने के लिए एक शक्तिशाली ह्यूरिस्टिक है।
• गणितीय अंतर्दृष्टि: उनके इंडेक्स की समता और 2-एडिक मूल्यांकन द्वारा कारमाइकल संख्याओं का वर्गीकरण यूलर लायर्स के वितरण के बारे में नई संरचनात्मक अंतर्दृष्टि प्रदान करता है, जो पुष्टि करता है कि वर्ग A संख्याएँ इस विशिष्ट क्रिप्टोग्राफिक कमजोरी के लिए "सर्वश्रेष्ठ" उम्मीदवार हैं।

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