👩🏼‍🤝‍👨🏿 👉 🕵️ मॉड्यूलर अंकगणित का परिचय 👨🏼‍⚖️ 👉🏽 🤶🏼

सामान्य जीवन में, हम आमतौर पर एक स्थिति संख्या प्रणाली का उपयोग करते हैं। एक स्थितीय संख्या प्रणाली में, एक संख्या रिकॉर्ड में प्रत्येक संख्यात्मक चरित्र (अंक) का मूल्य उसकी स्थिति (रैंक) [1] पर निर्भर करता है। हालांकि, तथाकथित "गैर-स्थितीय संख्या प्रणाली" हैं, जिनमें से एक "अवशिष्ट वर्ग प्रणाली" (आरएनएस) (या मूल अवशेष संख्या प्रणाली (आरएनएस)) है, जो मॉड्यूलर अंकगणित का आधार है। मॉड्यूलर अंकगणित "चीनी शेष प्रमेय" [2] पर आधारित है, जो हमारे मामले के लिए निम्नानुसार है:

कोप्राइम संख्या पी ₁ , ... पी _एन की किसी भी प्रणाली के लिए, सीमा से किसी भी संख्या एक्स [0; एम), जहां एम = पी ₁ * पी ₂ * ... * पी _एन वेक्टर-के रूप में एक-से-एक का प्रतिनिधित्व करने योग्य है ( ₁ , ₂ , ..., एक _एन ), जहां एक _i = X% p _i (इसके बाद "%" -) एक्स के पूर्णांक विभाजन के शेष भाग को पी _i द्वारा लेने का संचालन)।
पी ₁ , ... पी _एन - सिस्टम मॉड्यूल
मॉड्यूल के दिए गए सिस्टम के लिए संख्या का ₁ , ₂ , ..., _n - अवशेष (कटौती)

पहली नज़र में, यह स्पष्ट नहीं है कि ऐसी प्रणाली क्या लाभ दे सकती है, हालांकि, 2 गुण हैं जो माइक्रोइलेक्ट्रॉनिक के कुछ क्षेत्रों में मॉड्यूलर अंकगणितीय के प्रभावी उपयोग की अनुमति देते हैं:

इसके अलावा और गुणा में निर्वहन के हस्तांतरण का अभाव। हमें दो नंबर X ₁ और X ₂ दिए गए हैं, जिन्हें परस्पर सरल संख्याओं की प्रणाली के अनुसार अवशेषों (x ₁₁ , x ₁₂ , ..., x _1n ) और (x ₂₁ , x ₂₂ , ..., x _2n ) के रूप में दर्शाया गया है (p ₁ , p) ₂ , ..., पी _एन )। इस मामले में:
X ₃ = X ₁ + X ₂ = ((x ₁₁ + x ₂₁ )% p ₁ , (x ₁₂ + x ₂₂ )% p ₂ , ..., (x _1n + x _2n )% p _n )
X ₄ = X ₁ * X ₂ = ((x ₁₁ * x ₂₁ )% p ₁ , (x ₁₂ * x ₂₂ )% p ₂ , ..., (x _1n * x _2n )% p _n )
यही है, दो नंबरों को जोड़ने या गुणा करने के लिए, यह वेक्टर के संबंधित तत्वों को जोड़ने या गुणा करने के लिए पर्याप्त है, जो माइक्रोइलेक्ट्रॉनिक के लिए इसका मतलब है कि यह समानांतर में किया जा सकता है और छोटे आयामों पी ₁ , पी ₂ , ..., पी _{एन के कारण} बहुत जल्दी से किया जा सकता है।
वेक्टर की एक स्थिति में त्रुटि वेक्टर की अन्य स्थितियों में गणना को प्रभावित नहीं करती है। स्थितीय संख्या प्रणाली के विपरीत, वेक्टर के सभी तत्व समतुल्य होते हैं और उनमें से एक में त्रुटि केवल गतिशील रेंज में कमी की ओर ले जाती है। यह तथ्य हमें वृद्धि हुई सहिष्णुता और त्रुटि सुधार के साथ डिवाइस डिजाइन करने की अनुमति देता है।

साधारण गुणन	मॉड्यूलर गुणा

लेकिन सब कुछ उतना सहज नहीं है जितना हम चाहेंगे। स्थितीय संख्या प्रणाली के विपरीत, निम्नलिखित संचालन ("गैर-मॉड्यूलर" कहा जाता है) स्थितीय संख्या प्रणाली की तुलना में अधिक जटिल हैं: संख्याओं की तुलना, अतिप्रवाह नियंत्रण, विभाजन, वर्गमूल, आदि। माइक्रोइलेक्ट्रॉनिक में मॉड्यूलर अंकगणितीय का उपयोग करने के पहले सफल प्रयासों को 1950 के दशक में वापस किया गया था, लेकिन गैर-मॉड्यूलर संचालन के साथ कठिनाइयों के कारण, ब्याज कुछ हद तक कम हो गया है। हालांकि, वर्तमान में मॉड्यूलर अंकगणित फिर से निम्नलिखित कारणों से माइक्रोइलेक्ट्रॉनिक में लौट रहा है:

मोबाइल प्रोसेसर का व्यापक उपयोग, जिसमें कम बिजली की खपत के साथ उच्च गति की आवश्यकता होती है। अंकगणितीय जोड़ / गुणा संचालन में स्थानांतरण की कमी ऊर्जा की खपत को कम करती है।
कुछ मामलों में चिप पर तत्वों का बढ़ता घनत्व पूर्ण परीक्षण की अनुमति नहीं देता है; इसलिए, संभावित त्रुटियों के लिए प्रोसेसर की स्थिरता का महत्व बढ़ रहा है।
वैक्टर पर बड़ी संख्या में संचालन के साथ विशेष प्रोसेसर का उद्भव, जिसमें उच्च गति की आवश्यकता होती है और इसमें मुख्य रूप से संख्याओं का जोड़ और गुणा (उदाहरण के लिए, मैट्रिक्स गुणन, वैक्टर के स्केलर उत्पाद, फूरियर रूपांतरण, आदि) शामिल हैं।

वर्तमान में, मॉड्यूलर अंकगणितीय का उपयोग निम्नलिखित क्षेत्रों में किया जाता है: डिजिटल सिग्नल प्रोसेसिंग, क्रिप्टोग्राफी, इमेज प्रोसेसिंग / ऑडियो / वीडियो इत्यादि।

प्रत्यक्ष रूपांतरण

अवशिष्ट में एक संख्या प्रणाली के लिए एक स्थितीय संख्या प्रणाली (आमतौर पर द्विआधारी रूप में) से प्रत्यक्ष रूपांतरण प्रणाली के प्रत्येक मॉड्यूल के लिए विभाजन के शेष को खोजने में शामिल है।

उदाहरण : मान लीजिए कि आप मॉड्यूल की एक प्रणाली (3, 5, 7) से संख्या X = 25 का प्रतिनिधित्व प्राप्त करना चाहते हैं। X = (25% 3, 25% 5, 25% 7) = (1, 0, 4)।

किसी दिए गए मॉड्यूल के लिए माइक्रोइलेक्ट्रॉनिक में अवशेषों को खोजने का कार्यान्वयन अवशेषों के निम्नलिखित गुणों पर आधारित है:
(a + b)% p = (a% p + b% p)% p
(ए * बी)% पी = (एक% पी * बी% पी)% पी

किसी भी संख्या X को X% p = (x _n-1 * 2 ^n-1 + x _n-2 * 2 ^n-2 + x ₀ * 2 ⁰ )% p = ((x _n-1 )% p के रूप में लिखा जा सकता है। * 2 ^n-1 % p) + ((x _n-2 )% p * 2 ^n-2 % p) + ... + x ₀ % p)% p। चूंकि इस मामले में x _n-1 , ... x ₀ 0 या 1 हैं, वास्तव में, हमें फॉर्म (2 ⁱ % p) के अवशेषों को जोड़ने की आवश्यकता है।

उदाहरण : नंबर 25 को दिया जाए या बाइनरी नंबर सिस्टम 11001 में और आप शेष मोडुलो 7 को ढूंढना चाहते हैं।
25% 7 = (1 * 2 ⁴ + 1 * 2 ³ + 0 * 2 ² + 0 * ¹ + 1 * 2 ⁰ )% 7 = (2 ⁴ % 7 + 2 ³ % 7 + 1% 7)% 7 = (२ + १ + १)% 4 = ४

उपयोग किए गए मॉड्यूल की प्रणाली को एक विशिष्ट कार्य के लिए चुना जाता है। उदाहरण के लिए, 32-बिट संख्याओं का प्रतिनिधित्व करने के लिए, मॉड्यूल की निम्नलिखित प्रणाली पर्याप्त है: (7, 11, 13, 17, 19, 23, 29, 31) - वे सभी एक दूसरे के साथ पारस्परिक रूप से सरल हैं, उनका उत्पाद 6685349671: 4294967296 है। प्रत्येक मॉड्यूल नहीं है 5 बिट्स से अधिक है, अर्थात 5-बिट संख्याओं पर जोड़ और गुणा का संचालन किया जाएगा।
विशेष महत्व के रूप के मॉड्यूल की प्रणाली भी है: (2 ^एन -1, 2 ^एन , 2 ^एन +1) इस तथ्य के कारण कि उनके लिए प्रत्यक्ष और उलटा रूपांतरण सबसे सरल तरीके से किया जाता है। 2 ^एन द्वारा विभाजन के शेष को प्राप्त करने के लिए ^, संख्या के द्विआधारी प्रतिनिधित्व के अंतिम एन अंक लेने के लिए पर्याप्त है।

अंकगणित संचालन

उदाहरण : मॉड्यूल (3, 5, 7) की एक प्रणाली दी जाए, अर्थात हम ऐसे कार्य कर सकते हैं जिनका परिणाम 3 * 5 * 7 = 105 से अधिक न हो। हम दो संख्याओं को 8 और 10 से गुणा करते हैं।
8 = (8% 3, 8% 5, 8% 7) = (2, 3, 1)
10 = (10% 3, 10% 5, 10% 7) = (1, 0, 3)
8 * 10 = ((2 * 1)% 3, (3 * 0)% 5, (1 * 3)% 7) = (2, 0, 3)
चेक
80 = (80% 3, 80% 5, 80% 7) = (2, 0, 3)

उलटा परिवर्तन

अवशिष्ट वर्गों में संख्या प्रणाली से स्थितिगत संख्या प्रणाली में व्युत्क्रम परिवर्तन दो तरीकों में से एक में किया जाता है:

चीनी शेष प्रमेय या रूढ़िवादी आधारों की प्रणाली के आधार पर
एक बहुपद कोड (मिश्रित नाम-मूलांक प्रणाली, मिश्रित आधार प्रणाली) पर आधारित

विभिन्न तरीकों से प्रस्तावित विभिन्न साहित्य, वास्तव में, इन दोनों का मिश्रण हैं।

चीनी शेष प्रमेय पर आधारित एक विधि निम्नलिखित विचार पर आधारित है:
X = (x ₁ , x ₂ , ... x _n ) = (x ₁ , 0, ..., 0) + (0, x ₂ , ..., 0) + ... + (0, 0, ..., x _n ) = x ₁ * (1, 0, ..., 0) + x ₂ * (0, 1, ..., 0) + ... + x _n * (0, 0, ..., 1)।
यही है, व्युत्क्रम परिवर्तन के लिए, ऑर्थोगोनल आधारों बी 1 = (1, 0, ..., 0), बी 2 = (0, 1, ..., 0), ..., बीएन = (0, 0, ..., 1) की एक प्रणाली को खोजने के लिए आवश्यक है। ये वैक्टर एक बार दिए गए आधार के लिए पाए जाते हैं, और उनकी खोज के लिए फॉर्म के एक समीकरण को हल करना आवश्यक है: (M _i * b _i )% p _i = 1, जहां M _i = M / p _i और b _i वांछित संख्या है। इस स्थिति में, स्थितीय प्रतिनिधित्व B _i = M _i * b _i और
X = (x ₁ * (M ₁ * b ₁ ) + x ₂ * (M ₂ * b ₂ ) + ... + x _n * (M _n * b _n ))% M

उदाहरण : मॉड्यूल की एक प्रणाली दी जाए (3, 5, 7), हम एम _आई और बी _आई (0 <i <= 3) के मान पाएंगे।
एम = 3 * 5 * 7 = 105
एम ₁ = 105/3 = 35
एम ₂ = 105/5 = 21
एम ₃ = 105/7 = 15
(३५ * ब _१ )% ३ = १ => ख _१ = २
(21 * बी ₂ )% 5 = 1 => बी ₂ = 1
(१५ * ब _३ )% 1 = १ => ब _३ = १
अब हम अवशिष्ट वर्गों की प्रणाली में कुछ संख्या को बदल देंगे। रखना
X = (2, 3, 1) = (2 * 35 * 2 + 3 * 21 * 1 + 1 * 15 * 1)% 105 = (140 + 63 + 15)% 105 = 218% 105 = 8

इस पद्धति का नुकसान यह है कि व्युत्क्रम परिवर्तन के लिए बड़ी संख्याओं (एम ₁ , ..., एम _एन ) के गुणन और इसके अतिरिक्त की आवश्यकता होती है, साथ ही शेष मॉडुलो को बड़ी संख्या में लेने का संचालन भी होता है।

एक बहुपद कोड पर आधारित विधि इस विचार पर आधारित है कि किसी भी संख्या X को कोप्राइम संख्या p ₁ , ... p _n , की प्रणाली में दर्शाया जा सकता है: [4]:
X = एक ₁ + ₂ * p ₁ + a ₃ * p ₁ * p ₂ + ... + a _n-1 * p ₁ * p ₂ * ... * p _n-2 + a _n * p ₁ * p ₂ * ... * p _n-1 , जहाँ 0 <a _i <p _i

एक्स% पी ₁ = एक्स ₁ = ए ₁
(एक्स - ए _१ )% पी _२ = (एक्स _२ - ए _१ )% पी _२ = (ए _२ * पी _१ )% पी _२ => ए _२ = ((पी _१ ^-1 )% पी _२ * (एक्स _२) - एक ₁ ))% पी ₂
(एक्स - एक - एक - _२ * पी _१ )% पी _३ = (एक _३ * पी _१ * पी _२ )% पी _३ => ए _३ = ((पी ^२-१ )% पी _३ * ((पी _१) ^{- 1} )% पी ₃ * (एक्स ₃ - ए ₁ ) - एक ₂ ))% पी ₃
...

इस पद्धति का उपयोग करने के लिए, प्रपत्र (p _i ^-1 )% p _k ^{-1 के} स्थिरांक की आवश्यकता होती है। आप यह भी देख सकते हैं कि ₁ के मान के प्रकट होते ही ₃ की गणना शुरू करना संभव है। इस विधि के आधार पर कन्वेयर कन्वर्टर्स बनाए जा सकते हैं।

उदाहरण : एक ही उदाहरण पर विचार करें - मॉड्यूल सिस्टम (3, 5, 7) में संख्या X = (2, 3, 1) की स्थिति का प्रतिनिधित्व करें।
एक ₁ = x ₁ = 2
एक ₂ = ((पी ₁ ^-1 )% पी ₂ * (एक्स ₂ - ए ₁ ))% पी ₂ = ((3 ^-1 )% 5 * (3 - 2))% 5 = 2 * 1 = 2
एक ₃ = ((पी ₂ ^-1 )% पी ₃ * ((पी ₁ ^-1 )% पी ₃ * (एक्स ₃ - ए ₁ ) - ₂ ए)% पी ₃ = ((5 ^-1 )% 7 * ((3 ^-1 )% 7 * (1 - 2) - 2))% 7 = (3 * (5 * (1-2) -2))% 7 = (3 * (- 7))% 7 = 0
X = एक ₁ + ₂ * p ₁ + a ₃ * p ₁ * p ₂ = a ₁ + 3 * a ₂ + 15 * a ₃ = 2 + 3 * 2 + 15 * 0 = 8

नोट : फॉर्म (3 ^-1 )% 5 की एक निरंतरता को खोजने के लिए, समीकरण (3 * x)% 5 = 1 को हल करना आवश्यक है, जहां 0 <= x <5

पुनश्च

लेख कुछ गड़बड़ लिखा गया था, क्योंकि विषय काफी बड़ा है और एक लेख में सब कुछ फिट करना संभव नहीं है। निम्नलिखित लेखों में मैं मॉड्यूलर अंकगणित के विभिन्न पहलुओं को और अधिक विस्तार से वर्णन करने का प्रयास करूंगा। हबर पर, मुझे इस विषय से संबंधित कुछ भी नहीं मिला, केवल अन्य लेखों में संक्षिप्त संदर्भ, इसलिए सरल उदाहरणों के साथ एक छोटी समीक्षा लिखने का निर्णय लिया गया। उन लोगों के लिए जो विषय में रुचि रखते हैं, मैं संदर्भ की सूची (अंग्रेजी में) से पुस्तक संख्या [3] पढ़ने की सलाह देता हूं, यह एक सुलभ भाषा में बहुत सारे उदाहरणों के साथ लिखा गया है।

साहित्य

[१] en.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B7%D0%B8%D1%86%D0%B0%B8%D0%B0%BE%D0%DD%D0%BD%D0% B0% D1% 8F_% D1% 81% D0% B8% D1% 81% D1% 82% D0% B5% D5% BC0% D0% B0_% D1% 81% D1% 87% D0% B8% D8% 81% D0% BB% D0% B5% D0% BD% D0% B8% D1% 8F
[२] en.wikipedia.org/wiki/%D0%9A%D0%B8%D1%82%D0%B0%B0%B9%D1%81%81%D0%BA%D0%D0%D1%8F_%D1%% 82% D0% B5% D0% BE% D1% 80% D0% B5% D0% BC% D0% B0_% D0% BE% D0% B1_% D0% BE% D1% 81% D1% 82% D1% B0% D1% 82% D0% BA% D0% B0% D1% 85
[३] अमोस ओमोन्दी, बेंजामिन प्रेमकुमार, अवशेष संख्या प्रणाली: सिद्धांत और कार्यान्वयन, २०० 2007।
[४] एमए सोदरस्ट्रैंड, डब्ल्यूके जेनकींस, जीए जुलिएन और एफजे टेलर। 1986. अवशेष संख्या प्रणाली अंकगणित: डिजिटल सिग्नल प्रोसेसिंग में आधुनिक अनुप्रयोग, IEEE प्रेस, न्यूयॉर्क।

मॉड्यूलर अंकगणित का परिचय

प्रत्यक्ष रूपांतरण

अंकगणित संचालन

उलटा परिवर्तन

पुनश्च

साहित्य

More articles: