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

गणित में, विशेष रूप से अंकगणित के क्षेत्र में, एक पूर्णांक 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)$ है।

इस स्थिति में कि 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^{2}$ के संबंध में $n+1$ का मॉड्यूलर गुणक व्युत्क्रम है, क्योंकि $(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}}$ में प्रत्येक पूर्णांक सर्वांगसमता को संतुष्ट करेगा क्योंकि इन पूर्णांकों में कुछ पूर्णांक r और $3(7+10r)-1=21+30r-1=20+30r=10(2+3r),$ के लिए 7 + 10r का रूप होता है।

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

सर्वांगसमता वर्गों ${\overline {5}}$ और ${\overline {8}}$ का उत्पाद ${\overline {5}}$ का एक तत्व, मान लीजिए 25, और ${\overline {8}}$ का एक तत्व, मान लीजिए −2, का चयन करके और यह देखकर प्राप्त किया जा सकता है कि उनका उत्पाद (25)(−2) ) = −50 सर्वांगसमता वर्ग में है। इस प्रकार,${\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: विस्तारित यूक्लिडियन एल्गोरिथ्म

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

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

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

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

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

वह है,

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

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

बड़े O नोटेशन में, यह एल्गोरिथम |a| < m मानकर समय O(log²(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 के गुणनखंड की आवश्यकता होती है। व्यापक रूप से माना जाता है कि गुणनखंडन एक कम्प्यूटेशनल रूप से कठिन समस्या है। चूँकि जब m का अभाज्य गुणनखंड ज्ञात हो तो $\phi (m)$ की गणना करना सरल होता है।
• घातांक की सापेक्ष निवेश यद्यपि इसे मॉड्यूलर घातांक का उपयोग करके अधिक कुशलता से कार्यान्वित किया जा सकता है, जब m के बड़े मूल्य सम्मिलित होते हैं तो इसकी गणना मोंटगोमरी कमियों विधि के साथ सबसे कुशलता से की जाती है। इस एल्गोरिदम के लिए स्वयं एक मॉड्यूलर व्युत्क्रम मॉड m की आवश्यकता होती है, जिसकी गणना सबसे पहले की जानी थी। मोंटगोमरी विधि के बिना, मानक बाइनरी घातांक, जिसके लिए हर चरण पर विभाजन मॉड m की आवश्यकता होती है, m बड़ा होने पर एक धीमा संचालन होता है।

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

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

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

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

1. सभी i ≤ n के लिए उपसर्ग उत्पादों ${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1}}$ की गणना करें।
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 mod 2^w के मॉड्यूलर गुणक व्युत्क्रम k⁻¹ की गणना करने के लिए विस्तारित यूक्लिडियन एल्गोरिदम का उपयोग करें, जहां 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