💻 computer science

The complexity of solving a system of equations of the same degree

यह शोध पत्र समीकरणों के उन तंत्रों के लिए नियमितता की डिग्री (degree of regularity) और समाधान जटिलता (solving complexity) पर ऊपरी सीमाएं स्थापित करता है जिनका डिग्री समान (uniform degree) होता है और जो क्रिप्टोग्राफी में प्रचलित हैं, जो चरों (variables), समीकरणों और समीकरण की डिग्री पर उनकी निर्भरता का विश्लेषण करके किया गया है।

मूल लेखक: Giulia Gaggero, Elisa Gorla

प्रकाशित 2026-02-02

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

CC BY 4.0

मूल लेखक: Giulia Gaggero, Elisa Gorla

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

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

यह शोध पत्र इस बारे बारे में है कि इन तालों को तोड़ना कितना कठिन है और बिना किसी भाग्यशाली अनुमान (lucky guesses) पर निर्भर रहे, प्रयास के लिए एक गारंटीकृत "सबसे खराब स्थिति" (worst-case) का अनुमान प्रदान करने के बारे में है।

यहाँ रोजमर्रा के उपमाओं (analogies) का उपयोग करके इस शोध पत्र के विचारों का विवरण दिया गया है:

1. समस्या: उलझी हुई गांठ (The Tangled Knot)

क्रिप्टोग्राफी अक्सर इस विचार पर टिकी होती है कि बहुपद समीकरणों (polynomial equations) के एक तंत्र को हल करना अविश्वसनीय रूप से कठिन है (जैसे $x^2 + y = 5$ और $xy + z = 10$)। यदि आप उन्हें जल्दी से हल नहीं कर सकते, तो गुप्त कुंजी सुरक्षित रहती है।

इन प्रणालियों को तोड़ने के लिए, गणितज्ञ एक शक्तिशाली उपकरण का उपयोग करते हैं जिसे ग्रोबनर बेसिस (Gröbner basis) कहा जाता है। इस उपकरण को एक विशाल, स्वचालित छँटाई मशीन (sorting machine) के रूप में समझें। यह आपके बिखरे हुए समीकरणों को लेता है और उन्हें एक व्यवस्थित, समाधान योग्य सूची में पुनर्गठित करता है। हालाँकि, इस मशीन को छँटाई के कई "चरणों" (rounds) से गुजरना पड़ता है। इसे जितने अधिक चरणों की आवश्यकता होती है, उतना ही अधिक समय और कंप्यूटर शक्ति लगती है।

यह शोध पत्र एक विशिष्ट मीट्रिक पर ध्यान केंद्रित करता है जिसे डिग्री ऑफ रेगुलैरिटी (degree of regularity) कहा जाता है। आप इसे छँटाई मशीन की सीढ़ी की "ऊंचाई" के रूप में देख सकते हैं।

कम ऊंचाई: मशीन समीकरणों को जल्दी छाँट लेती है। ताला कमजोर है।
उच्च ऊंचाई: मशीन को समाधान खोजने के लिए बहुत ऊपर चढ़ना पड़ता है। ताला मजबूत है।

2. पुराना तरीका: ऊंचाई का अनुमान लगाना (Guessing the Height)

पहले, विशेषज्ञ इस "ऊंचाई" का अनुमान लगाने के लिए यह मान लेते थे कि समीकरण यादृच्छिक (random) और पूरी तरह से संतुलित (एक अवधारणा जिसे "सेमीरेगुलर" कहा जाता है) हैं। यह ऐसा ही है जैसे यह मान लेना कि आपके सामने आने वाली हर गांठ एक मानक, अनुमानित उलझन है।

दोष: यह केवल एक अनुमान है। कभी-कभी, गांठ वास्तव में एक अजीब, पेचीदा आकार की होती है जो नियमों का पालन नहीं करती है। यदि आप गलत अनुमान लगाते हैं, तो आप सोच सकते हैं कि एक ताला सुरक्षित है जबकि वह वास्तव में तोड़ना आसान है, या इसके विपरीत।

3. नया तरीका: एक गारंटीकृत सीमा (A Guaranteed Ceiling)

इस पत्र के लेखक कहते हैं, "चलिए अनुमान लगाना बंद करते हैं। आइए एक कठिन सीमा सिद्ध करें।"

वे उन प्रणालियों पर ध्यान केंद्रित करते हैं जहाँ सभी समीकरणों की डिग्री समान (जैसे, वे सभी द्विघात/quadratic या त्रिघात/cubic हैं) होती है। वे सिद्ध करते हैं कि समीकरणों को चाहे किसी भी तरह से व्यवस्थित किया जाए, एक गणितीय सीमा (ceiling) (एक ऊपरी सीमा) है कि छँटाई की सीढ़ी को कितनी ऊँचाई तक जाना होगा।

पुस्तकालय की उपमा:
कल्पना कीजिए कि आपके पास $n$ अलमारियाँ और $m$ किताबें वाला एक पुस्तकालय है।

समीकरणों की डिग्री यह है कि किताबें कितनी मोटी हैं।
चरों (variables) की संख्या अलमारियों की संख्या है।
समीकरणों की संख्या किताबों की संख्या है।

लेखक सिद्ध करते हैं कि यदि आपके पास एक ही मोटाई की निश्चित संख्या में किताबें हैं, तो आप गणितीय रूप से गारंटी दे सकते हैं कि आपको सही क्रम खोजने के लिए एक विशिष्ट अलमारी से ऊपर कभी भी चढ़ने की आवश्यकता नहीं होगी। वे इस अधिकतम अलमारी की संख्या की गणना सख्ती से इन आधारों पर करते हैं:

आपके पास कितनी किताबें हैं ( $m$ )।
कितनी अलमारियाँ हैं ( $n$ )।
किताबें कितनी मोटी हैं (डिग्री)।

4. "फील्ड इक्वेशन्स" का मोड़ (The "Field Equations" Twist)

क्रिप्टोग्राफी में, एक विशेष नियम होता है: संख्याएँ आमतौर पर घूमकर वापस आती हैं (जैसे एक घड़ी की तरह)। यदि आप 0 से 9 तक की संख्याओं के साथ काम कर रहे हैं, तो $10$ शून्य बन जाता है। गणित में, इसे "फील्ड इक्वेशन्स" जोड़ना कहा जाता है।

यह शोध पत्र इस बात पर भी नज़र रखता है कि इन "घूमकर वापस आने वाले" नियमों को मिश्रण में जोड़ने पर क्या होता है।

बिना 'वापस आने वाले' नियम के: छँटाई मशीन को एक निश्चित ऊंचाई तक चढ़ने की आवश्यकता हो सकती है।
'वापस आने वाले' नियम के साथ: मशीन समाधान तेजी से ढूंढ सकती है क्योंकि नियम अधिक सख्त हैं।

लेखक इस परिदृश्य के लिए भी एक नया, गारंटीकृत 'सीलिंग' (ऊपरी सीमा) प्रदान करते हैं। वे दिखाते हैं कि इन अतिरिक्त नियमों के साथ भी, समस्या कितनी कठिन हो सकती है, इसकी एक सीमा है, और वे सटीक रूप से गणना करते हैं कि वह सीमा क्या है।

5. यह क्यों महत्वपूर्ण है ("सिद्ध" होने का लाभ)

यह शोध पत्र स्वीकार करता है कि उनके द्वारा गणना की गई "सीलिंग" (ऊपरी सीमा) वास्तव में आवश्यक ऊंचाई से थोड़ी अधिक हो सकती है।

ह्यूरिस्टिक (पुराना तरीका): "मुझे दाैंक है कि यह गांठ आसानी से खुल जाएगी क्योंकि यह यादृच्छिक दिखती है।" (तेज़, लेकिन जोखिम भरा)।
प्रमाण (यह शोध पत्र): "मैं यह सिद्ध नहीं कर सकता कि यह गांठ आसान है, लेकिन मैं यह सिद्ध कर सकता हूँ कि इसे खोलने में 100 चरणों से अधिक कभी नहीं लगेगा।" (धीमा अनुमान, लेकिन 100% सुरक्षित)।

यह सुरक्षा के लिए अत्यंत महत्वपूर्ण है। यदि कोई क्रिप्टोग्राफर ऐसा ताला डिजाइन करना चाहता है जो अगले 50 वर्षों तक सुरक्षित रहे, तो उसे "सबसे खराब स्थिति" (worst-case scenario) को जानने की आवश्यकता है। वे इस उम्मीद पर निर्भर नहीं रहना चाहते कि समीकरण "अच्छे" होंगे। वे एक गणितीय गारंटी चाहते हैं कि छँटाई मशीन को कभी भी एक सुरक्षित ऊंचाई से ऊपर नहीं चढ़ना पड़ेगा।

सारांश

यह शोध पत्र एक गणितीय सुरक्षा जाल (mathematical safety net) प्रदान करता है। यह हमें बताता है: "यदि आपके पास चरों और समीकरणों की इन विशिष्ट संख्याओं वाला समीकरणों का एक तंत्र है, तो आप 100% निश्चित हो सकते हैं कि इसे हल करने के लिए X से अधिक गणनात्मक प्रयास की आवश्यकता नहीं होगी।"

यह "यह शायद यादृच्छिक दिखता है, इसलिए यह कठिन है" के अनुमान को "हमने सिद्ध किया है कि यह इससे अधिक कठिन नहीं हो सकता" की निश्चितता से बदल देता है। यह क्रिप्टोग्राफरों को वर्तमान गणितीय हमलों के खिलाफ ज्ञात, गारंटीकृत स्तर की सुरक्षा के साथ सिस्टम डिजाइन करने की अनुमति देता है।

तकनीकी सारांश: समान डिग्री के समीकरणों के तंत्र (Systems of Equations) को हल करने की जटिलता

समस्या विवरण

अनेक क्रिप्टोग्राफिक स्कीम्स, विशेष रूप से मल्टीवेरिएट क्रिप्टोग्राफी और पोस्ट-क्वांटम परिवेश में, की सुरक्षा मल्टीवेरिएट बहुपद समीकरणों (multivariate polynomial equations) के तंत्र को परिमित क्षेत्रों (finite fields) पर हल करने की कम्प्यूटेशनल कठिनाई पर टिकी होती है। ग्रोबनर बेसिस (Gröbner basis) विधियों के माध्यम से ऐसे तंत्रों को हल करने की जटिलता मुख्य रूप से डिग्री ऑफ रेगुलैरिटी ( $d_{reg}$ ) और सॉल्विंग डिग्री द्वारा नियंत्रित होती है। जबकि डिग्री ऑफ रेगुलैरिटी, ग्रोबनर बेसिस गणनाओं की जटिलता पर एक ऊपरी सीमा (upper bound) प्रदान करती है, क्रिप्टोग्राफिक आकार के तंत्रों के लिए इसे गणना करना या अनुमान लगाना अक्सर कठिन होता है।

सामान्य अभ्यास इस ह्यूरिस्टिक (heuristic) धारणा पर निर्भर करता है कि तंत्र सेमीरेगुलर (semiregular) या क्रिप्टोग्राफिक सेमीरेगुलर हैं, जो डिग्री ऑफ रेगुलैरिटी के लिए स्पष्ट सूत्र प्रदान करते हैं। हालांकि, यह धारणा हमेशा मान्य नहीं होती है; ऐसे पैरामीटर चयन और क्षेत्र मौजूद हैं जहाँ कोई सेमीरेगुलर अनुक्रम (sequence) उपलब्ध नहीं होता है। फलस्वरूप, डिग्री ऑफ रेगुलैरिटी और सॉल्विंग डिग्री पर प्रमाणित (proven), गैर-ह्यूरिस्टिक ऊपरी सीमाओं की आवश्यकता है, जो उन तंत्रों पर लागू हो सकें जहाँ डिग्री ऑफ रेगुलैरिटी परिमित है, बिना सेमीरेगुलरिटी धारणा पर निर्भर रहे।

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

लेखक कम्यूटेटिव अलजेब्रा (commutative algebra) के उपकरणों का उपयोग करके इस समस्या के प्रति दृष्टिकोण अपनाते हैं, विशेष रूप से उन तंत्रों पर ध्यान केंद्रित करते हैं जहाँ दिए गए डिग्री $D$ में $n$ बहुपदों का एक रेगुलर सीक्वेंस (regular sequence) बनाने वाला शीर्ष-डिग्री भाग (top-degree part) का आइडियल (ideal) मौजूद हो।

फ्रेमवर्क: पेपर $n$ चरों वाले $m$ बहुपदों के एक तंत्र $F = \{f_1, \dots, f_m\}$ पर विचार करता है जो एक क्षेत्र $F$ पर आधारित है। विश्लेषण यह मानता है कि शीर्ष-डिग्री भाग $f_1^{top}, \dots, f_m^{top}$ रैखिक रूप से स्वतंत्र हैं और तंत्र डिग्री $D$ में रेगुलर है (अर्थात शीर्ष-डिग्री भागों द्वारा जनरेट किया गया आइडियल डिग्री $D$ के $n$ बहुपदों का एक रेगुलर सीक्वेंस समाहित करता है)।
LPP आइडियल्स में न्यूनीकरण (Reduction to LPP Ideals): कास्टेलनुओवो-ममफोर्ड रेगुलैरिटी (Castelnuovo-Mumford regularity) को बाउंड करने के लिए, जो कि परिमित होने पर डिग्री ऑफ रेगुलैरिटी के बराबर होती है, लेखक आइजनबड-ग्रीन-हैरिस (EGH) अनुमान का उपयोग करते हैं। यह अनुमान यह दावा करता है कि विशिष्ट डिग्री के रेगुलर सीक्वेंस वाले होमोजेनियस आइडियल्स के बीच, लेक्स-प्लस-पावर्स (LPP) आइडियल की रेगुलैरिटी अधिकतम होती है।
संयोजन विश्लेषण (Combinatorial Analysis): लेखक दिए गए पैरामीटर्स ( $n, m, D$ ) से जुड़े विशिष्ट LPP आइडियल्स का निर्माण करते हैं। लेक्सिकोग्राफिक ऑर्डर के तहत इन आइडियल्स की संरचना का विश्लेषण करके, वे LPP आइडियल की रेगुलैरिटी निर्धारित करते हैं, जो मूल तंत्र की रेगुलैरिटी के लिए एक ऊपरी सीमा के रूप में कार्य करता है (EGH अनुमान के अधीन)।
फील्ड इक्वेशन्स (Field Equations): पद्धति को फील्ड इक्वेशन्स ( $x_i^q - x_i$ ) के साथ संवर्धित तंत्रों तक विस्तारित किया गया है, जो परिमित क्षेत्र $\mathbb{F}_q$ के लिए महत्वपूर्ण है, विशेष रूप से जब समीकरणों की डिग्री $D$ , क्षेत्र के आकार $q$ से अधिक या उसके बराबर हो।

मुख्य योगदान और परिणाम

1. डिग्री $D$ में रेगुलर तंत्रों के लिए ऊपरी सीमाएं (बिना फील्ड इक्वेशन्स के)

थ्योरम 23 डिग्री $D$ के $n$ चरों वाले $m$ समीकरणों के तंत्र की डिग्री ऑफ रेगुलरिटी के लिए एक सटीक (sharp) ऊपरी सीमा प्रदान करता है, यह मानते हुए कि तंत्र डिग्री $D$ में रेगुलर है।

यह सीमा समीकरणों की संख्या ( $m$ ), चरों ( $n$ ), और डिग्री ( $D$ ) पर निर्भर करती है।
सूत्र में विशिष्ट पूर्णांकों $k$ और $t$ की पहचान करना शामिल है ताकि $m-n$ एक विशिष्ट अंतराल (interval) के भीतर आता है जो कॉम्बिनेटोरियल सम ( $\sigma_{k,t}$ ) द्वारा परिभाषित है।
परिणामी सीमा है: $d_{reg}(F) \le (D - t) + (n - k)(D - 1)$ ।
यह सीमा सभी $m, n, D$ के मानों के लिए सटीक (sharp) है और उन तंत्रों द्वारा प्राप्त की जाती है जहाँ शीर्ष-डिग्री भाग एक विशिष्ट LPP आइडियल बनाते हैं।

कोरोलरी 27 इसे म्यूटेंट एल्गोरिदम (mutant algorithms) के लिए सॉल्विंग डिग्री के ऊपरी सीमा में अनुवादित करती है:
$\text{solv. deg}_m(F) \le D - t + 1 + (n - k)(D - 1)$

2. फील्ड इक्वेशन्स के साथ तंत्रों के लिए ऊपरी सीमाएं

पेपर फील्ड इक्वेशन्स जोड़े जाने के मामले को संबोधित करता है, जो $D \ge q$ होने पर प्रणालियों के लिए आवश्यक है।

प्रपोजिशन 31: बहुत अधिक ओवरडिटरमाइंडेड (overdetermined) तंत्रों के लिए (जहाँ $m$ , फील्ड इक्वेशन्स के मोड्यूलो बहुपदों के स्पेस के आयाम से अधिक है), डिग्री ऑफ रेगुलैरिटी ठीक $D$ होती है।
थ्योरम 33: उन तंत्रों के लिए जहाँ $q \le D \le n(q-1)$ $q \leq D \leq n (q - 1)$ है और शीर्ष-डिग्री भाग फील्ड इक्वेशन्स के मोड्यूलो रैखिक रूप से स्वतंत्र हैं, लेखक डिग्री ऑफ रेगुलरिटी पर एक ऊपरी सीमा प्रदान करते हैं।
- सीमा को $(x_1^q, \dots, x_n^q)$ के मोड्यूलो डिग्री $D$ के लेक्सिकोग्राफिक ऑर्डरिंग में $m$ -वें मोनॉमियल की स्थिति का विश्लेषण करके प्राप्त किया जाता है।
- सीमा को $B = q - t + (n - k)(q - 1)$ के रूप में व्यक्त किया जाता है, जहाँ $k$ और $t$ को $m$ द्वारा निर्धारित अंतराल द्वारा निर्धारित किया जाता है।
- $m, D,$ और $t$ के संबंध में विशिष्ट शर्तों के आधार पर, सीमा या तो $B$ या $B-1$ होती है।

कोरोलरी 34 इन परिणामों को बाइनरी सिस्टम्स ( $q=2$ ) के लिए विशिष्ट बनाती है, जो $\mathbb{F}_2$ पर डिग्री $D$ के तंत्रों के लिए डिग्री ऑफ रेगुलरिटी और सॉल्विंग डिग्री के लिए सरलीकृत सूत्र प्रदान करती है।

3. विशिष्ट स्कीम्स पर अनुप्रयोग

लेखक अपने बाउंड्स को ठोस क्रिप्टोग्राफिक स्कीम्स पर लागू करते हैं:

क्यूबिक सिंपल मैट्रिक्स (Cubic Simple Matrix): वे एक प्रमाणित सीमा $d_{reg} \le 2n - 1$ प्राप्त करते हैं, जो इस सिस्टम के लिए पहला प्रमाणित बाउंड है, जो पिछले ह्यूरिस्टिक अनुमानों के विपरीत है।
अनबैलेंस्ड ऑयल एंड वाइनगर (UOV): $\mathbb{F}_2$ पर UOV सिस्टम पर बाउंड्स को लागू किया गया है, जो यह दर्शाता है कि फील्ड इक्वेशन्स शामिल होने पर डिग्री ऑफ रेगुलरिटी कैसे व्यवहार करती है।

महत्व और दावे

पेपर मुख्य रूप से दावा करता है कि यह बहुपद तंत्रों को हल करने की जटिलता के लिए प्रमाणित, गैर-ह्यूरिस्टिक सीमाएं प्रदान करके महत्वपूर्ण है।

विश्वसनीयता: सेमीरेगुलरिटी धारणा पर आधारित अनुमानों (जो कुछ पैरामीटर्स के लिए विफल हो सकते हैं) के विपरीत, ये सीमाएं किसी भी ऐसे तंत्र के लिए मान्य हैं जहाँ डिग्री ऑफ रेगुलरिटी परिमित है और तंत्र एक दिए गए डिग्री में रेगुलर है।
व्यापकता: परिणाम किसी भी क्षेत्र पर तंत्रों पर लागू होते हैं और फील्ड इक्वेशन्स के साथ और बिना, दोनों मामलों को कवर करते हैं।
सटीकता (Sharpness): बाउंड्स को "सटीक" (sharp) बताया गया है, जिसका अर्थ है कि वे विशिष्ट तंत्रों (LPP आइडियल्स) द्वारा प्राप्त किए जाते हैं, जो सुरक्षा विश्लेषण के लिए एक यथार्थवादी वर्स्ट-केस (worst-case) अनुमान प्रदान करते हैं।
सीमाएं: लेखक स्पष्ट रूप से स्वीकार करते हैं कि उनके बाउंड्स आमतौर पर सेमीरेगुलरिटी ह्यूरिस्टिक के तहत प्राप्त बाउंड्स की तुलना में कम टाइट (अर्थात, अधिक ऊंचे) हैं। हालांकि, उनका तर्क है कि अनप्रमाणित धारणाओं से बचने के लिए यह ट्रेड-ऑफ आवश्यक है, विशेष रूप से उन परिदृश्यों में जहाँ सेमीरेगुलर सीक्वेंस मौजूद नहीं होते हैं।

यह कार्य नए एल्गोरिदम या प्रयोगात्मक कार्यान्वयन का प्रस्ताव नहीं करता है, बल्कि व्यापक श्रेणी के बहुपद तंत्रों (जो क्रिप्टोग्राफी के लिए प्रासंगिक हैं) के लिए मौजूदा ग्रोबनर बेसिस विधियों (मानक और म्यूटेंट दोनों) की जटिलता की सैद्धांतिक सीमाओं को स्थापित करता है।