मॉड्यूलर इन्वर्स कैलकुलेटर

मॉड्यूलर इन्वर्स कैलकुलेटर

लोकप्रिय AI Skill PRO

गणना दर्ज करें

परिणाम

मॉड्यूलर प्रतिलोम
4
वह x जहाँ (a·x) mod m = 1 हो
प्रतिलोम मौजूद है हाँ
gcd(a, m) 1

सूत्र (फॉर्मूला)

a·x≡1(modm)⟹x=a−1modm\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}
उपयोग आँकड़े

विज्ञापन

इस पेज पर त्रुटि की रिपोर्ट करें

मॉड्यूलर इन्वर्स क्या होता है?

किसी पूर्णांक a का मॉड्यूलो m के सापेक्ष मॉड्यूलर गुणात्मक प्रतिलोम वह पूर्णांक x होता है जिसके लिए \((a \cdot x) \bmod m = 1\) सही हो। आसान शब्दों में, यह मॉड्यूलर अंकगणित में "भाग" करने का तरीका है और यह संख्या सिद्धांत (number theory), RSA क्रिप्टोसिस्टम तथा कोडिंग थ्योरी के कई एल्गोरिदम का आधार है। यह कैलकुलेटर एक्सटेंडेड यूक्लिडियन एल्गोरिदम की मदद से x की गणना करता है।

$$\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}$$

घड़ी जैसी गोलाकार मॉड्यूलस रिंग के चारों ओर लिपटी संख्या रेखा, जिसमें a गुणा x 1 पर पहुँचता है
मॉड्यूलर प्रतिलोम x गुणा करने पर a को वापस 1 पर लाता है, मॉड्यूलस m के चारों ओर घूमते हुए।

इस कैलकुलेटर का इस्तेमाल कैसे करें

संख्या a और मॉड्यूलस m दर्ज करें (जहाँ \(m \geq 2\) हो)। यह टूल \(0 \leq x < m\) की सीमा में सबसे छोटा अऋणात्मक प्रतिलोम x लौटाता है, यह बताता है कि प्रतिलोम मौजूद है या नहीं, और साथ में \(\gcd(a, m)\) भी दिखाता है। अगर \(\gcd(a, m) \neq 1\) हो, तो कोई प्रतिलोम मौजूद नहीं होता और परिणाम "None" के रूप में दिखाया जाता है।

सूत्र को समझें

प्रतिलोम केवल तभी मौजूद होता है जब \(\gcd(a, m) = 1\) हो, यानी a और m सहअभाज्य (coprime) हों। एक्सटेंडेड यूक्लिडियन एल्गोरिदम ऐसे पूर्णांक x और y खोजता है जो \(a \cdot x + m \cdot y = \gcd(a, m)\) को संतुष्ट करते हैं। जब gcd 1 हो, तो x को मॉड्यूलो m से घटाकर (reduce करके) प्रतिलोम मिल जाता है। अगर परिणाम ऋणात्मक आए, तो उसमें m जोड़कर उसे धनात्मक मान में बदल दिया जाता है।

विज्ञापन
विस्तारित यूक्लिडियन एल्गोरिदम के चरणों का सपाट फ़्लोचार्ट जो gcd और गुणांक उत्पन्न करता है
विस्तारित यूक्लिडियन एल्गोरिदम ऐसे गुणांक देता है जो \(\gcd(a, m) = 1\) होने पर प्रतिलोम देते हैं।

हल किया हुआ उदाहरण

3 का मॉड्यूलो 11 के सापेक्ष प्रतिलोम निकालिए। हमें ऐसा x चाहिए जहाँ \(3x \equiv 1 \pmod{11}\) हो। जाँच करने पर, \(3 \times 4 = 12 = 11 + 1\), यानी \(12 \bmod 11 = 1\)। इसलिए \(x = 4\)। एक्सटेंडेड यूक्लिडियन एल्गोरिदम भी यही मान देता है, और \(\gcd(3, 11) = 1\) है, जिससे पुष्टि होती है कि प्रतिलोम मौजूद है।

चरण-दर-चरण: हाथ से विस्तारित यूक्लिड एल्गोरिदम

a का मॉड्यूलो m व्युत्क्रम वह संख्या x है जिसके लिए \(a \cdot x \equiv 1 \pmod{m}\) हो। यह तभी मौजूद होता है जब \(\gcd(a, m) = 1\) हो। विस्तारित यूक्लिड एल्गोरिदम इसे तीन चरणों में खोजता है।

  1. बार-बार भाग। m को a से भाग दें, फिर पिछले भाजक को शेषफल से भाग दें, और इसी तरह तब तक करते रहें जब तक शेषफल 0 न हो जाए। अंतिम शून्येतर शेषफल gcd है। यदि यह 1 नहीं है, तो कोई व्युत्क्रम मौजूद नहीं है।
  2. 1 को एक संयोजन के रूप में लिखें। पीछे की ओर काम करें (बैक-सब्स्टिट्यूशन), या चलते-चलते गुणांक ट्रैक करें, ताकि \(1 = a \cdot x + m \cdot y\) लिखा जा सके। यह बेज़ू तत्समक (Bézout identity) है।
  3. x को घटाएँ। \(x \bmod m\) लें। यदि x ऋणात्मक है, तो m जोड़ें (आवश्यकता हो तो दोहराएँ) ताकि परिणाम 0 से m − 1 की सीमा में आ जाए।

कार्य किया हुआ उदाहरण: a = 7, m = 40.

चरण भाग भागफल q शेषफल
1 40 = 5·7 + 5 5 5
2 7 = 1·5 + 2 1 2
3 5 = 2·2 + 1 2 1
4 2 = 2·1 + 0 2 0

अंतिम शून्येतर शेषफल 1 है, इसलिए \(\gcd(7, 40) = 1\) और एक व्युत्क्रम मौजूद है।

बैक-सब्स्टिट्यूशन:

$$1 = 5 - 2\cdot 2 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7 = 3(40 - 5\cdot 7) - 2\cdot 7 = 3\cdot 40 - 17\cdot 7$$

तो \(7 \cdot (-17) + 40 \cdot 3 = 1\), जिससे \(x = -17\) मिलता है।

पुनरावृत्त जाँच (a का गुणांक t): \(t_0 = 0\) (m = 40 के लिए) और \(t_1 = 1\) (a = 7 के लिए) से शुरू करें, फिर \(t_{k+1} = t_{k-1} - q_k \, t_k\) का उपयोग करें।

शेषफल प्रयुक्त q t
40 – 0
7 – 1
5 5 0 − 5·1 = −5
2 1 1 − 1·(−5) = 6
1 2 −5 − 2·6 = −17

जिस पंक्ति में शेषफल 1 पहुँचता है, वहाँ \(t = -17\) मिलता है। इसे घटाएँ: \(-17 + 40 = \)23.

सत्यापन: \(7 \cdot 23 = 161 = 4 \cdot 40 + 1\), इसलिए \(161 \bmod 40 = 1\)। ✓

यही विधि बड़ी संख्याओं पर भी काम करती है। a = 17, m = 3120 के लिए यह x = 2753 देती है, क्योंकि \(17 \cdot 2753 = 46801 = 15 \cdot 3120 + 1\)। यह युग्म एक क्लासिक पाठ्यपुस्तक RSA उदाहरण है।

उदाहरण इनपुट और उनके व्युत्क्रम

नीचे दिया प्रत्येक व्युत्क्रम \((a \cdot x) \bmod m = 1\) को संतुष्ट करता है। जब \(\gcd(a, m) > 1\) हो, तो कोई व्युत्क्रम मौजूद नहीं होता।

a m gcd(a, m) व्युत्क्रम x जाँच
3 11 1 4 3·4 = 12 = 1·11 + 1
7 26 1 15 7·15 = 105 = 4·26 + 1
5 12 1 5 5·5 = 25 = 2·12 + 1
10 17 1 12 10·12 = 120 = 7·17 + 1
17 3120 1 2753 17·2753 = 46801 = 15·3120 + 1
4 6 2 कोई नहीं 4x mod 6 हमेशा सम होता है, कभी 1 नहीं
6 9 3 कोई नहीं 6x mod 9 हमेशा 3 का गुणज होता है, कभी 1 नहीं

ध्यान दें कि 12 के मॉड्यूलो में 5 स्वयं अपना व्युत्क्रम है। सामान्यतः \(x^2 \equiv 1 \pmod{m}\) के 1 के अलावा अन्य हल भी होते हैं, इसलिए कुछ संख्याएँ स्व-व्युत्क्रम होती हैं।

विज्ञापन

मुख्य शब्द: सहअभाज्य, GCD, सर्वसमता और अवशेष

  • मॉड्यूलस (m): वह धनात्मक पूर्णांक जिस पर मान घूम कर वापस आते हैं, जैसे घड़ी के डायल पर।
  • सर्वसमता (≡): \(a \equiv b \pmod{m}\) का अर्थ है कि m, \(a - b\) को विभाजित करता है, इसलिए a और b को m से भाग देने पर समान शेषफल मिलता है।
  • GCD: महत्तम समापवर्तक, वह सबसे बड़ा पूर्णांक जो दोनों संख्याओं को विभाजित करता है।
  • सहअभाज्य (आपेक्षिक अभाज्य): दो पूर्णांक जिनका gcd 1 है। मॉड्यूलर व्युत्क्रम के मौजूद होने की यही ठीक शर्त है।
  • बेज़ू तत्समक: पूर्णांक a और m के लिए ऐसे पूर्णांक x और y होते हैं कि \(a \cdot x + m \cdot y = \gcd(a, m)\)। जब gcd 1 हो, तो इस समीकरण को m के मॉड्यूलो में घटाने पर \(a \cdot x \equiv 1\) मिलता है, इसलिए x व्युत्क्रम है।
  • अवशेष वर्ग: वे सभी पूर्णांक जिनका m के मॉड्यूलो समान शेषफल हो। व्युत्क्रम एक अवशेष वर्ग के रूप में अद्वितीय है, और कैलकुलेटर 0 से m − 1 के बीच का प्रतिनिधि दिखाता है।
  • मॉड्यूलर गुणक व्युत्क्रम: अवशेष \(x = a^{-1} \bmod m\) जिसके लिए \(a \cdot x \equiv 1 \pmod{m}\) हो।

आइलर का प्रमेय: यदि \(\gcd(a, m) = 1\) हो, तो \(a^{\varphi(m)} \equiv 1 \pmod{m}\), जहाँ \(\varphi\) आइलर का टोटिएंट फ़ंक्शन है। इसलिए व्युत्क्रम को \(a^{\varphi(m)-1} \bmod m\) के रूप में भी निकाला जा सकता है।

फ़र्मा का छोटा प्रमेय: जब m = p अभाज्य हो, तो \(\varphi(p) = p - 1\) होता है, इसलिए p से विभाज्य न होने वाले किसी भी a के लिए \(a^{-1} \equiv a^{p-2} \pmod{p}\)। उदाहरण: \(3^{9} = 19683 = 1789 \cdot 11 + 4\), इसलिए \(3^{-1} \equiv 4 \pmod{11}\), जो ऊपर की तालिका से मेल खाता है। घात सूत्र के लिए m का गुणनखंडन चाहिए (ताकि \(\varphi\) मिले), जबकि विस्तारित यूक्लिड एल्गोरिदम को इसकी आवश्यकता नहीं होती, इसलिए सामान्य मॉड्यूलस के लिए यह आमतौर पर तेज़ तरीका है।

अक्सर पूछे जाने वाले सवाल

प्रतिलोम कब मौजूद नहीं होता? जब a और m में 1 से बड़ा कोई सार्व गुणनखंड (common factor) हो — उदाहरण के लिए 4 मॉड्यूलो 6 (\(\gcd = 2\)) का कोई प्रतिलोम नहीं होता।

क्या m का अभाज्य (prime) होना ज़रूरी है? नहीं। m कोई भी पूर्णांक \(\geq 2\) हो सकता है; मायने सिर्फ़ इस बात की रखती है कि a और m सहअभाज्य हों।

उत्तर किस सीमा में आता है? प्रतिलोम सबसे छोटे अऋणात्मक शेषफल के रूप में दिया जाता है, यानी 0 और \(m - 1\) के बीच।

अंतिम अपडेट:

गणित और सांख्यिकी में सबसे लोकप्रिय

गणित और सांख्यिकी के सभी कैलकुलेटर देखें