a^b की गणना करके फिर mod लेना क्यों काम नहीं करता?

बड़े घातांकों (जैसे b = 10^1000) के लिए a^b में खगोलीय रूप से कई अंक होते हैं — किसी भी computer में संग्रहीत होने से कहीं अधिक। Square-and-multiply algorithm हर multiplication के बाद mod m लेकर intermediate values को छोटा रखता है, किसी भी संख्या को m^2 से अधिक नहीं बढ़ने देता।

ⁿ

मॉड्यूलर घातांक कैलकुलेटर

Square-and-Multiply · BigInt Support · RSA · Diffie-Hellman

Fast binary (right-to-left) algorithm का उपयोग करके arbitrarily large integers के लिए a^b mod m की गणना करें। चरण-दर-चरण तालिका, binary विज़ुअलाइज़ेशन, और cryptographic अनुप्रयोग।

त्वरित उदाहरण (Quick Examples)

आधार (a)

घातांक (b)

Modulus (m > 1)

a^b mod m

—

अंतिम परिणाम

b binary में

—

binary प्रतिनिधित्व

Squarings

—

⌊log₂ b⌋ चरण

Multiplications

—

popcount(b) − 1

b का Binary प्रतिनिधित्व

हरा = bit 1 (multiply & square)। धूसर = bit 0 (केवल square)। LSB बाईं ओर, MSB दाईं ओर। 32 bits तक सीमित।

एल्गोरिदम अवलोकन

...

चरण-दर-चरण Squaring तालिका

b के LSB से MSB तक columns process किए जाते हैं। हरी पंक्तियाँ: bit = 1, result पर multiplication लागू। धूसर पंक्तियाँ: bit = 0, केवल squaring।

चरण	Bit (LSB→MSB)	Current Base a^{2^k} mod m	Result	Operation

🔒

RSA Encryption और Decryption

मॉड्यूलर घातांक के माध्यम से public-key cryptography

RSA एक message M को C = M^e mod n के रूप में encrypt करता है। Decryption M = C^d mod n के माध्यम से M recover करती है। दोनों operations बिल्कुल मॉड्यूलर घातांक हैं।

Toy RSA उदाहरण (p=11, q=13, n=143): φ(n) = (p-1)(q-1) = 10×12 = 120 Public exponent: e = 7 (gcd(7,120)=1) Private exponent: d = 103 (7×103 = 721 = 6×120+1 ≡ 1 mod 120) Encrypt M=2: C = 2^7 mod 143 = 128 Decrypt C=128: M = 128^103 mod 143 = 2 ✓

इसे आज़माएं: calculator में Quick Example "2¹⁰³ mod 143 (toy RSA)" उपयोग करें।

🔑

Diffie-Hellman Key Exchange

असुरक्षित channel पर shared secret

Alice और Bob एक prime p और generator g पर सहमत होते हैं। Alice A = g^a mod p और Bob B = g^b mod p compute करते हैं। Shared key K = g^ab mod p है।

उदाहरण: p=23, g=5 Alice का secret a=6: A = 5^6 mod 23 = 8 Bob का secret b=15: B = 5^15 mod 23 = 19 Shared key (Alice): K = B^a mod p = 19^6 mod 23 = 2 Shared key (Bob): K = A^b mod p = 8^15 mod 23 = 2 ✓

Security: A = g^a mod p से a ज्ञात करना discrete logarithm problem है — large p के लिए computationally hard।

𝕧

Fermat Primality Test

मॉड्यूलर घातांक का उपयोग करके probabilistic prime detection

Fermat का छोटा प्रमेय: यदि p prime है और gcd(a, p) = 1, तो a^p-1 ≡ 1 (mod p)। Fermat primality test कई random bases के लिए इस शर्त की जाँच करता है।

p=17 की primality test: a=3 चुनें: 3^16 mod 17 = 1 ✓ (prime के अनुरूप) a=5 चुनें: 5^16 mod 17 = 1 ✓ (prime के अनुरूप) p=15 (composite) a=2 के साथ: 2^14 mod 15 = 4 ≠ 1 → 15 prime नहीं है ✓

मॉड्यूलर घातांक (Modular Exponentiation) क्या है?

मॉड्यूलर घातांक a^b mod m की गणना है — आधार a को घातांक b तक उठाना और modulus m से विभाजित करने पर शेष रखना। यह operation आधुनिक संख्या सिद्धांत और public-key cryptography की आधारशिला है। a और b कितने भी बड़े हों, परिणाम हमेशा [0, m−1] श्रेणी में एक पूर्णांक होता है।

उदाहरण के लिए, 3⁶⁴⁴ mod 645 = 36। जबकि intermediate value 3⁶⁴⁴ एक astronomically large संख्या है (300 से अधिक decimal digits), उत्तर केवल 36 है।

Naive Computation क्यों विफल होती है

सीधा approach — पहले a^b compute करें, फिर remainder लें — बड़े exponents के लिए पूरी तरह अव्यावहारिक है। 2¹⁰⁰⁰ में पहले से 300 से अधिक decimal digits हैं। RSA हजारों bits के exponents का उपयोग करता है, इसलिए naive intermediate value में observable universe के atoms से अधिक digits होंगे।

मुख्य insight यह है कि हम हर single multiplication के बाद mod m reduce कर सकते हैं, सभी intermediate values को m² से नीचे रख सकते हैं। इसे square-and-multiply trick के साथ combine करने से O(b) multiplications घटकर O(log b) हो जाते हैं।

Square-and-Multiply (Binary Exponentiation) Algorithm

एल्गोरिदम b के binary प्रतिनिधित्व को LSB से MSB तक process करता है। चरण k (b के bit k के अनुरूप) पर:

हमेशा square करें: base = base × base mod m compute करें (यह positional value 2^k के लिए account करता है)
यदि bit k = 1: result = result × base mod m भी multiply करें
यदि bit k = 0: multiplication छोड़ें

O(log b) Complexity

एल्गोरिदम ठीक ⌊log₂ b⌋ squarings और (popcount(b) − 1) multiplications करता है। चूँकि दोनों O(log b) हैं, modular multiplications की कुल संख्या O(log b) है। प्रत्येक multiplication में m² आकार की संख्याएं शामिल हैं, इसलिए total bit complexity O(log b × (log m)²) है।

2048-bit RSA parameters के लिए इसका मतलब लगभग 2000 multiplications है — किसी भी आधुनिक processor पर milliseconds में पूरी तरह feasible।

RSA Encryption और Decryption

RSA सबसे व्यापक रूप से deploy किया गया public-key cryptosystem है। Key generation दो large primes p और q का चयन करती है, n = p × q compute करती है, और public exponent e को φ(n) = (p−1)(q−1) के coprime चुनती है।

Encryption: C = M^e mod n
Decryption: M = C^d mod n

दोनों operations pure modular exponentiation हैं। RSA की security इस fact पर निर्भर है कि n को factor करना computationally hard है।

Diffie-Hellman Key Exchange

Diffie-Hellman (1976) पहला practical public-key cryptographic protocol था। दो parties publicly एक large prime p और primitive root g पर सहमत होते हैं। Shared secret g^ab mod p है, जिसे प्रत्येक party दूसरे के public value से compute करती है। एक eavesdropper जो दोनों public values देखता है, discrete logarithm problem को हल किए बिना shared secret compute नहीं कर सकता।

Fermat का छोटा प्रमेय

Fermat का छोटा प्रमेय कहता है: यदि p prime है और gcd(a, p) = 1, तो a^p−1 ≡ 1 (mod p)। यह primality के लिए एक आवश्यक शर्त है (हालांकि पर्याप्त नहीं — Carmichael numbers इसे सभी bases के लिए satisfy करते हैं जबकि composite होते हैं)।

संदर्भ तालिका: उदाहरण गणनाएँ

a	b	m	a^b mod m	b binary में	Squarings
3	644	645	36	1010000100	9
2	10	1000	24	1010	3
7	256	13	9	100000000	8
2	103	143	2	1100111	6
5	6	23	8	110	2
123	456	789	699	111001000	8

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

मॉड्यूलर घातांक क्या है?

मॉड्यूलर घातांक a^b mod m की गणना है — आधार a को घातांक b तक उठाना और m से विभाजित करने पर remainder लेना। परिणाम हमेशा [0, m−1] में होता है। यह RSA, Diffie-Hellman, ElGamal, और कई primality tests में central operation है।

a^b compute करके फिर mod लेना क्यों काम नहीं करता?

Large exponents (RSA में 65537 या अधिक) के लिए a^b में millions digits होते हैं। कोई computer इसे store नहीं कर सकता। Square-and-multiply algorithm प्रत्येक multiplication के बाद mod m reduce करता है, intermediate values को m² से नीचे रखता है, इसलिए सभी arithmetic tractable रहता है।

Square-and-Multiply एल्गोरिदम कैसे काम करता है?

एल्गोरिदम b के binary digits को LSB से MSB तक scan करता है। प्रत्येक चरण k पर: (1) current base को mod m square करें। (2) यदि b का bit k 1 है, तो running result को current base से mod m multiplied करें। यह binary decomposition b = ∑ b_k × 2^k का उपयोग करता है।

मॉड्यूलर घातांक की time complexity क्या है?

एल्गोरिदम O(log b) modular multiplications का उपयोग करता है — ⌊log₂ b⌋ squarings और अधिकतम ⌊log₂ b⌋ extra multiplications। m से कम numbers पर प्रत्येक multiplication का cost O((log m)²) bit operations है, जो total bit complexity O(log b × (log m)²) देता है।

RSA में मॉड्यूलर घातांक का उपयोग कैसे होता है?

RSA encryption C = M^e mod n है और decryption M = C^d mod n है। दोनों modular exponentiation हैं। Exponents e और d large integers हैं (real usage में क्रमशः 17 bits और 2048 bits)। Square-and-multiply algorithm इन operations को इतना fast बनाता है कि वे practical हों।

Fermat का छोटा प्रमेय क्या है?

Fermat का छोटा प्रमेय कहता है कि यदि p prime है और gcd(a, p) = 1, तो a^p-1 ≡ 1 (mod p)। यह RSA के लिए मौलिक है (exponent को mod (p-1)(q-1) चुना जाता है) और Miller-Rabin primality test को underpin करता है। यह primality की आवश्यक शर्त है लेकिन पर्याप्त नहीं।

Diffie-Hellman key exchange क्या है?

Diffie-Hellman एक cryptographic protocol है जो दो parties को असुरक्षित channel पर shared secret establish करने देता है। Alice secret a चुनकर A = g^a mod p भेजती है। Bob secret b चुनकर B = g^b mod p भेजता है। Shared key g^ab mod p है। Security discrete logarithm problem पर निर्भर करती है — carefully chosen p और g के लिए computationally hard।

मॉड्यूलर घातांक कैलकुलेटर

b का Binary प्रतिनिधित्व

एल्गोरिदम अवलोकन

Fermat के छोटे प्रमेय की जाँच

चरण-दर-चरण Squaring तालिका

RSA Encryption और Decryption

Diffie-Hellman Key Exchange

Fermat Primality Test

मॉड्यूलर घातांक (Modular Exponentiation) क्या है?

Naive Computation क्यों विफल होती है

Square-and-Multiply (Binary Exponentiation) Algorithm

O(log b) Complexity

RSA Encryption और Decryption

Diffie-Hellman Key Exchange

Fermat का छोटा प्रमेय

संदर्भ तालिका: उदाहरण गणनाएँ

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

संबंधित कैलकुलेटर