🔢 mathematics

Binary Caps and LCD Codes with Large Dimensions

यह शोध पत्र LCD कोड और प्रोजेक्टिव स्पेस में कैप्स के बीच एक संबंध स्थापित करता है ताकि न्यूनतम दूरी 4 या उससे अधिक वाले LCD कोड्स के लिए गणना-मुक्त अस्तित्वहीनता प्रमेय (nonexistence theorems) प्राप्त किए जा सकें, जिससे पहली बार को-डायमेंशन 7 और 8 के लिए इष्टतम न्यूनतम दूरियों का निर्धारण किया जा सके।

मूल लेखक: Keita Ishizuka, Yuhi Kamio

प्रकाशित 2026-04-07

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

CC BY 4.0

मूल लेखक: Keita Ishizuka, Yuhi Kamio

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

एक बड़ी तस्वीर: अटूट डिजिटल ताले बनाना

कल्पना कीजिए कि आप एक मास्टर लॉकस्मिथ (ताले बनाने वाले) हैं जो सबसे सुरक्षित डिजिटल तिजोरियाँ बनाने की कोशिश कर रहे हैं। कंप्यूटर विज्ञान की दुनिया में, इन "तिजोरियों" को कोड (codes) कहा जाता है। विशेष रूप से, यह शोध पत्र एक विशेष प्रकार के कोड के बारे में है जिसे एलसीडी कोड (LCD code - Linear Complementary Dual) कहा जाता है।

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

शोधकर्ताओं (इशिज़ुका और कामियो) का लक्ष्य एक सरल प्रश्न का उत्तर देना था: "हम इन तिजोरियों में वैध संदेशों को एक-दूसरे से कितनी दूर रख सकते हैं ताकि यदि शोर (noise) के कारण कुछ अक्षर बिगड़ भी जाएं, तो भी हम उन्हें ठीक कर सकें?" इस दूरी को न्यूनतम दूरी (minimum distance) कहा जाता है। दूरी जितनी अधिक होगी, तिजोरी उतनी ही मजबूत होगी।

समस्या: "एग्जॉस्टिव सर्च" (Exhaustive Search) की बाधा

लंबे समय तक, गणितज्ञों को छोटे आकारों के लिए ये मजबूत तिजोरियाँ बनाना पता था। लेकिन जैसे-जैसे तिजोरियाँ बड़ी होती गईं (विशेष रूप से, जब "को-डायमेंशन" या अतिरिक्त सुरक्षा स्थान 6, 7, या 8 तक बढ़ गया), यह समस्या एक दुःस्वप्न बन गई।

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

को-डायमेंशन 6 के लिए, उन्होंने एक अजीब पैटर्न देखा: कभी एक मजबूत तिजोरी संभव थी, तो कभी नहीं, यह इस पर निर्भर करता था कि आकार विषम (odd) था या सम (even)।
लेकिन वे बिना भारी और धीमे कंप्यूटर खोजों के यह सिद्ध नहीं कर सके कि यह पैटर्न क्यों मौजूद था।
को-डायमेंशन 7 और 8 के लिए, घास का ढेर इतना बड़ा था कि कंप्यूटरों ने काम पूरा ही नहीं कर सका। उत्तर अज्ञात थे।

नया दृष्टिकोण: ज्यामिति (Geometry) और "कैप्स" (Caps)

लेखकों ने घास के ढेर को गिनना बंद करने और घास के आकार को देखना शुरू कर दिया। उन्होंने महसूस किया कि इन कोड्स को बनाना वास्तव में एक विशेष प्रकार के ज्यामितीय स्थान (जिसे प्रोजेक्टिव स्पेस कहा जाता है) में बिंदुओं को व्यवस्थित करने के समान है।

यहाँ उपमा (analogy) दी गई है:

कोड: बिंदुओं का एक संग्रह।
नियम: कोई भी तीन बिंदु कभी भी एक सीधी रेखा में नहीं हो सकते।
आकार: ज्यामिति में, बिंदुओं का एक संग्रह जहाँ कोई भी तीन एक रेखा में नहीं होते, उसे कैप (Cap) कहा जाता है। (एक "कैप" को एक टोपी की तरह समझें जो बिंदुओं के समूह को इस तरह ढंकती है कि उनमें से कोई भी तीन एक पंक्ति में न बैठ सकें)।

शोधकर्ताओं ने एक जादुई संबंध की खोज की: एक कोड एलसीडी कोड है यदि और केवल यदि इन बिंदुओं से बना एक विशिष्ट गणितीय "संतुलन पैमाना" (जिसे ग्राम मैट्रिक्स कहा जाता है) संतुलित रहता है। यदि पैमाना संतुलित है (nonsingular), तो कोड सुरक्षित है। यदि यह झुक जाता है, तो कोड विफल हो जाता है।

बड़ी सफलता: "बिग हैट" (Big Hat) सिद्धांत

गणितज्ञों ब्रून और वेल्हौ द्वारा विकसित सबसे बड़े संभावित "कैप्स" के बारे में एक गहरे सिद्धांत का उपयोग करते हुए, लेखकों ने बिंदुओं के संग्रह के आकार के बारे में एक छिपा हुआ नियम खोजा।

उन्होंने सिद्ध किया कि यदि आप एक बहुत बड़ा, सुरक्षित एलसीडी कोड (न्यूनतम दूरी 4 या अधिक के साथ) बनाने का प्रयास करते हैं, तो बिंदुओं को एक बहुत ही विशिष्ट, कठोर आकार के भीतर फिट होना ही होगा। यह एक विशाल भीड़ को एक कमरे में फिट करने जैसा है; यदि भीड़ बहुत बड़ी है, तो उन्हें एक विशिष्ट फॉर्मेशन में खड़ा होना ही होगा, अन्यथा वे फिट ही नहीं हो पाएंगे।

इस ज्यामितीय बाधा ने दो प्रमुख खोजों को जन्म दिया:

"विषम/सम" (Odd/Even) नियम: उन्होंने गणितीय रूप से सिद्ध किया कि इन बड़े कोड्स के लिए, कोड का आकार सुरक्षा स्तर की पैरिटी (विषम/सम प्रकृति) से मेल खाना चाहिए। इसने बिना एक भी सर्च चलाए, कंप्यूटर खोजों में देखे गए बदलते पैटर्न की व्याख्या की।
आकार की सीमा: उन्होंने सिद्ध किया कि इन कोड्स के आकार पर एक सख्त सीमा है। यदि आप इन्हें इस सीमा से बड़ा बनाने का प्रयास करते हैं, तो वे अस्तित्व में ही नहीं रह सकते।

परिणाम: रहस्य को सुलझाना

इन ज्यामितीय नियमों को लागू करके, लेखकों ने तीन चीजें हासिल कीं:

गणना-मुक्त प्रमाण (Computation-Free Proof): उन्होंने सिद्ध किया कि को-डायमेंशन 6 के लिए, कुछ कोड आकार असंभव हैं। इसने धीमी, ब्रूट-फोर्स कंप्यूटर खोजों को एक साफ, तार्किक गणितीय प्रमाण से बदल दिया।
को-डायमेंशन 7 का समाधान: उन्होंने हर संभव लंबाई के लिए को-डायमेंशन 7 के आकार के कोड के लिए सर्वोत्तम सुरक्षा का पूरी तरह से मानचित्र तैयार किया। उन्होंने पाया कि "बदलते पैटर्न" कहाँ समाप्त होता है और अधिकतम सुरक्षा क्या है।
को-डायमेंशन 8 का समाधान: उन्होंने को-डायमेंशन 8 के लिए भी ऐसा ही किया, जो एक ऐसी समस्या थी जिसे पहले कंप्यूटरों के लिए बहुत कठिन माना जाता था। उन्होंने इस श्रेणी में प्रत्येक एकल कोड लंबाई के लिए सटीक अधिकतम सुरक्षा निर्धारित की।

यह क्यों मायने रखता है

इस शोध पत्र से पहले, यदि आप किसी विशिष्ट बड़े कोड के लिए सर्वोत्तम सुरक्षा जानना चाहते थे, तो आपको हफ्तों तक सुपरकंप्यूटर के चलने का इंतजार करना पड़ सकता था, या आपको बस अनुमान लगाना पड़ सकता था।

अब, इस "ज्यामितीय लेंस" की मदद से, हमारे पास एक स्पष्ट मानचित्र है। हम जानते हैं कि ये डिजिटल तिजोरियाँ कितनी बड़ी और कितनी मजबूत हो सकती हैं, और हम यह भी जानते हैं कि वे इससे बड़ी क्यों नहीं हो सकतीं। इसने लाखों संभावनाओं के एक अराजक पहेली को एक व्यवस्थित, समझने योग्य ज्यामितीय आकार में बदल दिया है।

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

यहाँ केइता इशिज़ुका और युही कामियो के शोध पत्र "Binary Caps and LCD Codes with Large Dimensions" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र सभी बाइनरी लीनियर कॉम्प्लीमेंट्री ड्यूल (LCD) $[n, k]$ कोडों के बीच सबसे बड़े न्यूनतम अंतर (minimum distance), जिसे $d^E_2(n, k)$ द्वारा दर्शाया गया है, को निर्धारित करने की मौलिक समस्या का समाधान करता है।

संदर्भ: साइड-चैनल और फॉल्ट इंजेक्शन हमलों का प्रतिरोध करने के लिए क्रिप्टोग्राफी में LCD कोड अत्यंत महत्वपूर्ण हैं। जबकि यह ज्ञात है कि $\mathbb{F}_q$ ( $q \ge 4$ ) पर कोई भी कोड एक LCD कोड के समतुल्य होता है, बाइनरी और टेनरी (ternary) LCD कोड वास्तविक संरचनात्मक बाधाएं लागू करते हैं।
विशिष्ट चुनौती: पिछले शोध ने छोटे आयामों ( $k \le 5$ ) और छोटी को-डायमेंशन ( $m = n-k \le 5$ ) के लिए $d^E_2(n, k)$ को निर्धारित किया था। हालांकि, बड़ी को-डायमेंशन ( $m \ge 6$ ) के लिए, $d \ge 4$ हेतु इष्टतम न्यूनतम अंतर निर्धारित करना एक बाधा बन गया था।
अंतराल (The Gap): मौजूदा विधियाँ Hamming कोड्स (जो कॉलम की 2-स्वतंत्रता सुनिश्चित करते हैं) पर निर्भर थीं ताकि $d \ge 3$ का विश्लेषण किया जा सके। ये विधियाँ $d \ge 4$ के लिए विफल हो जाती हैं, जिसके लिए 3-स्वतंत्रता (कोई भी तीन कॉलम रैखिक रूप से आश्रित नहीं होने चाहिए) की आवश्यकता होती है। फलस्वरूप, $m \ge 6$ के लिए $d^E_2(n, n-m)$ को निर्धारित करने के लिए पहले व्यापक कम्प्यूटेशनल खोज (exhaustive computational searches) की आवश्यकता थी, जो बड़े $n$ के लिए अव्यवहार्य है। विशेष रूप से, $d^E_2(n, n-6)$ के व्यवहार ने $n$ की समता (parity) के आधार पर एक वैकल्पिक पैटर्न दिखाया, लेकिन इसका कोई सैद्धांतिक स्पष्टीकरण नहीं था।

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

लेखक LCD कोड के बीजगणितीय गुणों और प्रोजेक्टिव स्पेस में कैप्स (caps) के ज्यामितीय गुणों के बीच एक नया संबंध स्थापित करते हैं।

ज्यामितीय अनुवाद (Geometric Translation):
- एक $[n, k, d]$ कोड जहाँ $d \ge 4$ है, वह प्रोजेक्टिव स्पेस $PG(m-1, 2) $(जहाँ$ m=n-k $) में बिंदुओं के एक सेट$ S$ के अनुरूप होता है, जहाँ कोई भी तीन बिंदु कोलीनियर (collinear) नहीं होते हैं। ऐसा सेट $S$ एक कैप (cap) कहलाता है।
- कैप $S$ द्वारा जनरेट किया गया कोड $C_S$ तब LCD होता है जब उसका संबंधित ग्राम मैट्रिक्स (Gram matrix) $U_S = \sum_{s \in S} ss^T$ $\mathbb{F}_2$ पर नॉन-सिंगुलर (invertible) होता है।
बड़े कैप्स का संरचनात्मक विश्लेषण (Structural Analysis of Large Caps):
- लेखक ब्रून (Bruen) और वेहलाउ (Wehlau) द्वारा विकसित मैक्सिमल कैप्स (maximal caps) की संरचना सिद्धांत का उपयोग करते हैं। यह सिद्धांत "पीरियड" (वेक्टरों का एक सबस्पेस $v$ जिससे $S+v = S$ ) के आधार पर बड़े कैप्स को वर्गीकृत करता है।
- वे कैप के पीरियड स्ट्रक्चर के सापेक्ष ग्राम मैट्रिक्स $U_S$ की रैंक का विश्लेषण करते हैं।
मुख्य सैद्धांतिक व्युत्पत्ति (Key Theoretical Derivation):
- वे सिद्ध करते हैं कि पर्याप्त बड़े कैप्स जिनका ग्राम मैट्रिक्स नॉन-सिंगुलर है, उन्हें एक विशिष्ट ज्यामितीय संरचना के भीतर होना चाहिए: हाइपरप्लेन का पूरक ( $\mathbb{F}_2^m \setminus \langle v \rangle^\perp$ )।
- यह ज्यामितीय बाधा कोड की लंबाई ( $n$ ) और को-डायमेंशन ( $m$ ) के सापेक्ष सख्त सीमाएं लगाती है।

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

कैप्स के माध्यम से LCD लक्षण वर्णन: यह शोध पत्र एक कैप से प्राप्त कोड के LCD होने के लिए एक आवश्यक और पर्याप्त शर्त प्रदान करता है: ग्राम मैट्रिक्स $U_S = \sum_{s \in S} ss^T$ का नॉन-सिंगुलर होना अनिवार्य है। यह एक बीजगणितीय कोडिंग समस्या को बिंदुओं के विन्यास (point configurations) के बारे में एक ज्यामितीय प्रश्न में बदल देता है।
बड़े कैप्स के लिए संरचना प्रमेय (Theorem 12): लेखक एक पर्याप्त शर्त स्थापित करते हैं जिसके तहत बड़े कैप्स हाइपरप्लेन पूरक में स्थित होते हैं। विशेष रूप से, यदि एक कैप $S$ पर्याप्त बड़ा है ( $|S| \ge 2^{m-2} + 2^{m-4} - \text{rank}(U_S) + 1$ ), तो उसे $\mathbb{F}_2^m \setminus \langle v \rangle^\perp$ का एक उपसमुच्चय होना चाहिए।
अस्तित्वहीनता प्रमेय (Theorems 13 & 17): संरचना प्रमेय और नॉन-सिंगुलैरिटी आवश्यकता को जोड़कर, वे सिद्ध करते हैं कि को-डायमेंशन $m \ge 4$ $m \geq 4$ के लिए, किसी भी LCD $[n, n-m]$ $[n, n - m]$ कोड के लिए जिसमें न्यूनतम अंतर $d \ge 4$ $d \geq 4$ है, निम्नलिखित शर्तें होनी चाहिए:
- पैरिटी बाधा (Parity Constraint): $n \equiv m \pmod 2$ (लंबाई और को-डायमेंशन की समता समान होनी चाहिए)।
- आकार की बाधा (Size Constraint): $n \le 2^{m-1} - m$ ।
कम्प्यूटेशन-मुक्त प्रमाण (Computation-Free Proofs): ये प्रमेय उन गैर-अस्तित्व परिणामों के लिए कठोर, गैर-कम्प्यूटेशनल प्रमाण प्रदान करते हैं जो पहले केवल ब्रूट-फोर्स सर्च के माध्यम से सत्यापित किए गए थे।

4. मुख्य परिणाम (Main Results)

यह ढांचा लेखकों को को-डायमेंशन $m=6, 7,$ और $8$ के लिए इष्टतम न्यूनतम अंतर को पूरी तरह से निर्धारित करने की अनुमति देता है।

को-डायमेंशन 6 ( $m=6$ ):
- यह सिद्ध करता है कि $17 \le n \le 26$ की सीमा में विषम $n$ के लिए LCD $[n, n-6, 4]$ कोड मौजूद नहीं हैं।
- यह बिना किसी व्यापक खोज के $d=3$ और $d=4$ के बीच देखे गए पूर्ववर्ती वैकल्पिक पैटर्न की व्याख्या करता है।
को-डायमेंशन 7 ( $m=7$ ):
- यह सभी $n$ के लिए $d^E_2(n, n-7)$ को पूरी तरह से निर्धारित करता है।
- परिणाम: यदि $n$ विषम है, तो $n \ge 34$ के लिए $d^E_2(n, n-7) = 4$ है, और यदि $n$ सम है, तो $d^E_2(n, n-7) = 3$ है (विशिष्ट श्रेणियों के लिए $n$ में)। बहुत बड़े $n$ के लिए, दूरी घटकर 2 हो जाती है।
को-डायमेंशन 8 ( $m=8$ ):
- यह सभी $n$ के लिए $d^E_2(n, n-8)$ को पूरी तरह से निर्धारित करता है।
- परिणाम: $n \ge 73$ के लिए, LCD कोड केवल तभी मौजूद होते हैं जब $n$ सम हो और $n \le 120$ हो। विषम $n \ge 73$ के लिए, अधिकतम दूरी 3 है। $n \ge 248$ के लिए, दूरी 2 है।

5. महत्व (Significance)

सैद्धांतिक सफलता: यह पहला सैद्धांतिक ढांचा है जो $n$ की समता (parity) के आधार पर इष्टतम LCD कोड दूरियों में "अल्टरनेटिंग पैटर्न" की व्याख्या करता है। यह क्षेत्र को कम्प्यूटेशनल गणना (enumeration) पर निर्भरता से हटाकर संरचनात्मक ज्यामितीय प्रमाणों की ओर ले जाता है।
स्केलेबिलिटी (Scalability): यह विधि इष्टतम दूरियों के निर्धारण को उन को-डायमेंशन ( $m=7, 8$ ) तक विस्तारित करती है जहाँ व्यापक खोज कम्प्यूटेशनल रूप से अव्यवहार्य थी।
सीमाएँ और भविष्य का कार्य: यह दृष्टिकोण ब्रून और वेहलाउ द्वारा बाइनरी प्रोजेक्टिव स्पेस ( $q=2$ ) में कैप्स के वर्गीकरण पर अत्यधिक निर्भर है। लेखक नोट करते हैं कि यह टेनरी ( $q=3$ ) या उच्च क्षेत्रों तक सीधे विस्तारित नहीं होता है, क्योंकि $q > 2$ के लिए बड़े कैप्स का विस्तृत वर्गीकरण अभी उपलब्ध नहीं है। गैर-बाइनरी LCD कोड के लिए ज्यामितीय ढांचे को विकसित करने और इन परिणामों को $m \ge 9$ तक विस्तारित करने के लिए भविष्य के कार्य की आवश्यकता है।

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