विस्तारित यूक्लिडियन एल्गोरिथम कैलकुलेटर
GCD · बेज़ौत गुणांक · मॉड्यूलर व्युत्क्रम
पूर्णांक s और t के साथ GCD(a, b) की गणना करें जो समीकरण s·a + t·b = GCD को संतुष्ट करते हैं। सह-अभाज्य होने पर पूर्ण पुनरावृत्ति तालिका और मॉड्यूलर व्युत्क्रम भी प्राप्त करें।
त्वरित उदाहरण (Quick Examples)
बेज़ौत की पहचान का सत्यापन (Bézout's Identity Verification)
मॉड्यूलर व्युत्क्रम विवरण (Modular Inverse Details)
चरण-दर-चरण पुनरावृत्ति तालिका (Step-by-Step Iteration Table)
प्रत्येक पंक्ति: भाज्य (dividend) = भागफल (quotient) × भाजक (divisor) + शेषफल (remainder)। हाइलाइट की गई पंक्ति वह है जहाँ शेषफल पहली बार 0 हो जाता है — GCD उस पंक्ति का भाजक है।
| चरण | भाज्य (Dividend) | भाजक (Divisor) | भागफल (Quotient) | शेषफल (Remainder) | s | t |
|---|
बैक-सबस्टीट्यूशन व्याख्या (Back-Substitution Explanation)
RSA क्रिप्टोग्राफी (RSA Cryptography)
मॉड्यूलर व्युत्क्रम के माध्यम से कुंजी जनरेशन
RSA में, n = p × q और पब्लिक एक्सपोनेंट e के लिए कुंजियों को जनरेट करने के लिए, प्राइवेट एक्सपोनेंट d को e × d ≡ 1 (mod λ(n)) को संतुष्ट करना आवश्यक है। विस्तारित यूक्लिडियन एल्गोरिथम इस मॉड्यूलर व्युत्क्रम की कुशलतापूर्वक गणना करता है।
GCD(17, 3120) = 1 (सह-अभाज्य — व्युत्क्रम मौजूद है)
विस्तारित GCD → d = 17⁻¹ mod 3120
17 × 2753 = 46801 = 15 × 3120 + 1 ≡ 1 (mod 3120)
∴ प्राइवेट कुंजी d = 2753
रैखिक डायोफैंटाइन समीकरणों को हल करना
ax + by = c के पूर्णांक समाधान
समीकरण ax + by = c के पूर्णांक समाधान केवल तभी होते हैं जब GCD(a, b) संख्या c को विभाजित करता है। विस्तारित यूक्लिडियन एल्गोरिथम एक विशिष्ट समाधान (x₀, y₀) देता है, जिससे सामान्य समाधान प्राप्त किया जा सकता है।
x = x₀ × (c / GCD) + k × (b / GCD)
y = y₀ × (c / GCD) − k × (a / GCD) किसी भी पूर्णांक k के लिए
क्रिप्टोग्राफिक कुंजी एक्सचेंज (Key Exchange)
डिफी-हेलमैन और अलगामल आधार
डिफी-हेलमैन और अलगामल (Diffie-Hellman & ElGamal) चक्रीय समूहों में मॉड्यूलर अंकगणित पर निर्भर करते हैं। डिक्रिप्शन के लिए मॉड्यूलर व्युत्क्रम की गणना आवश्यक है — उदाहरण के लिए अलगामल डिक्रिप्शन में s⁻¹ mod p की गणना, जहां s साझा गुप्त कुंजी है।
विस्तारित GCD(s, p) के माध्यम से व्युत्क्रम की गणना
चूंकि p अभाज्य है, GCD(s, p) = 1 हमेशा लागू होता है (s < p)
∴ अभाज्य मोड्यूली के लिए s⁻¹ mod p हमेशा अस्तित्व में रहता है
विस्तारित यूक्लिडियन एल्गोरिथम क्या है?
विस्तारित यूक्लिडियन एल्गोरिथम (Extended Euclidean Algorithm) शास्त्रीय यूक्लिडियन एल्गोरिथम का एक महत्वपूर्ण विस्तार है। जहां मूल यूक्लिडियन एल्गोरिथम बार-बार विभाजन के माध्यम से दो पूर्णांकों a और b के महत्तम समापवर्तक (GCD) को खोजता है, वहीं विस्तारित संस्करण एक साथ दो पूर्णांक गुणांकों s और t की गणना करता है — जिन्हें बेज़ौत गुणांक (Bézout coefficients) कहा जाता है — जो इस रैखिक समीकरण को संतुष्ट करते हैं:
s · a + t · b = GCD(a, b)
इस समीकरण को बेज़ौत की पहचान (Bézout's Identity) के रूप में जाना जाता है। यह सिद्धांत गारंटी देता है कि किसी भी दो पूर्णांकों के लिए ऐसे गुणांक हमेशा मौजूद रहते हैं। विस्तारित एल्गोरिथम इसे GCD गणना में अतिरिक्त विभाजनों के बिना प्राप्त कर लेता है।
बेज़ौत की पहचान की व्याख्या
बेज़ौत का प्रमेय (Bézout's Lemma) बताता है: यदि दो पूर्णांकों a और b का GCD(a, b) = d है, तो ऐसे पूर्णांक s और t मौजूद होते हैं जिनके लिए s · a + t · b = d हो। इसके अतिरिक्त, d वह सबसे छोटा सकारात्मक पूर्णांक है जिसे a और b के रैखिक संयोजन के रूप में लिखा जा सकता है।
बेज़ौत गुणांक अद्वितीय (unique) नहीं होते हैं। यदि (s, t) एक समाधान है, तो किसी भी पूर्णांक k के लिए (s + k · (b/d), t − k · (a/d)) भी एक वैध समाधान होगा। यह कैलकुलेटर सबसे कम निरपेक्ष मान वाले गुणांक प्रदान करता है।
एल्गोरिथम की चरण-दर-चरण कार्यप्रणाली
यह एल्गोरिथम बुनियादी GCD की तरह ही विभाजन लूप चलाता है, लेकिन दो अतिरिक्त अनुक्रमों (si) और (ti) को ट्रैक करता है जो हर चरण में ri = si · a + ti · b को संतुष्ट करते हैं। इसका आवर्ती संबंध (recurrence) इस प्रकार है:
- ri+1 = ri-1 − qi × ri (मानक GCD चरण)
- si+1 = si-1 − qi × si
- ti+1 = ti-1 − qi × ti
शुरुआती मानों (r₀, s₀, t₀) = (a, 1, 0) और (r₁, s₁, t₁) = (b, 0, 1) से शुरू करके, एल्गोरिथम तब समाप्त होता है जब ri = 0 हो। अंतिम गैर-शून्य शेषफल (ri-1) ही GCD होता है, और उसके साथ वाले गुणांक (si-1, ti-1) बेज़ौत गुणांक होते हैं।
समय जटिलता (Time Complexity) — लामे का प्रमेय
विस्तारित यूक्लिडियन एल्गोरिथम की समय जटिलता O(log min(a, b)) होती है। यह सीधे बुनियादी यूक्लिडियन एल्गोरिथम की जटिलता से मेल खाती है। लामे का प्रमेय (Lamé's Theorem) (1844) सिद्ध करता है कि विभाजन चरणों की संख्या छोटे इनपुट के दशमलव अंकों की संख्या के 5 गुना से अधिक नहीं हो सकती। चूंकि प्रत्येक चरण में केवल गुणांकों को अपडेट करने के लिए निरंतर कार्य (Constant Work) किया जाता है, इसलिए कुल जटिलता O(log min(a, b)) ही रहती है।
विस्तारित GCD के माध्यम से मॉड्यूलर व्युत्क्रम (Modular Inverse)
इसका सबसे महत्वपूर्ण अनुप्रयोग मॉड्यूलर व्युत्क्रम (Modular Inverse) की गणना करना है। a modulo m का मॉड्यूलर व्युत्क्रम (जिसे a⁻¹ mod m लिखा जाता है) एक ऐसा पूर्णांक x है जिसके लिए a × x ≡ 1 (mod m) हो। यह केवल तभी संभव है जब GCD(a, m) = 1 हो (यानी वे सह-अभाज्य हों)।
जब GCD(a, m) = 1 हो, तो विस्तारित यूक्लिडियन एल्गोरिथम से s · a + t · m = 1 प्राप्त होता है। Modulo m करने पर: s · a ≡ 1 (mod m), जिससे a⁻¹ mod m = s mod m मिलता है (यदि s नकारात्मक है तो सकारात्मक बनाने के लिए m जोड़ दिया जाता है)।