💻 computer science

An average case efficient algorithm for solving two-variable linear Diophantine equations

यह शोध पत्र दो-चरों वाले रैखिक डायोफेंटाइन समीकरणों को हल करने के लिए एक औसत-मामले में कुशल पुनरावृत्ति एल्गोरिदम प्रस्तुत करता है जो पुनरावृत्ति कॉल्स की औसत संख्या में एक स्थिरांक-पद सुधार प्रदर्शित करके और सभी समाधान योग्य इनपुट उदाहरणों के लिए कम पुनरावृत्ति प्राप्त करके विस्तारित यूक्लिड एल्गोरिदम से बेहतर प्रदर्शन करता है।

मूल लेखक: Mayank Deora, Pinakpani Pal

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

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

CC BY 4.0

मूल लेखक: Mayank Deora, Pinakpani Pal

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

बड़ी तस्वीर: "जादुई चाबी" की समस्या

कल्पना कीजिए कि आपके पास एक विशाल, जटिल ताला (एक गणितीय समीकरण) है और आपको इसे खोलने के लिए एक आदर्श चाबी ढूंढनी है। क्रिप्टोग्राफी (ऑनलाइन बैंकिंग और RSA एन्क्रिप्शन जैसी चीजों में उपयोग किए जाने वाले गुप्त कोड का विज्ञान) की दुनिया में, यह "ताला" एक लीनियर डायोफेंटाइन इक्वेशन (Linear Diophantine Equation) है।

यह समीकरण इस प्रकार दिखता है: $ax + by = c$।

$a$ और $b$ बड़े नंबर हैं (ताले के टंबलर्स की तरह)।
$c$ वह लक्ष्य संख्या है जिसे आप प्राप्त करना चाहते हैं।
$x$ और $y$ वे गुप्त चाबियाँ (पूर्णांक/integers) हैं जिन्हें आप खोजने की कोशिश कर रहे हैं।

दशकों से, इन चाबियों को खोजने के लिए "गोल्ड स्टैंडर्ड" एक पुराना, भरोसेमंद टूल रहा है जिसे एक्सटेंडेड यूक्लिड एल्गोरिदम (Extended Euclid's Algorithm) कहा जाता है। यह एक मास्टर लॉकस्मिथ (ताला बनाने वाला) की तरह है जिसने 2,000 वर्षों से एक ही सेट औजारों का उपयोग किया है। यह हमेशा काम करता है, लेकिन यह थोड़ा धीमा हो सकता है क्योंकि टंबलर्स को घुमाने के लिए इसमें बहुत सारे स्टेप्स लेने पड़ते हैं।

नया दावेदार: "DEA" एल्गोरिदम

इस पेपर के लेखक, मयंक देवरा और पिनाकपानी पाल ने एक पुराने, थोड़े अलग तरीके को फिर से देखने का फैसला किया जिसे DEA-R (डायोफेंटाइन इक्वेशन एल्गोरिदम - रिकर्सिव) कहा जाता है। उन्होंने पूछा: "क्या हम इस पुराने तरीके को गोल्ड स्टैंडर्ड से तेज़ बना सकते हैं?"

उन्होंने पाया कि इसका जवाब हाँ है, लेकिन एक ट्विस्ट के साथ। नया तरीका केवल सीधी रेखा में "तेज़" नहीं है; यह इस बारे में स्मार्ट है कि उसे कब रुकना है।

असली मंत्र: "पीरियडिक" पैटर्न

यहाँ उनकी खोज का सबसे दिलचस्प हिस्सा है, जिसे एक उपमा (analogy) के माध्यम से समझाया गया है:

कल्पना कीजिए कि आप एक विशिष्ट दरवाजे को खोजने के लिए सीढ़ियाँ चढ़ रहे हैं।

पुराना तरीका (Extended Euclid): आप एक समय में एक कदम उठाते हैं, हर कदम को गिनते हुए, चाहे कुछ भी हो। आप ऊपर पहुँचने के लिए हमेशा उतने ही कदम लेते हैं, चाहे आप जिस भी दरवाजे को ढूंढ रहे हों।
नया तरीका (DEA): लेखकों ने महसूस किया कि आपको कितने कदम लेने की आवश्यकता है, यह दरवाजे के नंबर (मान $c$ ) पर निर्भर करता है।

उन्होंने एक छिपा हुआ लय (rhythm) या पैटर्न (गणितज्ञ इसे "पीरियडिसिटी" कहते हैं) खोजा।

यदि दरवाजा नंबर ( $c$ ) एक "लकी" (भाग्यशाली) नंबर है, तो नया एल्गोरिदम शायद केवल एक स्टेप में समाधान ढूंढ लेगा।
यदि यह एक "अनलकी" (दुर्भाग्यशाली) नंबर है, तो इसमें कई स्टेप्स लग सकते हैं।
हालाँकि, ये "लकी" और "अनलकी" नंबर एक अनुमानित चक्र में दोहराते हैं।

उपमा: पुराने एल्गोरिदम को एक मेट्रोनोम की तरह समझें जो हर बार दरवाजा खोलने पर 100 बार क्लिक करता है। नया एल्गोरिदम एक स्मार्ट सेंसर की तरह है। कभी-कभी यह 10 बार क्लिक करता है, कभी 50 बार, लेकिन औसतन यह मेट्रोनोम की तुलना में कम बार क्लिक करता है।

"कांस्टेंट" सुधार

लेखकों ने यह साबित करने के लिए गणित की गहराई तक जाकर अध्ययन किया कि नया एल्गोरिदम औसतन कितनी मेहनत बचाता है।

पुराना एल्गोरिदम: लगभग $\log(b)$ स्टेप्स लेता है। (इसे एक लंबे, घुमावदार रास्ते के रूप में कल्पना करें)।
नया एल्गोरिदम: लगभग $2.28 \times (\log(b) - 1)$ स्टेप्स लेता है।

हालाँकि दोनों अभी भी बड़े नंबरों के साथ बढ़ते हैं, लेकिन नया एल्गोरिदम लगातार एक कांस्टेंट (स्थिर) मात्रा से छोटा रहता है। यह एक शॉर्टकट खोजने जैसा है जो आपको काम पर जाने के लिए हर बार ठीक 5 मिनट बचाता है, चाहे आप कितनी भी दूर रहते हों। हजारों यात्राओं (या लाखों क्रिप्टोग्राफिक गणनाओं) में, यह बचत बहुत बड़ी हो जाती है।

सिद्धांत से वास्तविकता तक: "इटरेटिव" अपग्रेड

मूल "DEA" तरीका जिसे उन्होंने देखा था, वह रिकर्सिव (Recursive) था।

रिकर्सिव: रूसी नेस्टिंग डॉल्स (Russian nesting dolls) की कल्पना करें। समस्या को हल करने के लिए, कंप्यूटर एक गुड़िया खोलता है, उसके अंदर एक और समस्या पाता है, उसे खोलता है, और इसी तरह तब तक चलता है जब तक कि वह सबसे छोटी गुड़िया तक नहीं पहुँच जाता। फिर उसे वापस क्रम में उन सभी को बंद करना पड़ता है। इसमें बहुत अधिक मेमोरी (स्पेस) और समय लगता है।
इटरेटिव (Iterative): लेखकों ने एक नया संस्करण बनाया जिसे DEA-I कहा जाता है। नेस्टिंग डॉल्स के बजाय, यह एक कन्वेयर बेल्ट की तरह है। कंप्यूटर संख्याओं को एक सिंगल लूप में प्रोसेस करता है, बिना मेमोरी को स्टैक किए आगे बढ़ता है।

परिणाम: जब उन्होंने बहुत बड़े नंबरों (4096 बिट्स, जो कि बहुत बड़ा है!) के साथ कंप्यूटर पर इसका परीक्षण किया, तो उन्होंने पाया कि:

नया एल्गोरिदम (DEA-I) औसतन मानक एक्सटेंडेड यूक्लिड एल्गोरिदम की तुलना में तेज़ था।
उनके द्वारा टेस्ट किए गए 100% समाधान योग्य समस्याओं के लिए, नए एल्गोरिदम ने पुराने की तुलना में कम स्टेप्स लिए।

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

क्रिप्टोग्राफी की दुनिया में, कंप्यूटर आपके क्रेडिट कार्ड लेनदेन, एन्क्रिप्टेड संदेशों और डिजिटल हस्ताक्षरों के लिए सुरक्षित कुंजियाँ (keys) बनाने के लिए लगातार इन समीकरणों को हल कर रहे होते हैं।

यदि आप इन गणनाओं से समय का एक छोटा सा हिस्सा भी बचा सकते हैं, तो आप:

प्रति सेकंड अधिक लेनदेन सुरक्षित कर सकते हैं।
ऊर्जा बचा सकते हैं (कम CPU समय का मतलब है कम बिजली)।
एन्क्रिप्शन को तेज़ बना सकते हैं, विशेष रूप से उन उपकरणों के लिए जिनमें सीमित शक्ति होती है, जैसे स्मार्टवॉच या IoT डिवाइस।

सारांश

यह पेपर मूल रूप से ऑप्टिमाइज़ेशन (अनुकूलन) की कहानी है। लेखकों ने एक ज्ञात गणितीय समस्या ली, समाधान कैसे व्यवहार करते हैं इसके पीछे छिपे एक लयबद्ध पैटर्न को खोजा, और एक नया, सुव्यवस्थित टूल (DEA-I) बनाया जो उस पैटर्न का लाभ उठाता है।

उन्होंने गणितीय रूप से सिद्ध किया कि यह नया टूल औसतन अधिक कुशल है, और उन्होंने यह साबित करने के लिए एक कंप्यूटर प्रोग्राम बनाया कि यह वास्तविक दुनिया में काम करता है। यह एक याद दिलाता है कि प्राचीन गणित में भी, अभी भी ऐसे शॉर्टकट छिपे हुए हैं जिनकी खोज की जानी बाकी है।

यहाँ मयंक देवरा और पिनाकपाणि पाल के शोध पत्र "An average case efficient algorithm for solving two-variable linear Diophantine equations" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र दो-चरणीय रैखिक डायोफेंटाइन समीकरणों (two-variable linear Diophantine equations) को हल करने की समस्या को संबोधित करता है, जो $ax + by = c $के रूप में होते हैं, जहाँ$ a, b, c$ पूर्णांक (integers) हैं और लक्ष्य $x$ और $y$ के लिए पूर्णांक समाधान खोजना है। यह समस्या सार्वजनिक-कुंजी क्रिप्टोग्राफी (public-key cryptography) में मौलिक है, विशेष रूप से RSA और एलिप्टिक कर्व क्रिप्टोग्राफी (ECC) में मॉड्यूलर मल्टीप्लिकेटिव इनवर्स की गणना करने के लिए।

जबकि एक्सटेंडेड यूक्लिडियन एल्गोरिदम (EEA) इन समीकरणों को हल करने के लिए एक मानक विधि है जिसकी समय जटिलता (time complexity) $\Theta(\log b)$ है, लेखक यह जांचते हैं कि क्या वैकल्पिक एल्गोरिदम औसत मामले (average case) में रिकर्सिव कॉल्स या इटरेशन की संख्या में सुधार प्रदान कर सकते हैं। विशेष रूप से, वे पूर्व साहित्य (जिसे DEA-R कहा जाता है) में प्रस्तावित एक रिकर्सिव एल्गोरिदम की समीक्षा करते हैं और मानक EEA के विरुद्ध इसके प्रदर्शन का विश्लेषण करते हैं।

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

लेखक सैद्धांतिक विश्लेषण, एल्गोरिद्मिक रूपांतरण और अनुभवजन्य कार्यान्वयन (empirical implementation) के संयोजन का उपयोग करते हैं।

एल्गोरिद्मिक पुनरावलोकन और रूपांतरण:
- DEA-R: वे रिकर्सिव Diophantine Equations Algorithm (DEA-R) का विश्लेषण करते हैं। मानक EEA के विपरीत, जो $ax + by = \gcd(a,b)$ को हल करता है, DEA-R सीधे $ax + by = c$ को हल करने का प्रयास करता है।
- DEA-I: रिकर्सन से जुड़े स्पेस और समय ओवरहेड को समाप्त करने के लिए, वे DEA-R का एक इटरेटिव (iterative) संस्करण व्युत्पन्न करते हैं, जिसे DEA-I कहा जाता है।
- EEA-I: वे तुलना के लिए आधार रेखा (baseline) के रूप में मानक एक्सटेंडेड यूक्लिडियन एल्गोरिदम का एक इटरेटिव संस्करण (EEA-I) भी लागू करते हैं।
आवर्तता विश्लेषण (Periodicity Analysis):
- मुख्य सैद्धांतिक योगदान एक फलन $R_{a,b}(c)$ को परिभाषित करना है, जो दिए गए निश्चित $a$ और $b$ के लिए, समीकरण को हल करने के लिए आवश्यक रिकर्सिव कॉल्स (या इटरेशन) की संख्या को दर्शाता है।
- वे सिद्ध करते हैं कि $R_{a,b}(c)$ , $c$ के संबंध में एक आवर्ती फलन (periodic function) है।
- प्रमेय 1 (Theorem 1): $R_{a,b}(c)$ का मूल आवर्त (fundamental period), $a$ और $b$ के यूक्लिडियन GCD गणना के दौरान उत्पन्न होने वाले सभी मध्यवर्ती शेषफल (intermediate remainders) का लघुतम समापवर्त्य (LCM) है (विशेष रूप से $LCM(a_2, a_3, \dots, a_{k+1})$ )।
औसत मामला विश्लेषण (Average Case Analysis):
- आवर्तता का उपयोग करते हुए, लेखक रिकर्सिव कॉल्स के लिए औसत ऊपरी सीमाओं (upper bounds) को व्युत्पन्न करते हैं।
- वे इनपुट मानों पर निचली सीमाएँ (lower bounds) स्थापित करने के लिए फाइबोनैची संख्याओं (लेम्मा 1 के माध्यम से, जो यूक्लिडियन एल्गोरिदम चरणों को फाइबोनैची विकास से जोड़ता है) का उपयोग करते हैं, जिससे औसत जटिलता पर कड़े ऊपरी बंधन प्राप्त होते हैं।
- वे समाधान योग्य उदाहरणों (solvable instances) के लिए कॉल की संख्या का एक सैद्धांतिक ऊपरी बंधन व्युत्पन्न करते है: $R_{avg} \leq 2.28(\log b - 1)$ , जो EEA के मानक $\Theta(\log b)$ की तुलना में है।
सेट इंटरसेक्शन विश्लेषण (Set Intersection Analysis):
- वे $c_i$ नामक सेट परिभाषित करते हैं जिसमें वे मान $c$ शामिल हैं जो ठीक $i$ रिकर्सिव कॉल्स का परिणाम देते हैं।
- प्रमेय 2 (Theorem 2) सभी सेटों $c_1, \dots, c_k$ के प्रतिच्छेदन (intersection) में एक $c$ मान के अस्तित्व के लिए एक पर्याप्त स्थिति (sufficient condition) प्रदान करता है, जिसका अर्थ है कि एक एकल रिकर्सिव कॉल में समाधान पाया जा सकता है।

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

इटरेटिव कार्यान्वयन (DEA-I): लेखक DEA-R एल्गोरिदम का एक स्पेस-कुशल इटरेटिव कार्यान्वयन प्रदान करते हैं, जो रिकर्सिव समाधानों में निहित स्टैक ओवरहेड को हटा देता है।
आवर्तता प्रमाण (Periodicity Proof): वे औपचारिक रूप से सिद्ध करते हैं कि DEA-R द्वारा आवश्यक चरणों की संख्या $c$ के संबंध में आवर्ती है, जिसका आवर्त यूक्लिडियन शेषफल के LCM द्वारा निर्धारित होता है।
औसत मामले में सुधार (Average Case Improvement): वे प्रदर्शित करते हैं कि समाधान योग्य उदाहरणों के लिए, DEA-R/DEA-I एल्गोरिदम को एक्सटेंडेड यूक्लिडियन एल्गोरिदम की तुलना में एक कॉन्स्टेंट-टर्म सुधार (constant-term improvement) की आवश्यकता होती है। विशेष रूप से, औसत चरणों की संख्या लगभग $2.28(\log b - 1)$ है, जो EEA के $\Theta(\log b)$ से कम है।
अनुभवजन्य सत्यापन (Empirical Validation): 4096-बिट और 512-बिट पूर्णांकों पर व्यापक परीक्षण के माध्यम से, वे दिखाते हैं कि DEA-I मौजूदा इटरेटिव EEA कार्यान्वयन की तुलना में इटरेशन की औसत संख्या में बेहतर प्रदर्शन करता है।

4. परिणाम (Results)

सैद्धांतिक सीमाएँ (Theoretical Bounds): विश्लेषण पुष्टि करता है कि DEA-R के लिए औसत रिकर्सिव कॉल्स की संख्या $O(\log b)$ है, लेकिन EEA की तुलना में एक छोटा कॉन्स्टेंट फैक्टर है। समाधान योग्य इनपुट के लिए, यह EEA के $\Theta(\log b)$ की तुलना में चरणों की संख्या में एक कॉन्स्टेंट कमी है।
प्रायोगिक प्रदर्शन (Experimental Performance):
- निश्चित $a, b$ , परिवर्तनशील $c$ : जब $a$ और $b$ को स्थिर रखा गया और $c$ को परिवर्तित किया गया, तो DEA-I एल्गोरिदम ने सभी समाधान योग्य मामलों के लिए EEA-I की तुलना में लगातार कम इटरेशन की आवश्यकता दिखाई। असाधारण (unsolvable) मामलों के लिए, इटरेशन गणना समान थी।
- रैंडम इनपुट: 100,000 रैंडम 4096-बिट इनपुट पर, औसत इटरेशन थे:
  - DEA-I: 2390.2
  - EEA-2 (मानक इटरेटिव EEA): 2392
  - EEA-I: 2393
- हालांकि बड़े रैंडम सेटों पर कच्चे औसत (raw averages) में अंतर बहुत कम था, लेकिन सैद्धांतिक विश्लेषण और विशिष्ट प्लॉट्स (बदलते $c$ के साथ) ने पुष्टि की कि DEA-I कभी भी EEA-I के इटरेशन काउंट से अधिक नहीं होता है और 100% समाधान योग्य मामलों के लिए यह स्पष्ट रूप से बेहतर है।
- बिट-साइज संवेदनशीलता (Bit-Size Sensitivity): सैद्धांतिक प्लॉट्स ने दिखाया कि $b > 12$ के बिट-साइज के लिए, DEA-R एल्गोरिदम को EEA-R की तुलना में लगातार कम से कम 4.5 कम रिकर्सिव कॉल्स की आवश्यकता होती है।

5. महत्व और सीमाएँ (Significance and Limitations)

महत्व (Significance):
- यह कार्य इस धारणा को चुनौती देता है कि डायोफेंटाइन समाधान के लिए एक्सटेंडेड यूक्लिडियन एल्गोरिदम सभी औसत-मामला परिदृश्यों के लिए इष्टतम विकल्प है।
- यह $c$ के मान के आधार पर $ax+by=c$ को हल करने की लागत का विश्लेषण करने के लिए एक सैद्धांतिक ढांचा (आवर्तता और सेट इंटरसेक्शन) प्रदान करता है।
- उच्च-आवृत्ति वाले क्रिप्टोग्राफिक अनुप्रयोगों में यह कॉन्स्टेंट सुधार महत्वपूर्ण है जहाँ लाखों मॉड्यूलर इनवर्स की गणना की जाती है।
सीमाएँ और भविष्य का कार्य (Limitations & Future Work):
- अरिथमेटिक ओवरहेड (Arithmetic Overhead): लेखक नोट करते हैं कि हालांकि DEA-I कम इटरेशन करता है, लेकिन प्रत्येक इटरेशन के भीतर अंकगणितीय संचालन (जिसमें बड़े नंबर या अधिक जटिल लॉजिक शामिल हो सकते हैं) EEA की तुलना में अधिक महंगे हो सकते हैं। यदि $c$ का बिट-साइज $a$ और $b$ की तुलना में काफी बड़ा है, तो जटिलता $O(\log c)$ में बदल सकती है, जिससे लाभ समाप्त हो सकता है।
- सटीक कार्डिनैलिटी (Exact Cardinality): वर्तमान विश्लेषण सटीक औसत मानों के बजाय ऊपरी सीमाएं प्रदान करता है क्योंकि सेट $c_i$ के इंटरसेक्शन की सटीक कार्डिनैलिटी की गणना करना जटिल है।
- प्रमेय 2 की बाधाएं (Theorem 2 Constraints): "सिंगल-कॉल" समाधान के अस्तित्व के लिए शर्त (प्रमेय 2) मध्यवर्ती इनपुट के विशिष्ट GCD गुणों पर निर्भर करती है, जो सभी रैंडम इनपुट के लिए लागू नहीं हो सकती है।
- भविष्य की दिशाएं (Future Directions): लेखक DEA-R की दक्षता को अधिकतम करने के लिए इनपुट को रैंडमली चुनने वाले संभाव्य एल्गोरिदम (probabilistic algorithms) विकसित करने और GCD के साथ डायोफेंटाइन समाधान की गणना करने के तरीकों का पता लगाने का सुझाव देते हैं।

निष्कर्षतः, यह शोध पत्र स्थापित करता है कि DEA-R (और इसका इटरेटिव संस्करण DEA-I) एल्गोरिदम, विशेष रूप से समाधान योग्य मामलों के लिए, दो-चरणीय रैखिक डायोफेंटाइन समीकरणों को हल करने के लिए मानक एक्सटेंडेड यूक्लिडियन एल्गोरिदम की तुलना में औसत चरणों की संख्या में एक गणितीय रूप से सिद्ध और अनुभवजन्य रूप से देखे गए कॉन्स्टेंट-फैक्टर सुधार की पेशकश करता है।