🔢 mathematics

Search-to-Decision Reductions for the Linear and General Code Equivalence Problems

यह शोधपत्र एक डिसीजन ऑरेकल (decision oracle) के माध्यम से परम्यूटेशन घटक को पुनः प्राप्त करके और एंगेल-श्नाइडर एल्गोरिदम का उपयोग करके डायगोनल और फील्ड ऑटोमोर्फिज्म घटकों को नियत समय (deterministic polynomial time) में निर्धारित करके, लीनियर और जनरल कोड इक्विवेलेंस समस्याओं के लिए कुशल सर्च-टू-डिसीजन रिडक्शन प्रस्तुत करता है।

मूल लेखक: Abhinaba Mazumder

प्रकाशित 2026-08-12

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

CC BY 4.0

मूल लेखक: Abhinaba Mazumder

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

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

इनमें से एक सबसे आशाजनक प्रकार के तालों का आधार एक पहेली है जिसे "कोड इक्विलेंस" (Code Equivalence) कहा जाता है। कल्पना कीजिए कि आपके पास संख्याओं के दो ग्रिड हैं। पहेली पूछती है: "क्या ये दो ग्रिड गुप्त रूप से एक ही हैं, बस उन्हें पुनर्व्यवस्थित और खींचा गया है?" आप कॉलम को शफल (shuffle) कर सकते हैं (जैसे किताबों को शेल्फ पर फिर से व्यवस्थित करना) और संख्याओं को स्ट्रेच (stretch) कर सकते हैं (जैसे फॉन्ट का आकार या रंग बदलना), लेकिन आप उस अंतर्निहित कहानी को नहीं बदल सकते जो संख्याएँ बताती हैं। यदि आप यह सिद्ध कर सकते हैं कि वे एक ही हैं, तो आपने ताला तोड़ दिया है। यदि आप नहीं कर सकते, तो रहस्य सुरक्षित रहता है। यह हमारे भविष्य के इंटरनेट को सुरक्षित करने वाले डिजिटल हस्ताक्षरों की एक नई पीढ़ी का आधार है।

लंबे समय तक, हमारी समझ में एक अंतर था। हमारे पास एक "डिसीजन" (decision) टूल था: एक जादुвई ओरेकल (oracle) जो केवल "हाँ" या "नहीं" कह सकता था कि, "क्या ये दो ग्रिड समान हैं?" लेकिन वास्तविक दुनिया में, हमें केवल हाँ/ना से अधिक की आवश्यकता है; हमें वास्तविक समाधान की आवश्यकता है। हमें यह जानना है कि किताबों को बिल्कुल कैसे पुनर्व्यवस्थित किया गया था और उन्हें कितना खींचा गया था। इसे "सर्च" (search) समस्या कहा जाता है। अब तक, हम जानते थे कि एक "हाँ/ना" उत्तर को सबसे सरल संस्करण के समाधान में कैसे बदला जाए (जहाँ आप केवल शफल कर सकते हैं), लेकिन अधिक जटिल संस्करणों (जहाँ आप संख्याओं को स्ट्रेच भी कर सकते हैं या संख्या प्रणाली के नियमों को भी बदल सकते हैं) के लिए यह एक रहस्य बना हुआ था।

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

जासूसी टूलकिट: शफलिंग और स्ट्रेचिंग

यह समझने के लिए कि पेपर कैसे काम करता है, आइए हम एक सरल उपमा का उपयोग करके पहेली के टुकड़ों को तोड़ें। कल्पना कीजिए कि आपके पास ताश की एक गड्डी है, लेकिन सूट और नंबरों के बजाय, कार्डों पर बिंदुओं के पैटर्न हैं।

पहेली: आपके पास दो डेक हैं, डेक A और डेक B। आपको संदेह है कि डेक B केवल डेक A है जिसे:

शफल (Shuffle) किया गया है: कार्डों का क्रम बदल दिया गया है।
स्ट्रेच (Stretch) किया गया है: कुछ कार्डों पर बिंदुओं को एक गुप्त संख्या से गुणा किया गया है (जैसे किसी छवि को ज़ूम इन करना)।
ट्विस्ट (Twist) किया गया है: (सबसे जटिल संस्करण में) नियम कि कैसे बिंदु आपस में क्रिया करते हैं, एक "फील्ड ऑटोमोर्फिज्म" (field automorphism) द्वारा थोड़े बदल दिए गए हैं, जो एक गुप्त नियम की तरह है जो एक विशिष्ट पैटर्न में '2' को '3' में और '3' को '2' में बदल देता है।

"डिसीजन" समस्या एक रेफरी से पूछने जैसी है: "क्या ये डेक एक ही हैं?" रेफरी केवल "हाँ" या "नहीं" कहता है।
"सर्च" समस्या पूछने जैसी है: "मुझे डेक A को डेक B में बदलने के लिए सटीक चालों की सूची दिखाएं।"

जादू का कमाल: शफल को पकड़ना

पेपर की पहली बड़ी सफलता यह पता लगाने में है कि केवल "हाँ/ना" रेफरी का उपयोग करके शफल (परम्यूटेशन) को कैसे खोजा जाए।

कल्पना कीजिए कि आप जानना चाहते हैं कि डेक A का पहला कार्ड (मान लीजिए कि वह "एース" है) डेक B में किस स्थान पर गया है। आप रेफरी से यह नहीं पूछ सकते, "क्या एース स्थिति 5 पर है?" क्योंकि रेफरी "हाँ" कह सकता है भले ही एース वास्तव में स्थिति 6 पर हो, क्योंकि डेक को मिलाने के अन्य तरीके भी हो सकते हैं।

इसलिए, लेखक "प्रोजेक्टिव क्लासेस" (Projective Classes) नामक एक चतुर ट्रिक का उपयोग करते हैं। इसे ऐसे समझें जैसे समान दिखने वाले कार्डों को अलग-अलग रंगों के साथ समूहबद्ध करना। यदि एース और किंग का बिंदुओं का पैटर्न एक जैसा है (बस आकार अलग है), तो वे एक ही "क्लास" के सदस्य हैं।

जासूस की रणनीति कार्डों को "पिन" (pin) करने की है।

जासूस डेक A के पहले कार्ड को लेता है और उसकी 100 प्रतियां बनाता है, उन्हें डेक के अंत में चिपका देता है।
फिर, वे डेक B के एक संभावित कार्ड (मान लीजिए स्थिति 5 वाला) को लेते हैं और उसकी 100 प्रतियां बनाते हैं, उन्हें भी डेक B के अंत में चिपका देते हैं।
वे रेफरी से पूछते हैं: "क्या ये नए, विशाल डेक समान हैं?"

यदि रेफरी "नहीं" कहता है, तो इसका मतलब है कि उम्मीदवार कार्ड (स्थिति 5) गलत चुनाव था। "एース" वहां नहीं जा सकता था।
यदि रेफरी "हाँ" कहता है, तो यह एक मजबूत संकेत है कि "एース" वास्तव में स्थिति 5 पर गया था।

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

पेपर सिद्ध करता है कि प्रत्येक कार्ड के लिए ऐसा करने से, आप एक-एक करके, पूरे शफल की सूची को पुनर्गठित कर सकते हैं। यह एक जिग्सॉ पहेली को एक-एक टुकड़े करके हल करने जैसा है, लेकिन टुकड़े को फिट करने के बजाय, आप एक जादुई दर्पण से पूछते हैं कि क्या तस्वीर सही दिख रही है।

दूसरा चरण: स्ट्रेच को खोजना

एक बार जब शफल ज्ञात हो जाता है, तो पहेली बहुत आसान हो जाती है। "स्ट्रेचिंग" वाला हिस्सा (डायगोनल मैट्रिक्स) प्रत्येक कार्ड के लिए गुप्त गुणकों (multipliers) को खोजने जैसा है।

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

कल्पना कीजिए कि आपके पास समीकरणों का एक सेट है: "कार्ड A (2 से स्ट्रेच किया गया) बराबर कार्ड B है।" यदि आप कार्ड A और कार्ड B जानते हैं, तो आप बस भाग देकर "2" को ज्ञात कर सकते हैं। पेपर बताता है कि यहाँ बिल्कुल यही होता है। लेखक इस समस्या को संकेतों के एक नेटवर्क (ग्राफ) में परिवर्तित करते हैं और गुप्त गुणकों को खोजने के लिए इसमें चलते हैं। यह चरण तेज़, नियत (deterministic) है, और इसमें और अधिक "हाँ/ना" प्रश्नों की आवश्यकता नहीं होती है।

अंतिम बॉस: "ट्विस्ट" (फील्ड ऑटोमोर्फिज्म)

सबसे जटिल संस्करण में एक "ट्विस्ट" शामिल है जहाँ संख्या प्रणाली के नियम ही बदल जाते है (एक फील्ड ऑटोमोर्फिज्म)। यह ऐसा है जैसे रेफरी अचानक निर्णय ले ले कि डेक B में, संख्या 2 वास्तव में 3 का अर्थ है।

पेपर दिखाता है कि यह ट्विस्ट "प्रोजेक्टिव क्लासेस" (समान कार्डों का समूह) को खराब नहीं करता है। क्योंकि समूह वही रहता है, जासूस पहले चरण के समान "पिनिंग" ट्रिक का उपयोग करके शफल को ढूंढ सकता है, भले ही ट्विस्ट शामिल हो।

एक बार शफल मिल जाने के बाद, जासूस हर संभव "ट्विस्ट" को आजमाता है (केवल $\log_p q$ ट्विस्ट होते हैं)। प्रत्येक संभावित ट्विस्ट के लिए, वे दूसरे चरण के "स्ट्रेचिंग" गणित को चलाते हैं। यदि गणित पूरी तरह से काम करता है, तो उन्होंने गुप्त ट्विस्ट को ढूंढ लिया है। यदि यह काम नहीं करता है, तो वे अगले ट्विस्ट को आजमाते हैं। चूंकि आजमाने के लिए बहुत कम ट्विस्ट हैं, इसलिए यह अभी भी बहुत तेज़ है।

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

पेपर दो मुख्य बातें सिद्ध करता है:

लीनियर कोड इक्विलेंस (LCE) के लिए: यदि आपके पास यह बताने वाला टूल है कि क्या दो कोड समान हैं (हाँ/नहीं), तो आप एक ऐसा टूल बना सकते हैं जो उचित समय में सटीक समाधान खोज सकता है।
जनरलाइज्ड कोड इक्विलेंस (GCE) के लिए: यह "ट्विस्ट" के साथ सबसे जटिल संस्करण के लिए भी काम करता है।

लेखक स्पष्ट रूप से इस विचार को खारिज करते हैं कि ये समस्याएं (सर्च) मौलिक रूप से तय करने (डिसाइड) की तुलना में कठिन हैं। पेपर सिद्ध करता है कि "सर्च" समस्या कोई अलग, कठिन पहाड़ नहीं है; यह बस एक पथ है जो स्वाभाविक रूप से "डिसीजन" पहाड़ का अनुसरण करता है।

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

संक्षेप में, यह पेपर हमें मास्टर की (master key) सौंपता है। यह दिखाता है कि "हाँ/ना" ओरेकल पूरे रहस्य को खोलने के लिए पर्याप्त शक्तिशाली है, जो एक अस्पष्ट पुष्टि को एक सटीक, कार्रवाई योग्य समाधान में बदल देता है। यह हमारे भविष्य के लिए सुरक्षित, क्वांटम-प्रूफ डिजिटल हस्ताक्षर बनाने के लिए पहेली के एक महत्वपूर्ण हिस्से को पूरा करने जैसा है।

तकनीकी सारांश: रैखिक और सामान्य कोड तुल्यता के लिए सर्च-टू-डिसीजन रिडक्शन (Search-to-Decision Reductions)

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

यह शोध पत्र कोड इक्विवेलेंस (Code Equivalence - CE) समस्या को संबोधित करता है, जो यह पूछता है कि क्या दो रैखिक कोड (linear codes) विशिष्ट मीट्रिक-संरक्षण परिवर्तनों (metric-preserving transformations) के सेट तक समान हैं। लेखक दो विशिष्ट वेरिएंट्स पर ध्यान केंद्रित करते हैं:

लीनियर कोड इक्विवेलेंस (LCE): यह निर्धारित करना कि क्या दो कोड $C_1$ और $C_2$ (जेनेरेटर मैट्रिसेस $G$ और $F$ के साथ) किसी व्युत्क्रमणीय मैट्रिक्स $S \in GL_k(\mathbb{F}_q)$ और मोनोमियल मैट्रिक्स $M \in Mon_n$ के लिए $SGM = F$ को संतुष्ट करते हैं।
जनरलाइज्ड कोड इक्विवेलेंस (GCE): LCE को फील्ड ऑटोमोर्फिज्म (field automorphisms) को शामिल करने के लिए विस्तारित करना, यह पूछना कि क्या $S \alpha(G) M = F$ किसी $\alpha \in Aut(\mathbb{F}_q)$ के लिए सत्य है।

जबकि हाल के कार्य [4] ने परम्यूटेशन कोड इक्विवेलेंस (PCE) के लिए एक सर्च-टू-डिसीजन रिडक्शन स्थापित किया, LCE और GCE के मामलों में इसका विस्तार एक खुला प्रश्न बना हुआ था। यह शोध पत्र उस अंतर को हल करता है, और LCE एवं GCE के सर्च संस्करणों से उनके डिसीजन समकक्षों (decision counterparts) के लिए कुशल रिडक्शन प्रदान करता है।

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

प्रस्तावित कार्यप्रणाली [4] में उपयोग किए गए PCE फ्रेमवर्क को अनुकूलित करती है, लेकिन LCE और GCE में निहित स्केलिंग और फील्ड ऑटोमोर्फिज्म घटकों को संभालने के लिए आवश्यक संशोधनों को पेश करती है। रिडक्शन दो प्राथमिक चरणों में आगे बढ़ता है:

1. परम्यूटेशन घटक की रिकवरी (Recovery of the Permutation Component)

पहला चरण मोनोमियल मैट्रिक्स $M = PD $से जुड़े परम्यूटेशन$ \pi$ को रिकवर करना है।

प्रोजेक्टिव क्लासेस (Projective Classes): PCE (जहाँ समान कॉलम का उपयोग होता है) के बजाय, लेखक प्रोजेक्टिव क्लासेस का उपयोग करते हैं। दो कॉलम $g_i$ और $g_j$ एक ही क्लास के अंतर्गत आते हैं यदि वे आनुपातिक (proportional) हैं ( $g_i \sim g_j$ )। एक मुख्य लेम्मा यह स्थापित करता है कि कोई भी फील्ड ऑटोमोर्फिज्म $\alpha$ इन प्रोजेक्टिव क्लासेस को सुरक्षित रखता है।
ओरेकल क्वेरीज़ (Oracle Queries): एल्गोरिदम प्रत्येक इंडेक्स $t$ $t$ के लिए इमेज $\pi(t)$ $π (t)$ को पुनरावृत्ति (iteratively) से निर्धारित करता है। यह जेनेरेटर मैट्रिसेस $G$ $G$ और $F$ $F$ में विशिष्ट कॉलम की कई कॉपियाँ जोड़कर क्वेरी इंस्टेंस का निर्माण करता है।
- यदि किसी कॉलम की प्रोजेक्टिव क्लास पहले से ही "प्रतिनिधित्व" (represent) या मैप की जा चुकी है, तो इमेज को क्लास साइज के बायजेक्शन (bijection) का लाभ उठाकर बिना ओरेकल कॉल के निर्धारित किया जाता है।
- यदि क्लास अनरिप्रेजेंटेड है, तो एल्गोरिदम कॉलम $t$ की $(\ell+1)m$ कॉपियाँ $G$ में और कॉलम $i$ की $F$ में जोड़कर कैंडिडेट इमेजेस $i$ का परीक्षण करता है। डिसीजन ओरेकल यह निर्धारित करता है कि क्या एक वैध इक्विवेलेंस मौजूद है।
यूनिकनेस (Uniqueness): क्लास साइज के आधार पर जोड़े गए कॉलमों की संख्या को सावधानीपूर्वक नियंत्रित करके, एल्गोरिदम यह सुनिश्चित करता है कि ओरेकल द्वारा पाया गया कोई भी वैध इक्विवेलेंस विशिष्ट टारगेट कॉलम को टेस्ट किए गए कैंडिडेट पर मैप करेगा, जिससे परम्यूटेशन प्रभावी रूप से "पिन" (pin) हो जाता है।

2. डायगोनल और ऑटोमोर्फिज्म घटकों की रिकवरी (Recovery of the Diagonal and Automorphism Components)

एक बार जब परम्यूटेशन $P$ रिकवर हो जाता है, तो समस्या डायगोनल मैट्रिक्स $D$ (और GCE के लिए ऑटोमोर्फिज्म $\alpha$ ) को खोजने में बदल जाती है।

डायगोनल इक्विवेलेंस में रिडक्शन: $P$ ज्ञात होने के साथ, समीकरण $SGM = F $बदलकर$ S(GP)D = F $हो जाता है। मैट्रिसेस को सिस्टेमैटिक फॉर्म (एक इंफॉर्मेशन सेट का उपयोग करके) में बदलकर, समस्या को$ D_I^{-1} A'' D_J = F'' $को हल करने में बदल दिया जाता है, जहाँ$ A'' $और$ F''$ सब-मैट्रिसेस हैं। यह डायगोनल इक्विवेलेंस समस्या का एक उदाहरण है।
एंजेल-श्नाइडर एल्गोरिदम (Engel-Schneider Algorithm): लेखक डायगोनल इक्विवेलेंस समस्या को हल करने के लिए नियत (deterministic) एंजेल-श्नाइडर एल्गोरिदम [8] का उपयोग करते हैं। इसमें नॉन-जीरो एंट्रीज के आधार पर एक बाइपार्टाइट ग्राफ का निर्माण करना और स्केलिंग फैक्टर्स को निर्धारित करने के लिए ब्रेड्थ-फर्स्ट सर्च का उपयोग करना शामिल है। यह चरण बिना किसी अतिरिक्त ओरेकल एक्सेस के, नियत बहुपद समय (deterministic polynomial time) में किया जाता है।
GCE को संभालना: जनरलाइज्ड केस के लिए, चूंकि फील्ड ऑटोमोर्फिज्म प्रोजेक्टिव क्लासेस को सुरक्षित रखते हैं, इसलिए परम्यूटेशन रिकवरी स्टेप समान रहता है। इसके बाद, एल्गोरिदम सभी संभावित फील्ड ऑटोमोर्फिज्म्स (जिनकी संख्या $\log_p q$ है) के माध्यम से पुनरावृत्ति करता है। प्रत्येक कैंडिडेट $\alpha$ के लिए, यह $(\alpha(G), F)$ के लिए LCE इंस्टेंस को हल करने का प्रयास करता है। यदि कोई समाधान मौजूद है, तो सही $\alpha$ की पहचान कर ली जाती है।

मुख्य योगदान और परिणाम (Key Contributions and Results)

शोध पत्र निम्नलिखित मुख्य परिणाम प्रस्तुत करता है:

थ्योरम I.1: search-LCE से LCE के बीच एक कुशल रिडक्शन है। यह रिडक्शन अधिकतम $O(n^2)$ ओरेकल कॉल्स का उपयोग करता है। ओरेकल क्वेरीज़ में लंबाई $n + \frac{2}{27}n^3 + O(n^2)$ वाले कोड शामिल हैं।
थ्योरम I.2: search-GCE से GCE के बीच एक कुशल रिडक्शन है। यह स्वाभाविक रूप से LCE परिणाम का अनुसरण करता है, क्योंकि परम्यूटेशन रिकवरी फील्ड ऑटोमोर्फिज्म के तहत अपरिवर्तित रहती है, और शेष घटकों को ऑटोमोर्फिज्म के साइक्लिक ग्रुप के माध्यम से पुनरावृति करके हल किया जाता है।
नियत बहुपद समय (Deterministic Polynomial Time): डायगोनल और ऑटोमोर्फिज्म घटकों की रिकवरी एंजेल-श्नाइडर एल्गोरिदम पर भरोसा करते हुए, $n$ , $k$ , और $\log q$ के बहुपद समय में नियत रूप से प्राप्त की जाती है।

महत्व और दावे (Significance and Claims)

लेखक दावा करते हैं कि उनका कार्य हाल के सर्वेक्षणों [9] और PCE रिडक्शन पेपर [4] में हाइलाइट किए गए खुले प्रश्नों को हल करता है। प्राथमिक महत्व LCE या GCE के लिए किसी भी डिसीजन सॉल्वर को बहुपद समय में सर्च सॉल्वर में रचनात्मक रूप से परिवर्तित करना है।

फ्रेमवर्क की पूर्णता (Completeness of the Framework): पेपर प्रदर्शित करता है कि PCE के लिए सर्च-टू-डिसीजन रिडक्शन स्वाभाविक रूप से अधिक जटिल लीनियर और जनरलाइज्ड सेटिंग्स में विस्तारित होता है, बशर्ते कि प्रोजेक्टिव क्लासेस की संरचना और डायगोनल इक्विवेलेंस के मौजूदा एल्गोरिदम का लाभ उठाया जाए।
क्रिप्टोग्राफिक निहितार्थ (Cryptographic Implications): इन रिडक्शंस को स्थापित करके, यह पेपर इन समस्याओं के हार्डनेस लैंडस्केप की समझ को मजबूत करता है, जो लीनियर इक्विवेलेंस सिग्नेचर स्कीम (LESS) [3] जैसे पोस्ट-क्वांटम क्रिप्टोग्राफिक स्कीम्स के लिए आधारभूत हैं।
सीमाएं और भविष्य का कार्य (Limitations and Future Work): लेखक विनम्रतापूर्वक नोट करते हैं कि वे GCE से LCE (या इसके विपरीत) की ओर रिवर्स दिशा में रिडक्शन प्रदान नहीं करते हैं, हालांकि ऑटोमोर्फिज्म की गणना करना GCE से LCE तक एक रिडक्शन प्रदान करता है। इसके अलावा, वे पहचान करते हैं कि मैट्रिक्स कोड इक्विवेलेंस (MCE) के लिए एक समान सर्च-टू-डिसीजन रिडक्शन, जिसका उपयोग MEDS स्कीम [5] में किया जाता है, अभी भी एक खुला प्रश्न है।

शोध पत्र निष्कर्ष निकालता है कि हैमिंग मीट्रिक वेरिएंट्स (PCE, LCE, GCE) के लिए सर्च-टू-डिसीजन रिडक्शन अब तय हो गए हैं, जो इन विशिष्ट इक्विवेलेंस समस्याओं के लिए एक पूर्ण सैद्धांतिक टूलकिट प्रदान करते हैं।