पावर मॉड कैलकुलेटर

आधार	7
घातांक	256
मॉड्यूलस	13

पावर मॉड कैलकुलेटर क्या है?

पावर मॉड कैलकुलेटर $(\text{base}^{\text{exponent}}) \bmod m$ की गणना करता है — यानी किसी आधार (base) को एक घात (power) तक बढ़ाने और फिर मॉड्यूलस से भाग देने पर बचने वाला शेषफल। इस एक ही संक्रिया को मॉड्यूलर एक्सपोनेंशिएशन कहा जाता है, और यह संख्या सिद्धांत (number theory) तथा क्रिप्टोग्राफी में हर जगह काम आती है: RSA एन्क्रिप्शन, Diffie-Hellman की-एक्सचेंज, प्राइमलिटी टेस्ट और हैश फंक्शन — सब इसी पर टिके हैं। बड़े घातांकों के लिए इसे सीधे निकालना (पहले विशाल घात निकालना और फिर शेषफल लेना) व्यावहारिक रूप से असंभव है, इसलिए हम एक तेज़ एल्गोरिदम का सहारा लेते हैं।

$$\text{result} = \text{Base}^{\text{Exponent}} \bmod \text{Modulus}$$

इसका उपयोग कैसे करें

तीन पूर्ण संख्याएँ दर्ज करें: आधार (base), घातांक (exponent) (शून्य या धनात्मक), और मॉड्यूलस $m$ (1 से बड़ा एक धनात्मक पूर्णांक)। कैलकुलेट दबाते ही टूल $0$ से $m-1$ के बीच का परिणाम लौटा देता है। ऋणात्मक आधारों को स्वतः ही सही गैर-ऋणात्मक अवशेष (residue) में बदल दिया जाता है।

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

विशाल संख्या $\text{base}^{\text{exponent}}$ को बनाने के बजाय, कैलकुलेटर स्क्वायर-एंड-मल्टिप्लाई (जिसे बाइनरी एक्सपोनेंशिएशन भी कहते हैं) तकनीक का उपयोग करता है। यह घातांक को बाइनरी रूप में पढ़ता है। परिणाम को 1 से शुरू करते हुए, यह बार-बार आधार का वर्ग करता है (मॉड्यूलो $m$ में); और जब भी घातांक का वर्तमान बाइनरी अंक 1 होता है, तो उस वर्ग किए गए मान को चल रहे परिणाम में गुणा कर देता है — फिर से मॉड्यूलो $m$ घटाते हुए। चूँकि हर मध्यवर्ती संख्या $m^2$ से छोटी रहती है, इसलिए सैकड़ों अंकों वाले घातांकों के लिए भी यह गणना बहुत तेज़ होती है।

वर्ग और गुणा मॉड्यूलर घातांक एल्गोरिदम का फ़्लोचार्ट — वर्ग करो और गुणा करो: घातांक के बिट्स को स्कैन करें, हर चरण में वर्ग करें और बिट 1 होने पर गुणा करें, पूरे समय मॉड $m$ से कम करते रहें।

हल किया गया उदाहरण

आइए $7^{256} \bmod 13$ निकालें। 13 के सापेक्ष 7 का क्रम (order) 12 को विभाजित करता है, और $7^{12} \equiv 1$ होता है। चूँकि $256 = 12 \times 21 + 4$, इसलिए $$7^{256} \equiv 7^{4} = 2401 \equiv 9 \pmod{13}$$ यानी उत्तर है 9 — और यह यहाँ तुरंत मिल जाता है, बिना कभी 217 अंकों वाली विशाल संख्या $7^{256}$ बनाए।

बार-बार वर्ग करके आधार^घातांक मॉड m की गणना की चरण तालिका — हर चरण वर्तमान मान का वर्ग करके मॉड $m$ से कम करता है, और जहाँ घातांक बिट सेट हो वहाँ आधार से गुणा करता है।

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

अगर मॉड्यूलस 1 हो तो? हर पूर्णांक मॉड्यूलो 1 में 0 के सर्वांगसम (congruent) होता है, इसलिए परिणाम 0 आता है।

क्या घातांक 0 हो सकता है? हाँ। किसी भी आधार की घात 0 का मान 1 होता है, इसलिए परिणाम $1 \bmod m$ होता है (जो $m > 1$ होने पर 1 ही रहता है)।

घात को सीधे ही क्यों न निकालें? बड़े घातांकों के लिए मध्यवर्ती संख्या में इतने अधिक अंक होंगे कि वह ओवरफ़्लो कर जाएगी। हर चरण पर मॉड्यूलर रिडक्शन करने से मान छोटे रहते हैं और तरीका कुशल बना रहता है।