मॉड्यूलर गुणक व्युत्क्रम

गणित में, विशेष रूप से अंकगणित के क्षेत्र में, एक पूर्णांक का एक मॉड्यूलर गुणन व्युत्क्रम a एक पूर्णांक है x ऐसा कि उत्पाद ax मापांक के संबंध में 1 से सर्वांगसमता संबंध#बुनियादी उदाहरण है m. मॉड्यूलर अंकगणित के मानक अंकन में इस सर्वांगसमता को इस प्रकार लिखा जाता है

$ax\equiv 1{\pmod {m}},$

जो कि कथन लिखने का संक्षिप्त तरीका है m मात्रा को (समान रूप से) विभाजित करता है ax − 1, या, दूसरे तरीके से कहें तो, विभाजित करने के बाद शेषफल ax पूर्णांक द्वारा m है 1. यदि a में एक व्युत्क्रम मॉड्यूलो है m, तो इस सर्वांगसमता के अनंत संख्या में समाधान हैं, जो इस मापांक के संबंध में एक मॉड्यूलर अंकगणित#सर्वांगसमता वर्ग बनाते हैं। इसके अलावा, कोई भी पूर्णांक जो सर्वांगसम हो a (अर्थात्, में a'सर्वांगसमता वर्ग) का कोई तत्व है x का सर्वांगसमता वर्ग एक मॉड्यूलर गुणक व्युत्क्रम के रूप में। के अंकन का उपयोग करना ${\overline {w}}$ सर्वांगसमता वर्ग को इंगित करने के लिए w, इसे सर्वांगसमता वर्ग का मॉड्यूलो गुणात्मक व्युत्क्रम कहकर व्यक्त किया जा सकता है ${\overline {a}}$ सर्वांगसमता वर्ग है ${\overline {x}}$ ऐसा है कि:

${\overline {a}}\cdot _{m}{\overline {x}}={\overline {1}},$

जहां प्रतीक $\cdot _{m}$ तुल्यता वर्गों मॉड्यूलो के गुणन को दर्शाता है m. इस तरह से लिखे जाने पर, परिमेय संख्या या वास्तविक संख्याओं के सेट में गुणात्मक व्युत्क्रम की सामान्य अवधारणा के साथ सादृश्य को स्पष्ट रूप से दर्शाया जाता है, संख्याओं को सर्वांगसम वर्गों द्वारा प्रतिस्थापित किया जाता है और बाइनरी ऑपरेशन को उचित रूप से बदल दिया जाता है।

वास्तविक संख्याओं पर अनुरूप ऑपरेशन की तरह, इस ऑपरेशन का मौलिक उपयोग, जब संभव हो, फॉर्म की रैखिक सर्वांगसमताओं को हल करने में होता है

$ax\equiv b{\pmod {m}}.$

मॉड्यूलर गुणक व्युत्क्रम खोजने का क्रिप्टोग्राफी, यानी सार्वजनिक-कुंजी क्रिप्टोग्राफी और आरएसए (क्रिप्टोसिस्टम) के क्षेत्र में व्यावहारिक अनुप्रयोग भी है। इन अनुप्रयोगों के कंप्यूटर कार्यान्वयन के लिए एक लाभ यह है कि एक बहुत तेज़ एल्गोरिदम (विस्तारित यूक्लिडियन एल्गोरिदम) मौजूद है जिसका उपयोग मॉड्यूलर गुणक व्युत्क्रमों की गणना के लिए किया जा सकता है।

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

Main article: Modular arithmetic

किसी दिए गए सकारात्मक पूर्णांक के लिए m, दो पूर्णांक, a और b, सर्वांगसम मॉड्यूलो कहलाते हैं m अगर m उनके अंतर को विभाजित करता है। इस द्विआधारी संबंध को निरूपित किया जाता है,

$a\equiv b{\pmod {m}}.$

यह पूर्णांकों के समुच्चय पर एक तुल्यता संबंध है, ℤ, और समतुल्य वर्गों को सर्वांगसम वर्ग मॉड्यूलो कहा जाता है m या अवशेष वर्ग मॉड्यूलो m. होने देना ${\overline {a}}$ पूर्णांक वाले सर्वांगसम वर्ग को निरूपित करें a, तब

${\overline {a}}=\{b\in \mathbb {Z} \mid a\equiv b{\pmod {m}}\}.$

एक रैखिक सर्वांगसमता प्रपत्र की एक मॉड्यूलर सर्वांगसमता है

$ax\equiv b{\pmod {m}}.$

वास्तविक पर रैखिक समीकरणों के विपरीत, रैखिक सर्वांगसमताओं में शून्य, एक या कई समाधान हो सकते हैं। अगर x प्रत्येक तत्व की तुलना में रैखिक सर्वांगसमता का एक समाधान है ${\overline {x}}$ एक समाधान भी है, इसलिए, जब एक रैखिक सर्वांगसमता के समाधानों की संख्या के बारे में बात की जाती है तो हम विभिन्न सर्वांगसमता वर्गों की संख्या का उल्लेख कर रहे होते हैं जिनमें समाधान होते हैं।

अगर d का सबसे बड़ा सामान्य भाजक है a और m फिर रैखिक सर्वांगसमता ax ≡ b (mod m) के पास समाधान हैं यदि और केवल यदि d बांटता है b. अगर d बांटता है b, तो बिल्कुल हैं d समाधान। एक पूर्णांक का एक मॉड्यूलर गुणन व्युत्क्रम a मापांक के संबंध में m रैखिक सर्वांगसमता का एक समाधान है

$ax\equiv 1{\pmod {m}}.$

पिछला परिणाम कहता है कि समाधान मौजूद है यदि और केवल यदि gcd(a, m) = 1, वह है, a और m सहअभाज्य पूर्णांक होना चाहिए (अर्थात् सहअभाज्य)। इसके अलावा, जब यह स्थिति कायम रहती है, तो वास्तव में एक ही समाधान होता है, यानी, जब यह मौजूद होता है, तो एक मॉड्यूलर गुणक व्युत्क्रम अद्वितीय होता है: अगर b और b' दोनों मॉड्यूलर गुणात्मक व्युत्क्रम हैं a मापांक का सम्मान m, तब

$ab\equiv ab'\equiv 1{\pmod {m}},$

इसलिए

$a(b-b')\equiv 0{\pmod {m}}.$

अगर a ≡ 0 (mod m), तब gcd(a, m) = a, और a में मॉड्यूलर गुणक व्युत्क्रम भी नहीं होगा। इसलिए, b ≡ b' (mod m).

कब ax ≡ 1 (mod m) का एक समाधान है इसे अक्सर इस तरह से दर्शाया जाता है -

$x\equiv a^{-1}{\pmod {m}},$

लेकिन इसे संकेतन का दुरुपयोग माना जा सकता है क्योंकि इसे गुणात्मक व्युत्क्रम के रूप में गलत समझा जा सकता है $a$ (जो, मॉड्यूलर गुणक व्युत्क्रम के विपरीत, कब को छोड़कर पूर्णांक नहीं है a 1 या -1 है)। यदि अंकन उचित होगा a की व्याख्या सर्वांगसमता वर्ग के प्रतीक चिह्न के रूप में की गई है ${\overline {a}}$, क्योंकि सर्वांगसम वर्ग का गुणन व्युत्क्रम अगले भाग में परिभाषित गुणन के साथ एक सर्वांगसम वर्ग है।

पूर्णांक मॉड्यूलो m

सर्वांगसमता संबंध, मॉड्यूलो m, पूर्णांकों के समुच्चय को विभाजित करता है m सर्वांगसमता कक्षाएं। इन पर जोड़ और गुणा की संक्रियाओं को परिभाषित किया जा सकता है m वस्तुओं को निम्नलिखित तरीके से: दो सर्वांगसमता वर्गों को जोड़ने या गुणा करने के लिए, पहले प्रत्येक वर्ग से एक प्रतिनिधि चुनें (किसी भी तरह से), फिर दो प्रतिनिधियों पर पूर्णांकों के लिए सामान्य ऑपरेशन करें और अंत में सर्वांगसमता वर्ग लें जिसका परिणाम होगा पूर्णांक संक्रिया सर्वांगसम वर्गों पर संक्रिया के परिणाम के रूप में निहित है। प्रतीकों में, साथ में $+_{m}$ और $\cdot _{m}$ सर्वांगसमता वर्गों पर संचालन का प्रतिनिधित्व करते हुए, ये परिभाषाएँ हैं

${\overline {a}}+_{m}{\overline {b}}={\overline {a+b}}$

और

${\overline {a}}\cdot _{m}{\overline {b}}={\overline {ab}}.$

ये ऑपरेशन अच्छी तरह से परिभाषित हैं, जिसका अर्थ है कि अंतिम परिणाम उन प्रतिनिधियों की पसंद पर निर्भर नहीं करता है जो परिणाम प्राप्त करने के लिए बनाए गए थे। m} इन दो परिभाषित संक्रियाओं के साथ सर्वांगसमता वर्ग एक रिंग (गणित) बनाते हैं, जिसे पूर्णांक मॉड्यूलो का रिंग कहा जाता है m. इन बीजगणितीय वस्तुओं के लिए अक्सर कई नोटेशन का उपयोग किया जाता है $\mathbb {Z} /m\mathbb {Z}$ या $\mathbb {Z} /m$, लेकिन कई प्रारंभिक पाठ और अनुप्रयोग क्षेत्र एक सरलीकृत नोटेशन का उपयोग करते हैं $\mathbb {Z} _{m}$ जब अन्य बीजगणितीय वस्तुओं के साथ भ्रम की संभावना नहीं होती है।

पूर्णांक मॉड्यूलो की सर्वांगसमता कक्षाएं m को परंपरागत रूप से अवशेष वर्ग मॉड्यूलो एम के रूप में जाना जाता था, जो इस तथ्य को दर्शाता है कि सर्वांगसमता वर्ग के सभी तत्वों को विभाजित करने पर समान शेष (अर्थात् अवशेष) होता है। m. का कोई भी सेट m पूर्णांकों का चयन इस प्रकार किया जाता है कि प्रत्येक एक अलग सर्वांगसमता वर्ग मॉड्यूलो m से आता है जिसे पूर्ण अवशेष प्रणाली मॉड्यूलो m कहा जाता है|अवशेष मॉड्यूलो की पूर्ण प्रणाली m. पूर्णांकों के लिए विभाजन एल्गोरिथ्म दर्शाता है कि पूर्णांकों का समुच्चय, {0, 1, 2, ..., m − 1} अवशेष मॉड्यूलो की एक पूरी प्रणाली बनाएं m, जिसे कम से कम अवशेष प्रणाली मॉड्यूलो एम|कम से कम अवशेष प्रणाली मॉड्यूलो के रूप में जाना जाता है m. अंकगणितीय समस्याओं के साथ काम करने में कभी-कभी अवशेषों की पूरी प्रणाली के साथ काम करना और सर्वांगसमता की भाषा का उपयोग करना अधिक सुविधाजनक होता है, जबकि अन्य समय में रिंग के सर्वांगसम वर्गों के दृष्टिकोण का उपयोग करना अधिक सुविधाजनक होता है। $\mathbb {Z} /m\mathbb {Z}$ अधिक उपयोगी है.

पूर्णांकों का गुणक समूह m

Main article: Multiplicative group of integers modulo n

संपूर्ण अवशेष प्रणाली मॉड्यूलो का प्रत्येक तत्व नहीं m में एक मॉड्यूलर गुणात्मक व्युत्क्रम होता है, उदाहरण के लिए, शून्य कभी नहीं होता है। एक पूर्ण अवशेष प्रणाली के उन तत्वों को हटाने के बाद जो अपेक्षाकृत प्रमुख नहीं हैं m, जो बचा है उसे कम अवशेष प्रणाली कहा जाता है, जिसके सभी तत्वों में मॉड्यूलर गुणक व्युत्क्रम होते हैं। कम अवशेष प्रणाली में तत्वों की संख्या होती है $\phi (m)$, कहाँ $\phi$ यूलर का टोटिएंट फ़ंक्शन है, यानी, सकारात्मक पूर्णांकों की संख्या से कम m जो अपेक्षाकृत प्रमुख हैं m.

एक इकाई वाले सामान्य वलय में प्रत्येक तत्व का गुणात्मक व्युत्क्रम नहीं होता है और जो होता है उसे इकाई (रिंग सिद्धांत) कहा जाता है। चूँकि दो इकाइयों का गुणनफल एक इकाई है, रिंग की इकाइयाँ एक समूह (गणित) बनाती हैं, रिंग की इकाइयों का समूह और अक्सर इसे निरूपित किया जाता है R^× अगर R अंगूठी का नाम है. पूर्णांक मॉड्यूलो के वलय की इकाइयों का समूह m को पूर्णांक मॉड्यूलो का गुणक समूह कहा जाता है m, और यह कम अवशेष प्रणाली के लिए समरूपता है। विशेष रूप से, इसमें ऑर्डर (समूह सिद्धांत) (आकार) है, $\phi (m)$.

उस मामले में {{mvar|m}मान लीजिए, } एक अभाज्य संख्या है p, तब $\phi (p)=p-1$ और के सभी गैर-शून्य तत्व $\mathbb {Z} /p\mathbb {Z}$ इस प्रकार गुणात्मक व्युत्क्रम होते हैं $\mathbb {Z} /p\mathbb {Z}$ एक सीमित क्षेत्र है. इस मामले में, पूर्णांकों का गुणक समूह मॉड्यूलो है p क्रम का एक चक्रीय समूह बनाएं p − 1.

उदाहरण

किसी भी पूर्णांक के लिए $n>1$, हमेशा ऐसा ही होता है $n^{2}-n+1$ का मॉड्यूलर गुणक व्युत्क्रम है $n+1$ मापांक के संबंध में $n^{2}$, तब से $(n+1)(n^{2}-n+1)=n^{3}+1$. उदाहरण हैं $3\times 3\equiv 1{\pmod {4}}$, $4\times 7\equiv 1{\pmod {9}}$, $5\times 13\equiv 1{\pmod {16}}$ और इसी तरह।

निम्नलिखित उदाहरण मापांक 10 का उपयोग करता है: दो पूर्णांक सर्वांगसम मॉड 10 हैं यदि और केवल यदि उनका अंतर 10 से विभाज्य है, उदाहरण के लिए

$32\equiv 2{\pmod {10}}$ चूँकि 10, 32 - 2 = 30 को विभाजित करता है, और

$111\equiv 1{\pmod {10}}$ चूँकि 10, 111 - 1 = 110 को विभाजित करता है।

इस मापांक के संबंध में दस सर्वांगसमता वर्गों में से कुछ हैं:

${\overline {0}}=\{\cdots ,-20,-10,0,10,20,\cdots \}$ :${\overline {1}}=\{\cdots ,-19,-9,1,11,21,\cdots \}$

${\overline {5}}=\{\cdots ,-15,-5,5,15,25,\cdots \}$ और

${\overline {9}}=\{\cdots ,-11,-1,9,19,29,\cdots \}.$

रैखिक सर्वांगसमता 4x ≡ 5 (mod 10) का कोई समाधान नहीं है क्योंकि पूर्णांक जो 5 के सर्वांगसम हैं (अर्थात, जो इसमें हैं)। ${\overline {5}}$) सभी विषम हैं 4x सदैव सम होता है. हालाँकि, रैखिक सर्वांगसमता 4x ≡ 6 (mod 10) के दो समाधान हैं, अर्थात्, x = 4 और x = 9. वह gcd(4, 10) = 2 और 2, 5 को विभाजित नहीं करता है, लेकिन 6 को विभाजित करता है।

तब से gcd(3, 10) = 1, रैखिक सर्वांगसमता 3x ≡ 1 (mod 10) समाधान होंगे, यानी, 3 मॉड्यूल 10 के मॉड्यूलर गुणक व्युत्क्रम मौजूद होंगे। वास्तव में, 7 इस सर्वांगसमता को संतुष्ट करता है (अर्थात्, 21 − 1 = 20)। हालाँकि, अन्य पूर्णांक भी सर्वांगसमता को संतुष्ट करते हैं, उदाहरण के लिए 17 और −3 (यानी, 3(17) − 1 = 50 और 3(−3) − 1 = −10)। विशेष रूप से, प्रत्येक पूर्णांक ${\overline {7}}$ सर्वांगसमता को संतुष्ट करेगा क्योंकि इन पूर्णांकों का रूप है 7 + 10r कुछ पूर्णांक के लिए r और

$3(7+10r)-1=21+30r-1=20+30r=10(2+3r),$

10 से विभाज्य है। इस सर्वांगसमता में समाधानों का केवल यही एक सर्वांगसमता वर्ग है। इस मामले में समाधान सभी संभावित मामलों की जाँच करके प्राप्त किया जा सकता था, लेकिन बड़े मॉड्यूल के लिए व्यवस्थित एल्गोरिदम की आवश्यकता होगी और इन्हें अगले भाग में दिया जाएगा।

सर्वांगसम वर्गों का उत्पाद ${\overline {5}}$ और ${\overline {8}}$ के एक तत्व का चयन करके प्राप्त किया जा सकता है ${\overline {5}}$, मान लीजिए 25, और का एक तत्व ${\overline {8}}$, मान लीजिए −2, और यह देखते हुए कि उनका उत्पाद (25)(−2) = −50 सर्वांगसमता वर्ग में है ${\overline {0}}$. इस प्रकार, ${\overline {5}}\cdot _{10}{\overline {8}}={\overline {0}}$. जोड़ को इसी प्रकार परिभाषित किया गया है। दस सर्वांगसम वर्ग, सर्वांगसम वर्गों के जोड़ और गुणन की इन संक्रियाओं के साथ मिलकर पूर्णांक मॉड्यूल 10 का वलय बनाते हैं, अर्थात, $\mathbb {Z} /10\mathbb {Z}$.

एक पूर्ण अवशेष प्रणाली मॉड्यूलो 10 सेट {10, −9, 2, 13, 24, −15, 26, 37, 8, 9} हो सकता है, जहां प्रत्येक पूर्णांक एक अलग सर्वांगसमता वर्ग मॉड्यूल 10 में है। अद्वितीय न्यूनतम अवशेष प्रणाली मॉड्यूलो 10 {0, 1, 2, ..., 9} है। एक कम अवशेष प्रणाली मॉड्यूलो 10 {1, 3, 7, 9} हो सकता है। इन संख्याओं द्वारा दर्शाए गए किन्हीं दो सर्वांगसम वर्गों का गुणनफल फिर से इन चार सर्वांगसम वर्गों में से एक है। इसका तात्पर्य यह है कि ये चार सर्वांगसम वर्ग एक समूह बनाते हैं, इस मामले में क्रम चार का चक्रीय समूह, जिसमें (गुणक) जनरेटर के रूप में 3 या 7 होता है। निरूपित सर्वांगसमता वर्ग वलय की इकाइयों का समूह बनाते हैं $\mathbb {Z} /10\mathbb {Z}$. ये सर्वांगसमता वर्ग बिल्कुल वही हैं जिनमें मॉड्यूलर गुणात्मक व्युत्क्रम होते हैं।

गणना

विस्तारित यूक्लिडियन एल्गोरिथ्म

Main article: Extended Euclidean algorithm

का एक मॉड्यूलर गुणक व्युत्क्रम a मापांक mविस्तारित यूक्लिडियन एल्गोरिथ्म का उपयोग करके पाया जा सकता है।

यूक्लिडियन एल्गोरिदम दो पूर्णांकों का सबसे बड़ा सामान्य भाजक (जीसीडी) निर्धारित करता है a और m. अगर a में गुणक व्युत्क्रम मापांक है m, यह जीसीडी 1 होनी चाहिए। एल्गोरिदम द्वारा निर्मित कई समीकरणों में से अंतिम को इस जीसीडी के लिए हल किया जा सकता है। फिर, बैक प्रतिस्थापन नामक विधि का उपयोग करके, मूल मापदंडों और इस जीसीडी को जोड़ने वाला एक अभिव्यक्ति प्राप्त किया जा सकता है। दूसरे शब्दों में, पूर्णांक x और y बेज़ौट की पहचान को संतुष्ट करने के लिए पाया जा सकता है,

$ax+my=\gcd(a,m)=1.$

पुनः लिखा, यह है

$ax-1=(-y)m,$

वह है,

$ax\equiv 1{\pmod {m}},$

तो, एक मॉड्यूलर गुणात्मक व्युत्क्रम a की गणना की गई है. एल्गोरिथम का एक अधिक कुशल संस्करण विस्तारित यूक्लिडियन एल्गोरिथम है, जो सहायक समीकरणों का उपयोग करके, एल्गोरिथम के माध्यम से दो पासों को कम कर देता है (बैक प्रतिस्थापन को एल्गोरिथम के माध्यम से रिवर्स में गुजरने के रूप में सोचा जा सकता है) केवल एक तक।

बड़े O नोटेशन में, यह एल्गोरिथम समय के अनुसार चलता है O(log²(m)), यह मानते हुए |a| < m, और इसे इसके विकल्प, घातांक की तुलना में बहुत तेज़ और आम तौर पर अधिक कुशल माना जाता है।

यूलर के प्रमेय का उपयोग करना

विस्तारित यूक्लिडियन एल्गोरिथ्म के विकल्प के रूप में, यूलर के प्रमेय का उपयोग मॉड्यूलर व्युत्क्रमों की गणना के लिए किया जा सकता है। यूलर के प्रमेय के अनुसार, यदि a सहअभाज्य है m, वह है, gcd(a, m) = 1, तब

$a^{\phi (m)}\equiv 1{\pmod {m}},$

कहाँ $\phi$ यूलर का टोटिएंट फ़ंक्शन है। यह इस तथ्य से पता चलता है कि a गुणक समूह से संबंधित है $(\mathbb {Z} /m\mathbb {Z} )$^× यदि और केवल यदि a सहअभाज्य है m. इसलिए, एक मॉड्यूलर गुणक व्युत्क्रम सीधे पाया जा सकता है:

$a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.$

विशेष मामले में जहां m एक प्रधान है, $\phi (m)=m-1$ और एक मॉड्यूलर व्युत्क्रम दिया गया है

$a^{-1}\equiv a^{m-2}{\pmod {m}}.$

यह विधि आम तौर पर विस्तारित यूक्लिडियन एल्गोरिदम की तुलना में धीमी है, लेकिन कभी-कभी इसका उपयोग तब किया जाता है जब मॉड्यूलर एक्सपोनेंटिएशन के लिए कार्यान्वयन पहले से ही उपलब्ध होता है। इस पद्धति के कुछ नुकसानों में शामिल हैं:

• मूल्य $\phi (m)$ ज्ञात होना चाहिए और सबसे कुशल ज्ञात गणना की आवश्यकता है m का गुणनखंडन. व्यापक रूप से माना जाता है कि गुणनखंडन एक कम्प्यूटेशनल रूप से कठिन समस्या है। हालाँकि, गणना $\phi (m)$ का अभाज्य गुणनखंडन होने पर यह सीधा है m ज्ञात है।
• घातांक की सापेक्ष लागत. यद्यपि बड़े मान होने पर इसे मॉड्यूलर घातांक का उपयोग करके अधिक कुशलता से कार्यान्वित किया जा सकता है m इसमें शामिल हैं इसकी गणना मोंटगोमरी कटौती पद्धति से सबसे कुशलता से की जाती है। इस एल्गोरिदम को स्वयं एक मॉड्यूलर व्युत्क्रम मॉड की आवश्यकता होती है m, जिसकी गणना सबसे पहले की जानी थी। मोंटगोमरी विधि के बिना, मानक बाइनरी घातांक, जिसके लिए डिवीजन मॉड की आवश्यकता होती है m हर कदम पर, धीमी गति से काम करता है जब m बड़ी है।

इस तकनीक का एक उल्लेखनीय लाभ यह है कि इसमें कोई सशर्त शाखाएँ नहीं होती हैं जो के मूल्य पर निर्भर करती हैं a, और इस प्रकार का मूल्य a, जो सार्वजनिक-कुंजी क्रिप्टोग्राफी में एक महत्वपूर्ण रहस्य हो सकता है, को साइड-चैनल हमलों से बचाया जा सकता है। इस कारण से, कर्व25519 का मानक कार्यान्वयन व्युत्क्रम की गणना करने के लिए इस तकनीक का उपयोग करता है।

एकाधिक व्युत्क्रम

अनेक संख्याओं के व्युत्क्रम की गणना करना संभव है a_i, मॉड्यूलो एक सामान्य m, यूक्लिडियन एल्गोरिथम के एकल आह्वान और प्रति अतिरिक्त इनपुट के तीन गुणन के साथ। मूल विचार सभी का उत्पाद बनाना है a_i, उसे उलटा करें, फिर से गुणा करें a_j सभी के लिए j ≠ i केवल वांछित को छोड़ना a⁻¹
_i.

अधिक विशेष रूप से, एल्गोरिथ्म (सभी अंकगणित मॉड्यूलो द्वारा निष्पादित) है m):

1. उपसर्ग योग की गणना करें ${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1}}$ सभी के लिए i ≤ n.
2. गणना करें b⁻¹
   _n किसी भी उपलब्ध एल्गोरिदम का उपयोग करना।
3. के लिए i से n 2 से नीचे, गणना करें
   • a⁻¹
     _i = b⁻¹
     _ib_i−1 और
   • b⁻¹
     _i−1 = b⁻¹
     _ia_i.
4. आखिरकार, a⁻¹
   ₁ = b⁻¹
   ₁.

समानांतर कंप्यूटिंग का फायदा उठाने के लिए रैखिक रूप से बजाय पेड़ संरचना में गुणन करना संभव है।

अनुप्रयोग

मॉड्यूलर गुणक व्युत्क्रम खोजने के एल्गोरिदम में कई अनुप्रयोग हैं जो मॉड्यूलर अंकगणित के सिद्धांत पर निर्भर करते हैं। उदाहरण के लिए, क्रिप्टोग्राफी में मॉड्यूलर अंकगणित का उपयोग कुछ कार्यों को अधिक तेज़ी से और कम भंडारण आवश्यकताओं के साथ पूरा करने की अनुमति देता है, जबकि अन्य ऑपरेशन अधिक कठिन हो जाते हैं। इन दोनों सुविधाओं का उपयोग लाभ के लिए किया जा सकता है। विशेष रूप से, आरएसए एल्गोरिथ्म में, किसी संदेश को एन्क्रिप्ट और डिक्रिप्ट करना संख्याओं की एक जोड़ी का उपयोग करके किया जाता है जो सावधानीपूर्वक चयनित मापांक के संबंध में गुणक व्युत्क्रम होते हैं। इनमें से एक नंबर को सार्वजनिक कर दिया गया है और इसे तीव्र एन्क्रिप्शन प्रक्रिया में उपयोग किया जा सकता है, जबकि डिक्रिप्शन प्रक्रिया में उपयोग किए जाने वाले दूसरे नंबर को छिपाकर रखा जाता है। सार्वजनिक नंबर से छिपे हुए नंबर को निर्धारित करना कम्प्यूटेशनल रूप से असंभव माना जाता है और यही सिस्टम गोपनीयता सुनिश्चित करने के लिए काम करता है। एक अलग संदर्भ में एक अन्य उदाहरण के रूप में, कंप्यूटर विज्ञान में सटीक विभाजन समस्या पर विचार करें जहां आपके पास विषम शब्द-आकार की संख्याओं की एक सूची है, जिनमें से प्रत्येक को विभाजित किया जा सकता है। k और आप उन सभी को विभाजित करना चाहते हैं k. एक समाधान इस प्रकार है:

1. गणना करने के लिए विस्तारित यूक्लिडियन एल्गोरिदम का उपयोग करें k⁻¹, का मॉड्यूलर गुणक व्युत्क्रम k mod 2^w, कहाँ w एक शब्द में बिट्स की संख्या है। यह व्युत्क्रम मौजूद होगा क्योंकि संख्याएँ विषम हैं और मापांक में कोई विषम गुणनखंड नहीं है।
2. सूची में प्रत्येक संख्या के लिए इसे गुणा करें k⁻¹ और परिणाम का सबसे कम महत्वपूर्ण शब्द लें।

कई मशीनों पर, विशेष रूप से विभाजन के लिए हार्डवेयर समर्थन के बिना, विभाजन गुणन की तुलना में धीमा ऑपरेशन है, इसलिए यह दृष्टिकोण काफी गति प्रदान कर सकता है। पहला चरण अपेक्षाकृत धीमा है लेकिन इसे केवल एक बार करने की आवश्यकता है।

मॉड्यूलर गुणक व्युत्क्रमों का उपयोग रैखिक सर्वांगसमताओं की एक प्रणाली का समाधान प्राप्त करने के लिए किया जाता है जिसकी गारंटी चीनी शेष प्रमेय द्वारा दी जाती है।

उदाहरण के लिए, सिस्टम

X ≡ 4 (मॉड 5)

X ≡ 4 (मॉड 7)

X ≡ 6 (मॉड 11)

सामान्य समाधान हैं क्योंकि 5,7 और 11 जोड़ीवार सहअभाज्य हैं। द्वारा एक समाधान दिया गया है

X = t₁ (7 × 11) × 4 + t₂ (5 × 11) × 4 + t₃ (5 × 7) × 6

कहाँ

t₁ = 3, 7 × 11 (मॉड 5) का मॉड्यूलर गुणक व्युत्क्रम है,

t₂ = 6, 5 × 11 (मॉड 7) का मॉड्यूलर गुणक व्युत्क्रम है और

t₃ = 6, 5 × 7 (मॉड 11) का मॉड्यूलर गुणक व्युत्क्रम है।

इस प्रकार,

X = 3 × (7 × 11) × 4 + 6 × (5 × 11) × 4 + 6 × (5 × 7) × 6 = 3504

और अपने अनूठे संक्षिप्त रूप में

X ≡ 3504 ≡ 39 (मॉड 385)

चूँकि 385, 5,7 और 11 का लघुत्तम समापवर्तक है।

इसके अलावा, मॉड्यूलर गुणक व्युत्क्रम क्लोस्टरमैन योग की परिभाषा में प्रमुखता से आता है।

यह भी देखें

• व्युत्क्रम सर्वांगसम जनरेटर - एक छद्म-यादृच्छिक संख्या जनरेटर जो मॉड्यूलर गुणक व्युत्क्रमों का उपयोग करता है
• तर्कसंगत पुनर्निर्माण (गणित)

संदर्भ

• Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (2nd ed.), Springer-Verlag, ISBN 0-387-97329-X
• Rosen, Kenneth H. (1993), Elementary Number Theory and its Applications (3rd ed.), Addison-Wesley, ISBN 978-0-201-57889-8
• Schumacher, Carol (1996). Chapter Zero: Fundamental Notions of Abstract Mathematics. Addison-Wesley. ISBN 0-201-82653-4.
• Trappe, Wade; Washington, Lawrence C. (2006), Introduction to Cryptography with Coding Theory (2nd ed.), Prentice-Hall, ISBN 978-0-13-186239-5

बाहरी संबंध

• Weisstein, Eric W. "Modular Inverse". MathWorld.
• Guevara Vasquez, Fernando provides a solved example of solving the modulo multiplicative inverse using Euclid's Algorithm