संख्या सिद्धांत और मॉड्यूलर अंकगणित: चरण-दर-चरण हल सहित अभ्यास प्रश्न
आरेखों, संकेतों और पूर्ण हल के साथ मुफ़्त संख्या सिद्धांत और मॉड्यूलर अंकगणित अभ्यास प्रश्न। हर बार नए मान, तीन स्तरों पर: gcd और शेषफल, प्रतिलोम और सर्वांगसमताएँ, मॉड्यूलर घात और RSA।
मुफ़्त अभ्यास प्रश्नआसान
942 mod 11 ज्ञात करें, वह शेषफल r जिसके लिए 0 ≤ r < 11।
संख्या सिद्धांत और मॉड्यूलर अंकगणित के प्रश्न कैसे हल करें
पहले हर संख्या को n के मापांक में घटाएँ; शेषफल 0 से n − 1 के बीच होते हैं।
gcd के लिए यूक्लिड एल्गोरिथ्म से बार-बार भाग दें; अंतिम अशून्य शेषफल ही gcd है।
प्रतिलोम के लिए विस्तारित एल्गोरिथ्म चलाएँ और a का गुणांक रखें; ऋणात्मक हो तो n जोड़ें।
a·x ≡ b को हल करने के लिए a⁻¹ से गुणा करें; दो सर्वांगसमताओं को x = r₁ + m₁k लिखकर मिलाएँ।
घातों के लिए घातांक को द्विआधारी में लिखें और बार-बार वर्ग करें; RSA में d = e⁻¹ mod φ(n) होता है, जहाँ φ(n) = (p − 1)(q − 1)।
सामान्य गलतियाँ
ऋणात्मक संख्या के लिए ऋणात्मक शेषफल देना।
यूक्लिड के एल्गोरिथ्म को पहले शेषफल पर ही रोक देना।
प्रतिलोम में n जोड़ने की जगह उसे ऋणात्मक छोड़ देना।
RSA घातांक d को φ(n) के बजाय n के मापांक में लेना।
फर्मा प्रमेय में घातांक को p − 1 की जगह p के मापांक में घटाना।
मुख्य सूत्र
शेषफल सहित विभाजन
a = q·n + r, 0 ≤ r < n
यूक्लिड
gcd(a, b) = gcd(b, a mod b)
लघुत्तम समापवर्त्य
lcm(a, b) = a·b/gcd(a, b)
व्युत्क्रम
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
रैखिक सर्वांगसमता
a·x ≡ b → x ≡ a⁻¹·b (mod n)
यूलर का टोशेंट
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
फर्मा
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
संख्या सिद्धांत और मॉड्यूलर अंकगणित शुरू से सीखें
1शेषफल और सर्वांगसमताएँ
a को n से भाग देने पर भागफल q और शेषफल r मिलता है: a = q·n + r, जहाँ 0 ≤ r < n। शेषफल को a mod n लिखा जाता है। ऋणात्मक संख्या के लिए q भी ऋणात्मक होता है: −3 = −1·7 + 4, इसलिए −3 mod 7 = 4।
दो संख्याएँ n के मापांक में सर्वांगसम होती हैं, a ≡ b (mod n), जब उनका शेषफल समान हो, अर्थात जब n, a − b को विभाजित करे।
शेषफलों को हर चरण पर घटाया जा सकता है, जिससे संख्याएँ छोटी रहती हैं:
(a + b) mod n = ((a mod n) + (b mod n)) mod n, और a·b के लिए भी यही
उदाहरण के लिए 47·58 mod 9: 47 ≡ 2 और 58 ≡ 4, इसलिए 47·58 ≡ 8 (mod 9)।
स्व-जाँच −17 mod 5 क्या है?
2
3
−2
−3
उत्तर: 3. −17 = −4·5 + 3, इसलिए शेषफल 3 है। उत्तर 2 तो 17 mod 5 है; शेषफल कभी ऋणात्मक नहीं होता।
2यूक्लिड का एल्गोरिथ्म
महत्तम समापवर्तक gcd(a, b) वह सबसे बड़ी संख्या है जो दोनों को विभाजित करती है। यूक्लिड का एल्गोरिथ्म gcd(a, b) = gcd(b, a mod b) का उपयोग करता है:
भाग दें: a = q·b + r।
(a, b) को (b, r) से बदलें।
शेषफल 0 होने तक दोहराएँ। अंतिम अशून्य शेषफल ही gcd है।
लघुत्तम समापवर्त्य इससे मिलता है: lcm(a, b) = a·b / gcd(a, b)।
स्व-जाँच gcd(84, 36) क्या है?
12
252
4
6
उत्तर: 12. 84 = 2·36 + 12 और 36 = 3·12 + 0, इसलिए gcd 12 है। 252 लघुत्तम समापवर्त्य है, 84·36/12।
3प्रतिलोम और विस्तारित एल्गोरिथ्म
n के मापांक में a का प्रतिलोम वह संख्या x है जिसके लिए a·x ≡ 1 (mod n)। यह ठीक तभी मौजूद होता है जब gcd(a, n) = 1।
विस्तारित यूक्लिडीय एल्गोरिथ्म यूक्लिड को (n, a) पर चलाता है और हर शेषफल के लिए एक गुणांक t रखता है, ताकि हर शेषफल r ≡ t·a (mod n) हो। n के लिए t = 0 और a के लिए t = 1 से शुरू करें; हर नया t, दो पंक्ति ऊपर के t में से q गुणा एक पंक्ति ऊपर का t घटाने पर मिलता है। जब शेषफल 1 आए, तो उसका t प्रतिलोम है।
प्रतिलोम की सहायता से सर्वांगसमता a·x ≡ b (mod n) हल होती है: x ≡ a⁻¹·b। जब d = gcd(a, n) 1 से बड़ा हो, तो d, b को विभाजित करे तो d हल होते हैं, अन्यथा कोई नहीं।
सहअभाज्य मापांकों वाली दो सर्वांगसमताओं, x ≡ r₁ (mod m₁) और x ≡ r₂ (mod m₂), का m₁·m₂ के मापांक में ठीक एक हल होता है (चीनी शेषफल प्रमेय)। x = r₁ + m₁k लिखें और k के लिए हल करें।
बार-बार वर्ग करना aᵏ mod n को तेज़ी से निकालता है: k को द्विआधारी में लिखें, वर्ग करके और घटाकर a, a², a⁴, a⁸, … mod n निकालें, और जिन घातों का बिट 1 है उन्हें गुणा करें।
फर्मा का लघु प्रमेय: अभाज्य p के लिए जो a को विभाजित नहीं करता, aᵖ⁻¹ ≡ 1 (mod p)। इसलिए घातांक को p − 1 के मापांक में घटाया जा सकता है।
RSA दो अभाज्य संख्याओं p और q से कुंजी बनाता है:
n = p·q और φ(n) = (p − 1)(q − 1)।
e चुनें जिसके लिए gcd(e, φ(n)) = 1 हो; (n, e) सार्वजनिक कुंजी है।
d = e⁻¹ mod φ(n) निकालें: यही निजी कुंजी है।
एन्क्रिप्ट: c = mᵉ mod n; डिक्रिप्ट: m = cᵈ mod n।
यूलर का φ(n) 1 से n तक की उन संख्याओं को गिनता है जो n से सहअभाज्य हैं: अभाज्य के लिए φ(p) = p − 1, φ(pᵏ) = pᵏ − pᵏ⁻¹, और सहअभाज्य गुणनखंडों के लिए φ गुणात्मक है।
स्व-जाँच एक RSA कुंजी में p = 5, q = 11 और e = 3 है। d क्या है?
13
27
37
3
उत्तर: 27. φ(n) = 4·10 = 40, और 3·27 = 81 = 2·40 + 1, इसलिए d = 27। n = 55 के मापांक में 3 का प्रतिलोम 37 होता, पर d को φ(n) के मापांक में लिया जाता है।
5सामान्य गलतियाँ
ऋणात्मक संख्या के लिए ऋणात्मक शेषफल देना: −17 mod 5 का मान 3 है, −2 नहीं।
यूक्लिड को अंतिम अशून्य शेषफल की जगह पहले शेषफल पर रोक देना।
विस्तारित एल्गोरिथ्म से मिले ऋणात्मक गुणांक में n जोड़ना भूल जाना।
RSA घातांक d को φ(n) के बजाय n के मापांक में निकालना।
फर्मा प्रमेय में घातांक को p − 1 की जगह p के मापांक में घटाना।
6परीक्षा प्रश्न कैसे दिखते हैं
आसान: gcd और शेषफल। आप gcd या lcm के लिए यूक्लिड का एल्गोरिथ्म चलाते हैं, ऋणात्मक संख्याओं के शेषफल निकालते हैं, और योग व गुणनफल को n के मापांक में घटाते हैं।
मध्यम: प्रतिलोम और सर्वांगसमताएँ। आप विस्तारित एल्गोरिथ्म से मॉड्यूलर प्रतिलोम निकालते हैं, रैखिक सर्वांगसमताएँ हल करते हैं, चीनी शेषफल प्रमेय से दो सर्वांगसमताएँ मिलाते हैं, और यूलर का φ(n) निकालते हैं।
कठिन: मॉड्यूलर घात और RSA। आप बार-बार वर्ग करना और फर्मा प्रमेय उपयोग करते हैं, कई हलों वाली सर्वांगसमताएँ हल करते हैं, और RSA के निजी घातांक, सिफरटेक्स्ट और डिक्रिप्ट किए गए संदेश निकालते हैं।
बड़ी संख्याओं को गुणा किए बिना (914·953) mod 11 ज्ञात करें: पहले घटाएँ।
n = 11
ज्ञात करें: (914·953) mod 11
संकेत दिखाएँ
(x·y) mod n = ((x mod n)·(y mod n)) mod n, और योग के लिए भी यही सत्य है।
914 mod 11 = 1, 953 mod 11 = 7.
शेषफलों के गुणनफल को 11 के मापांक में घटाएँ।
उत्तर और चरण-दर-चरण हल दिखाएँ
विभाज्यता और शेषफल: a mod n वह शेषफल r है जिसके लिए 0 ≤ r < n और a = q·n + r, a ऋणात्मक होने पर भी। यूक्लिड का एल्गोरिथ्म a = q·b + r को दोहराकर और (a, b) को (b, r) से बदलकर gcd(a, b) निकालता है; अंतिम अशून्य शेषफल gcd है। फिर lcm(a, b) = a·b/gcd(a, b)। शेषफलों को हर चरण पर घटाया जा सकता है: (a + b) mod n और (a·b) mod n केवल a mod n और b mod n पर निर्भर करते हैं।
हर संख्या को घटाएँ
914 ≡ 1, 953 ≡ 7 (mod 11)
मिलाएँ
1·7 = 7 ≡ 7 (mod 11)
उत्तर
(914·953) mod 11 = 7
उदाहरण 2मध्यम
यूलर का टोशेंट φ(637) ज्ञात करें, यानी 1 से 637 तक के वे पूर्णांक जो 637 से सहअभाज्य हैं।
n = 637 = 72·13
ज्ञात करें: φ(637)
संकेत दिखाएँ
n को अभाज्य गुणनखंडों में बाँटें: 637 = 72·13।
φ सहअभाज्य गुणनखंडों के लिए गुणात्मक है, और φ(pᵏ) = pᵏ − pᵏ⁻¹।
φ(n) = n·∏(1 − 1/p).
उत्तर और चरण-दर-चरण हल दिखाएँ
प्रतिलोम और सर्वांगसमताएँ: a का n के मापांक में प्रतिलोम ठीक तब होता है जब gcd(a, n) = 1। विस्तारित यूक्लिडीय एल्गोरिथ्म 1 = s·n + t·a लिखता है, और तब a⁻¹ ≡ t (mod n)। gcd(a, n) = 1 वाली सर्वांगसमता a·x ≡ b (mod n) का हल x ≡ a⁻¹·b है। सहअभाज्य मापांकों वाली दो सर्वांगसमताओं x ≡ r₁ (mod m₁) और x ≡ r₂ (mod m₂) का m₁·m₂ के मापांक में एक हल होता है (चीनी शेषफल प्रमेय)। यूलर का φ(n) 1 से n तक की उन संख्याओं को गिनता है जो n से सहअभाज्य हैं: φ(n) = n·∏(1 − 1/p)।
अभाज्य गुणनखंड
637 = 72·13
टोशेंट
φ(637) = φ(49)·φ(13) = 42·12 = 504
उत्तर
φ(637) = 504
उदाहरण 3कठिन
एक RSA कुंजी में p = 13, q = 37 और e = 23 हैं। सिफरटेक्स्ट c = 225 को डिक्रिप्ट करें: संदेश m ज्ञात करें।
p = 13q = 37e = 23c = 225
ज्ञात करें: m
संकेत दिखाएँ
n = 481, φ(n) = 432।
d = e⁻¹ mod φ(n) = 263।
m = cd mod n = 225263 mod 481: बार-बार वर्ग करना उपयोग करें.
उत्तर और चरण-दर-चरण हल दिखाएँ
मॉड्यूलर घात और RSA: aᵏ mod n बार-बार वर्ग करके निकालें: k को द्विआधारी में लिखें, वर्ग करें, हर चरण के बाद घटाएँ और जिन घातों का बिट 1 है उन्हें गुणा करें। फर्मा: अभाज्य p के लिए, जो a को विभाजित नहीं करता, aᵖ⁻¹ ≡ 1 (mod p), इसलिए घातांक को p − 1 के मापांक में घटाया जा सकता है। RSA: अभाज्य p और q चुनें, n = p·q और φ(n) = (p − 1)(q − 1); सार्वजनिक घातांक e, φ(n) से सहअभाज्य है, और निजी घातांक d = e⁻¹ mod φ(n) है। c = mᵉ mod n से एन्क्रिप्ट करें और m = cᵈ mod n से डिक्रिप्ट करें।
निजी घातांक
n = 481, φ(n) = 432
d = 23−1 mod 432 = 263
बार-बार वर्ग करके डिक्रिप्ट करें
263 = 256 + 4 + 2 + 1
2251 ≡ 225 (mod 481)
2252 ≡ 120 (mod 481)
2254 ≡ 451 (mod 481)
2258 ≡ 419 (mod 481)
22516 ≡ 477 (mod 481)
22532 ≡ 16 (mod 481)
22564 ≡ 256 (mod 481)
225128 ≡ 120 (mod 481)
225256 ≡ 451 (mod 481)
225263 ≡ 225·120·451·451 ≡ 361 (mod 481)
संदेश
m = 361
जाँच: 36123 mod 481 = 225
उत्तर
m = 361
प्रश्न और उत्तर
संख्या सिद्धांत और मॉड्यूलर अंकगणित क्या है?
a को n से भाग देने पर भागफल q और शेषफल r मिलता है: a = q·n + r, जहाँ 0 ≤ r < n। शेषफल को a mod n लिखा जाता है। ऋणात्मक संख्या के लिए q भी ऋणात्मक होता है: −3 = −1·7 + 4, इसलिए −3 mod 7 = 4।
दो संख्याएँ n के मापांक में सर्वांगसम होती हैं, a ≡ b (mod n), जब उनका शेषफल समान हो, अर्थात जब n, a − b को विभाजित करे।
संख्या सिद्धांत और मॉड्यूलर अंकगणित के प्रश्न चरण-दर-चरण कैसे हल करें?
पहले हर संख्या को n के मापांक में घटाएँ; शेषफल 0 से n − 1 के बीच होते हैं।
gcd के लिए यूक्लिड एल्गोरिथ्म से बार-बार भाग दें; अंतिम अशून्य शेषफल ही gcd है।
प्रतिलोम के लिए विस्तारित एल्गोरिथ्म चलाएँ और a का गुणांक रखें; ऋणात्मक हो तो n जोड़ें।
a·x ≡ b को हल करने के लिए a⁻¹ से गुणा करें; दो सर्वांगसमताओं को x = r₁ + m₁k लिखकर मिलाएँ।
घातों के लिए घातांक को द्विआधारी में लिखें और बार-बार वर्ग करें; RSA में d = e⁻¹ mod φ(n) होता है, जहाँ φ(n) = (p − 1)(q − 1)।
संख्या सिद्धांत और मॉड्यूलर अंकगणित में आम गलतियाँ क्या हैं?
ऋणात्मक संख्या के लिए ऋणात्मक शेषफल देना।
यूक्लिड के एल्गोरिथ्म को पहले शेषफल पर ही रोक देना।
प्रतिलोम में n जोड़ने की जगह उसे ऋणात्मक छोड़ देना।
RSA घातांक d को φ(n) के बजाय n के मापांक में लेना।
फर्मा प्रमेय में घातांक को p − 1 की जगह p के मापांक में घटाना।
संख्या सिद्धांत और मॉड्यूलर अंकगणित के अभ्यास में क्या शामिल है?
आसान: gcd और शेषफल
मध्यम: प्रतिलोम और सर्वांगसमताएँ
कठिन: मॉड्यूलर घात और RSA
हर प्रश्न में नए मान होते हैं, इसलिए आप उत्तर नहीं बल्कि विधि सीखते हैं। अटक गए? पहले एक छोटा संकेत खोलें, और पूरी व्याख्या तभी जब ज़रूरत हो।
अभ्यास कैसे काम करता है
हर प्रश्न में नए मान होते हैं, इसलिए आप उत्तर नहीं बल्कि विधि सीखते हैं।
अटक गए? पहले एक छोटा संकेत खोलें, और पूरी व्याख्या तभी जब ज़रूरत हो।
आपकी प्रगति, गलतियाँ और सहेजे गए प्रश्न रखे जाते हैं, ताकि आप परीक्षा से पहले दोहरा सकें।