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

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

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

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

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

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

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

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

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

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

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

किसी दिए गए सकारात्मक पूर्णांक 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' मापांक 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}$ और $\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: पूर्णांकों का गुणक समूह मॉड्यूलो एन

संपूर्ण अवशेष प्रणाली मॉड्यूलो का प्रत्येक तत्व नहीं 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