🔢 mathematics

U-Bit Collapse in Arnault Composites:Probing the Boundary of Strong Lucas Pseudoprimes

यह शोधपत्र एक कम्प्यूटेशनल अध्ययन प्रस्तुत करता है जो यह प्रदर्शित करता है कि आधार 11 तक के सभी मिलर-रबिन परीक्षणों को उत्तीर्ण करने के लिए विशेष रूप से इंजीनियर किए गए संयुक्त पूर्णांक (composite integers), नगण्य अनुक्रम अपभ्रंश (sequence degeneracy) के साथ निरंतर स्ट्रॉन्ग लुकास संभाव्य अभाज्य परीक्षण (strong Lucas probable prime test) में विफल हो जाते हैं, जिससे इन दो प्रमाणिकता परीक्षण घटकों की सांख्यिकीय स्वतंत्रता का अनुभवजन्य प्रमाण मिलता है और बेली-पीएसडब्ल्यू (Baillie-PSW) प्रकार के परीक्षणों की सुदृढ़ता को समर्थन मिलता है।

मूल लेखक: Bowman Hall

प्रकाशित 2026-01-28

📖 4 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Bowman Hall

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक बहुत ही विशिष्ट क्लब के सुरक्षा गार्ड हैं। अंदर जाने के लिए, आपको दो अलग-अलग प्रकार के आईडी (ID) परीक्षणों से गुजरना होगा।

मिलर-राबिन चेक (The Miller-Rabin Check): यह एक मानक आईडी स्कैन की तरह है। यह तेज़ है और अधिकांश नकली आईडी को पकड़ लेता है।
लुकास चेक (The Lucas Check): यह एक बहुत कठिन, अधिक जटिल परीक्षण है। यह उन सूक्ष्म विवरणों को देखता है जिन्हें पहला परीक्षण मिस कर देता है।

दशकों से, गणितज्ञ एक ऐसा "नकली आईडी" (एक भाज्य संख्या/composite number) बनाने की कोशिश कर रहे हैं जो इतनी चतुराई से डिज़ाइन किया गया हो कि वह दोनों चेकों को धोखा दे सके। अब तक, कोई सफल नहीं हुआ है। "बेली-पीएसडब्ल्यू" (Baillie-PSW) परीक्षण, जो इन दोनों चेकों को जोड़ता है, को कभी चकमा नहीं दिया जा सका है।

प्रयोग: परम नकली आईडी बनाना

इस शोध पत्र में, लेखक बोमन हॉल (Bowman Hall) ने एक गणितज्ञ अरनॉट (Arnault) द्वारा बनाए गए एक विशिष्ट ब्लूप्रिंट का उपयोग करके इन सुपर-चतुर नकली आईडी को बनाने की कोशिश की।

इस ब्लूप्रिंट को अरनॉट की एक फैक्ट्री मशीन की तरह समझें जो संख्याओं को तेज़ी से तैयार करती है। लेखक ने इस मशीन को बहुत तेज़ गति से चलाया, जिससे हजारों संख्याएँ उत्पन्न हुईं।

लक्ष्य: ऐसी संख्याएँ बनाना जो पहले चेक (मिलर-राबिन) को धोखा देने में इतनी अच्छी हों कि वे बहुत सख्त सेटिंग्स (बेस 11 तक) के साथ परीक्षण किए जाने पर भी पास हो सकें।
परिणाम: मशीन इस काम में बहुत अच्छी थी। हजारों संख्याओं में से, इसे प्रति घंटा लगभग 20 ऐसी संख्याएँ मिलीं जिन्होंने सफलतापूर्वक पहले चेक को धोखा दिया।

बड़ी खोज: "यू-बिट कोलैप्स" (The U-Bit Collapse)

जब लेखक के पास इन 200 "सुपर-फेक" संख्याओं का संग्रह हो गया, तो उन्होंने इन्हें दूसरे, अधिक कठिन चेक: स्ट्रॉन्ग लुकास टेस्ट (Strong Lucas Test) के अधीन किया।

उन्होंने यह मापने का एक नया तरीका पेश किया कि ये संख्याएँ लुकास टेस्ट को पास करने के कितने करीब पहुँचीं। उन्होंने इसे "यू-बिट कोलैप्स" (U-bit Collapse) कहा।

रूपक (Metaphor): कल्पना कीजिए कि लुकास टेस्ट उम्मीद करता है कि संख्या एक विशाल, पूर्ण आकार के पत्थर (लगभग 350 बिट्स का डेटा) की तरह हो। यदि कोई नकली आईडी वास्तव में अच्छी है, तो उसे उस पत्थर को लगभग शून्य तक सिकोड़ देना चाहिए (जिससे परीक्षण विफल हो जाए)।
मापन: लेखक ने मापा कि "पत्थर" कितना सिकुड़ा।
- उन्होंने क्या उम्मीद की थी: एक बड़ा संकुचन (लगभग 350 बिट्स का कोलैप्स), जिसका अर्थ होता कि नकली आईडी पास हो गई है।
- उन्होंने क्या पाया: पत्थर बहुत कम सिकुड़ा।
  - औसतन, संकुचन केवल 1.6 बिट्स था।
  - देखा गया सबसे बड़ा संकुचन 8 बिट्स था।
  - 26% संख्याएँ बिल्कुल नहीं सिकुड़ीं। वे बिल्कुल सामान्य, ईमानदार संख्याओं की तरह दिखीं।

इसका क्या अर्थ है

लेखक निष्कर्ष निकालते हैं कि "अरनॉट ब्लूप्रिंट" ऐसी संख्याएँ बनाने में उत्कृष्ट है जो पहले चेक को पास होने जैसा दिखाती हैं, लेकिन दूसरे चेक को पास करने में यह पूरी तरह से बेकार है।

उपमा: यह एक जालसाज की तरह है जो ड्राइवर लाइसेंस के फ़ॉन्ट और स्याही की नकल करने में माहिर है (पहला चेक पास करना), लेकिन होलोग्राम या सूक्ष्म प्रिंट (दूसरा चेक) की नकल करने में पूरी तरह विफल रहता है। वे कितनी भी कोशिश क्यों न करें, होलोग्राम हमेशा नकली ही दिखता है।
"ऑर्थोगोनैलिटी" (Orthogonality): लेखक इस शब्द का उपयोग यह कहने के लिए करते हैं कि दोनों परीक्षण दो अलग-अलग आयामों (dimensions) की तरह हैं। एक में अच्छा होना आपको दूसरे में बिल्कुल भी मदद नहीं करता है। वे पूरी तरह से अलग नियमों पर काम करते हैं।

निचोड़ (The Bottom Line)

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

यह हमें इस बात का गहरा विश्वास देता है कि संयुक्त सुरक्षा प्रणाली (Baillie-PSW) अभी भी अटूट है। पहले भाग के परीक्षण को धोखा देने के लिए उपयोग किए जाने वाले विशिष्ट तरीके आपको दूसरे भाग को धोखा देने के करीब भी नहीं ले जाते हैं। इस प्रणाली को तोड़ने के लिए, आपको एक पूरी तरह से अलग तरह के तरीके की आवश्यकता होगी, जिसे हमने अभी तक खोजा नहीं है।

तकनीकी सारांश: अर्नाल्ट कंपोजिट्स में U-बिट कोलैप्स (U-Bit Collapse)

समस्या विवरण
बेली-पीएसडब्ल्यू (Baillie–PSW) प्राइमैलिटी टेस्ट, जो मिलर-रबिन टेस्ट को एक स्ट्रॉन्ग लुकास प्रोबेबल प्राइम टेस्ट के साथ जोड़ता है, का 1980 से व्यापक खोजों के बावजूद कोई ज्ञात कंपोजिट काउंटरएग्जांपल (composite counterexample) नहीं मिला है। जबकि एफ. अर्नाल्ट ने विशिष्ट अभाज्य गुणनखंडन (prime factorizations) को इंजीनियर करके (कारमाइकल संख्याएं) कई मिलर-रबिन टेस्ट्स को पास करने वाले भाज्य पूर्णांकों (composite integers) को निर्मित करने के लिए रूपरेखा विकसित की है, यह एक खुला प्रश्न बना हुआ है कि क्या इन निर्माणों को लुकास घटक (Lucas component) से बचने के लिए विस्तारित किया जा सकता है। यह शोध पत्र जांच करता है कि क्या अर्नाल्ट-प्रकार के कंपोजिट्स, विशेष रूप से वे जो बेस 11 तक मिलर-रबिन टेस्ट पास करने के लिए इंजीनियर किए गए हैं, लुकास अनुक्रम (Lucas sequence) में कोई मापने योग्य "डीजेनेरेसी" (degeneracy) प्रदर्शित करते हैं जो बाबेली-पीएसडब्ल्यू स्यूडोप्राइम (Baillie–PSW pseudoprime) के निर्माण की ओर संकेत दे सके।

कार्यप्रणाली
अध्ययन ने लगभग 350 बिट्स के कंपोजिट पूर्णांक $n = p_1 p_2 p_3$ उत्पन्न करने के लिए एक हाई-थ्रूपुट निर्माण प्रक्रिया का उपयोग किया। यह निर्माण अर्नाल्ट फ्रेमवर्क का पालन करता था, यह सुनिश्चित करते हुए कि अभाज्य गुणनखंड $p_i$ ऐसी स्थितियों को पूरा करते हैं जहाँ $p_i - 1$ एक बड़े सामान्य कारक $f$ को साझा करता है, जिससे कंपोजिट बेस 11 तक के मिलर-रबिन टेस्ट पास कर सके।

उत्पादन पैमाना: यह प्रक्रिया एक सिंगल-कोर ARM इंस्टेंस पर चली, जिसने प्रति मिनट लगभग 7,700 कारमाइकल संख्याएं उत्पन्न कीं।
चयन मानदंड: इस स्ट्रीम से, उन कंपोजिट्स को अलग किया गया जो बेस 11 तक के सभी मिलर-रबिन टेस्ट पास करते थे, जिसकी प्राप्ति दर लगभग 0.015% (लगभग 20 प्रति घंटा) थी।
डेटासेट: विस्तृत विश्लेषण के लिए कुल 200 ऐसे कंपोजिट्स एकत्र किए गए।
परीक्षण: प्रत्येक कंपोजिट का मानक डिस्क्रिमिनेन्ट्स $D$ (ऐसे $D$ चुने गए जहाँ $(D/n) = -1$ ) का उपयोग करके स्ट्रॉन्ग लुकास प्रोबेबल प्राइम टेस्ट के अधीन परीक्षण किया गया।
मीट्रिक: लेखकों ने U-बिट कोलैप्स मीट्रिक पेश किया, जिसे $\delta = \log_2 n - \log_2(U_d \mod n)$ के रूप में परिभाषित किया गया है, जहाँ $n+1 = d \cdot 2^s$ । यह मीट्रिक $[0, n)$ में $U_d$ के यूनिफॉर्म डिस्ट्रीब्यूशन से विचलन को मापता है। एक महत्वपूर्ण कोलैप्स (बड़ा $\delta$ ) यह संकेत देगा कि लुकास टर्म असामान्य रूप से छोटा है, जो एक स्ट्रॉन्ग लुकास स्यूडोप्राइम के लिए आवश्यक स्थिति है।

प्रमुख परिणाम
200-सैंपल डेटासेट के विश्लेषण से निम्नलिखित निष्कर्ष प्राप्त हुए:

लुकास टेस्ट को विफल करने में असमर्थता: सभी 200 कंपोजिट्स स्ट्रॉन्ग लुकास टेस्ट में विफल रहे; कोई भी स्ट्रॉन्ग लुकास स्यूडोप्राइम नहीं पाया गया।
नगण्य U-बिट कोलैप्स: देखे गए कोलैप्स मान एक वास्तविक स्यूडोप्राइम के लिए आवश्यक $\approx 350$ $\approx 350$ बिट्स की तुलना में बहुत कम थे।
- औसत $\delta$ : 1.61 बिट्स।
- मीडियन $\delta$ : 1.0 बिट्स।
- अधिकतम $\delta$ : 8 बिट्स (एक 344-बिट कंपोजिट में देखा गया, जो 336 बिट्स तक की कमी को दर्शाता है)।
- जीरो कोलैप्स: 26% नमूने (52 कंपोजिट्स) ने कोई मापने योग्य कोलैप्स नहीं दिखाया ( $\delta = 0$ ), जिसका अर्थ है कि उनके $U_d \mod n$ मान $[0, n)$ में रैंडम तत्वों से सांख्यिकीय रूप से अविभेदनीय थे।
पैरामीटर्स की स्वतंत्रता: सहसंबंध विश्लेषण (Correlation analysis) ने अर्नाल्ट निर्माण पैरामीटर्स ( $k, M$ ) या कंपोजिट बिट-साइज के साथ U-बिट कोलैप्स के बीच नगण्य संबंध प्रकट किया ( $|\rho| < 0.09$ )।
रेसिड्यू पैटर्न (Residue Patterns): हालांकि 35 के मॉड्युलो (modulo 35) में कुछ रेसिड्यू क्लासेस (जैसे 2, 8, 18, 22, 23, 32) अभाज्य गुणनखंडों के बीच बार-बार दिखाई दिए, लेकिन कोई भी एकल पैटर्न डेटासेट पर हावी नहीं था, और ये पैटर्न लुकास रेजिस्टेंस (Lucas resistance) के साथ सह-संबंधित नहीं थे।

महत्व और दावे
यह शोध पत्र निष्कर्ष निकालता है कि बेस 11 तक मिलर-रबिन टेस्ट से बचने के लिए सक्षम बीजगणितीय स्थितियां (algebraic conditions) लुकास टेस्ट से बचने के लिए कोई सार्थक प्रगति प्रदान नहीं करती हैं। लेखक तर्क देते हैं कि मिलर-रबिन और लुकास टेस्ट के दोनों घटक मौलिक रूप से स्वतंत्र बीजगणितीय संरचनाओं को लक्षित करते हैं।

ऑर्थोगोनैलिटी (Orthogonality): परिणाम मिलर-रबिन और लुकास टेस्ट की ऑर्थोगोनैलिटी के लिए मजबूत अनुभवजन्य साक्ष्य प्रदान करते हैं। मिलर-रबिन टेस्ट को तोड़ने के लिए उपयोग किए गए निर्माण विधियों द्वारा लुकास टेस्ट को तोड़ने के लिए आवश्यक 'कोलैप्स' उत्पन्न नहीं होता है।
Baillie–PSW की मजबूती: लुकास टेस्ट को चकमा देने के लिए आवश्यक U-बिट कोलैप्स की अनुपस्थिति, यहाँ तक कि उन कंपोजिट्स के मामले में भी जिन्हें विशेष रूप से मिलर-रबिन को रोकने के लिए इंजीनियर किया गया था, Baillie–PSW टेस्ट की निरंतर विश्वसनीयता को पुष्ट करती है।
निर्माण निहितार्थ: अध्ययन यह सुझाव देता है कि एक Baillie–PSW स्यूडोप्राइम का निर्माण करने के लिए मानक कारमाइकल या अर्नाल्ट निर्माणों में पाए जाने वाले गुणों की तुलना में गुणात्मक रूप से भिन्न बीजगणितीय बाधाओं (algebraic constraints) को संतुष्ट करने की आवश्यकता होगी। शोध पत्र का मानना है कि देखा गया न्यूनतम कोलैप्स वर्तमान निर्माण प्रतिमान (construction paradigm) की मौलिक सीमाओं को दर्शाता है, न कि गणनात्मक प्रयास की कमी को।

निष्कर्ष
यह कम्प्यूटेशनल अध्ययन स्थापित करता है कि अर्नाल्ट फ्रेमवर्क, हालांकि मिलर-रबिन स्यूडोप्राइम्स उत्पन्न करने में प्रभावी है, फिर भी Baillie–PSW टेस्ट को चुनौती देने के लिए आवश्यक लुकास अनुक्रम डीजेनेरेसी (Lucas sequence degeneracy) उत्पन्न करने में विफल रहता है। U-बिट कोलैप्स मीट्रिक का परिचय भविष्य के अन्वेषणों के लिए एक मात्रात्मक ढांचा प्रदान करता है, हालांकि डेटा यह सुझाव देता है कि Baillie–PSW काउंटरएग्जांपल खोजने के लिए अर्नाल्ट प्रतिमान से परे वैकल्पिक निर्माण विधियों की आवश्यकता हो सकती है।

प्रयोग: परम नकली आईडी बनाना

बड़ी खोज: "यू-बिट कोलैप्स" (The U-Bit Collapse)

इसका क्या अर्थ है

निचोड़ (The Bottom Line)

इसी तरह के और पेपर