मोंटगोमरी मॉड्यूलर गुणन: Difference between revisions

Latest revision as of 16:16, 29 May 2023

मॉड्यूलर अंकगणितीय संगणना में, मोंटगोमरी मॉड्यूलर गुणन जिसे प्रायः मोंटगोमरी गुणन के रूप से भी जाना जाता है, यह सफलता और तीव्रता से मॉड्यूलर गुणन करने की विधि है। इसे 1985 में अमेरिकी गणितज्ञ पीटर मॉन्टगोमरी (गणितज्ञ) द्वारा प्रस्तुत किया गया था।^[1]^[2]

मोंटगोमरी मॉड्यूलर गुणन संख्याओं के विशेष प्रतिनिधित्व पर निर्भर करता है जिसे मोंटगोमरी फॉर्म कहा जाता है। यह एल्गोरिथ्म मोंटगोमरी रूपों का उपयोग करता है, इस प्रकार $a$ और $b$ के मोंटगोमरी रूप की कुशलतापूर्वक गणना करने के लिए $ab mod N$ की दक्षता को भाजक के संचालन से प्रयुक्त होती है। मौलिक रूप से मॉड्यूलर गुणन डबल-चौड़ाई वाले उत्पाद को कम करता है, इस प्रकार $ab$ विभाजन का उपयोग करके $N$ और केवल शेष को रखते हुए इस विभाजन के लिए भागफल अंकों के अनुमान और सुधार की आवश्यकता है। इसके विपरीत मोंटगोमरी रूप स्थिरांक $R > N$ पर निर्भर करता है, जो कि कोप्राइम पूर्णांक है मुख्य रूप से $N$ , और मोंटगोमरी गुणन में आवश्यक एकमात्र विभाजन $R$ है। इस प्रकार $R$ को चुना जाता है जिससे कि विभाजन द्वारा $R$ सरल है, कलन की गति में अधिक सुधार करता है। व्यवहारिक रूप से, $R$ सदैव दो की घात को प्रकट करता हैं, क्योंकि दो की घात द्वारा विभाजन को लघु स्थानांतरण द्वारा लागू करता है।

इस कारण इसे परिवर्तित करने की आवश्यकता है। इस प्रकार $a$ और $b$ मोंटगोमरी रूप में और उनके उत्पाद मोंटगोमरी रूप से बाहर का अर्थ है कि मोंटगोमरी गुणन द्वारा एकल उत्पाद की गणना पारंपरिक या बैरेट कटौती कलन की तुलना में धीमी है। चूंकि, पंक्ति में कई गुणन करते समय, जैसा कि मॉड्यूलर घातांक में होता है, मध्यवर्ती परिणाम मोंटगोमरी रूप में छोड़े जा सकते हैं। इसके कारण प्रारंभिक और अंतिम रूपांतरण समग्र संगणना का नगण्य अंश बन जाता है। इस प्रकार आरएसए (क्रिप्टोसिस्टम) और डिफी-हेलमैन की एक्सचेंज जैसे कई महत्वपूर्ण क्रिप्टो सिस्टम अंकगणितीय संचालन मोडुलो बड़ी विषम संख्या पर आधारित हैं, और इन क्रिप्टोसिस्टम्स के लिए, मोंटगोमरी गुणन का उपयोग करके संगणना $R$ की घात दो को उपलब्ध विकल्पों से अधिक उपयोगी माना जाता है।^[3]

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

$N$ धनात्मक पूर्णांक मापांक दर्शाता है। इस प्रकार भागफल की रिंग को $Z / N Z$ में $N$ अवशेषों वाले वर्ग मॉड्यूल सम्मिलित रहते हैं, अर्ताथ इसके तत्व फॉर्म के समुच्चय हैं, जो इस प्रकार हैं-

\{a+kN\colon k\in \mathbf {Z} \},

जहाँ $a$ पूर्णांकों के बीच है। प्रत्येक अवशेष वर्ग पूर्णांकों का समूह है जैसे कि समुच्चय में किसी भी दो पूर्णांकों का अंतर विभाज्य $N$ है और अवशेष वर्ग उस संपत्ति के संबंध में अधिकतम है; पूर्णांकों को अवशेष वर्ग से बाहर नहीं छोड़ा जाता है जब तक कि वे विभाज्यता की स्थिति का उल्लंघन नहीं करते हैं। इस प्रकार अवशेष वर्ग के अनुरूप $a$ तथा $a$ द्वारा अंकित किया जाता है, इस प्रकार अवशेष वर्गों की समानता को सर्वांगसमता कहा जाता है और इसे इस प्रकार निरूपित किया जाता है।

{\bar {a}}\equiv {\bar {b}}{\pmod {N}}.

कंप्यूटर पर संपूर्ण अवशेष वर्ग को संग्रहीत करना असंभव है क्योंकि अवशेष वर्ग में अधिकांशतः कई तत्व होते हैं। इसके अतिरिक्त अवशेष वर्गों को प्रतिनिधि के रूप में संग्रहीत किया जाता है। परंपरागत रूप से, ये प्रतिनिधि पूर्णांक होते हैं, जहाँ पर $a$ जिसके लिए $0 \leq a \leq N - 1$ मान उपयोगी हैं जिसके अनुसार यदि $a$ पूर्णांक है, तो इसका प्रतिनिधि $a$ है जिसको $a mod N$ लिखा जाता है। इस प्रकार सर्वांगसमता लिखते समय, पूर्णांक की पहचान उस अवशेष वर्ग के साथ करना सरल है जो यह प्रतिनिधित्व करता है। इस परिपाटी के साथ उपरोक्त समानता $a \equiv b mod N$ लिखी जाती है।

अवशेष वर्गों पर अंकगणित पहले उनके प्रतिनिधियों पर पूर्णांक अंकगणित करके किया जाता है। पूर्णांक ऑपरेशन का आउटपुट अवशेष वर्ग को निर्धारित करता है, और मॉड्यूलर ऑपरेशन का आउटपुट अवशेष वर्ग के प्रतिनिधि की गणना करके निर्धारित किया जाता है। उदाहरण के लिए, यदि $N = 17$ , फिर अवशेष वर्गों का योग $7$ और $15$ की गणना पूर्णांक योग $7 + 15 = 22$ द्वारा ज्ञात करके की जाती है, इस कारण पुनः इसका निर्धारण $22 mod 17$ , 0 और 16 के बीच का पूर्णांक जिसका अंतर 22 के साथ 17 का गुणक है। इस स्थिति में, वह पूर्णांक 5 है, इसलिए $7 + 15 \equiv 5 mod 17$ मान उपयोग किया जाता हैं।

मोंटगोमरी फॉर्म

यदि $a$ और $b$ श्रेणी में पूर्णांक $[0, N - 1]$ हैं, तो उनका योग सीमा $[0, 2 N - 2]$ में है और उनका अंतर सीमा में $[- N + 1, N - 1]$ है, इसलिए प्रतिनिधि का निर्धारण करना $[0, N - 1]$ के लिए अधिकतम घटाव या जोड़ को क्रमशः $N$ के लिए आवश्यक है, चूंकि, उत्पाद $ab$ की सीमा $[0, N 2 - 2 N + 1]$ में है। मध्यवर्ती पूर्णांक उत्पाद का भंडारण $ab$ को या तो दोगुने बिट्स की आवश्यकता होती है इस प्रकार $a$ या $b$ , और कुशलता से प्रतिनिधि का निर्धारण $[0, N - 1]$ विभाजन की आवश्यकता है। गणितीय रूप से, 0 और के बीच का पूर्णांक $N - 1$ के अनुरूप है $ab$ को यूक्लिडियन डिवीजन प्रमेय के कथन को लागू करके व्यक्त किया जा सकता है:

ab=qN+r,

जहाँ $q$ भागफल है $\lfloor ab/N\rfloor$ और $r$ , शेष, अंतराल में है $[0, N - 1]$ . शेष $r$ है, इस कारण $ab mod N$ के निर्धारण $r$ कंप्यूटिंग $q$ द्वारा किया जा सकता है, फिर घटाना $qN$ से $ab$ . उदाहरण के लिए, फिर से $N=17$ , उत्पाद $7 \cdot 15$ कंप्यूटिंग द्वारा $7\cdot 15=105$ पर इसका निर्धारण किया जाता है, इसे विभाजित करना $\lfloor 105/17\rfloor =6$ , और घटाना $105-6\cdot 17=105-102=3$ सरल हो जाता हैं।

क्योंकि की गणना $q$ विभाजन की आवश्यकता है, यह अधिकांश कंप्यूटर हार्डवेयर पर अवांछनीय रूप से महंगा है। मोंटगोमरी फॉर्म रिंग के तत्वों को व्यक्त करने का अलग तरीका है जिसमें मॉड्यूलर उत्पादों की गणना महंगे डिवीजनों के बिना की जा सकती है। जबकि विभाजन अभी भी आवश्यक हैं, उन्हें अलग भाजक $R$ के संबंध में किया जा सकता है। इस विभाजक को दो की शक्ति के रूप में चुना जा सकता है, जिसके लिए विभाजन को शिफ्टिंग, या मशीनी शब्दों की पूरी संख्या से परिवर्तित किया जा सकता है, जिसके लिए शब्दों को छोड़ कर विभाजन को परिवर्तित किया जा सकता है। ये विभाजन तेज़ हैं, इसलिए मोंटगोमरी फॉर्म का उपयोग करके मॉड्यूलर उत्पादों की गणना करने की अधिकांश लागत साधारण उत्पादों की गणना करने की लागत है।

सहायक मापांक $R$ धनात्मक पूर्णांक होना चाहिए जैसे कि $gcd(R, N) = 1$ इसका उदाहरण हैं। इस प्रकार कम्प्यूटरीकृत उद्देश्यों के लिए यह भी आवश्यक है कि विभाजन और कमी के लिए मोडुलो $R$ सरल हैं, और मॉड्यूलस मॉड्यूलर गुणन के लिए तब तक उपयोगी नहीं है जब तक $R > N$ अवशेष वर्ग का मोंटगोमरी रूप $a$ हैं। इसके संबंध में $R$ है $aR mod N$ , अर्थात यह अवशेष वर्ग $aR$ का प्रतिनिधि है, उदाहरण के लिए, मान लीजिए $N = 17$ ओर वो $R = 100$ . 3, 5, 7 और 15 के मोंटगोमरी $300 mod 17 = 11$ , $500 mod 17 = 7$ , $700 mod 17 = 3$ , और $1500 mod 17 = 4$ का रूप हैं।

मोंटगोमरी रूप में जोड़ और घटाव वितरण नियम के कारण सामान्य मॉड्यूलर जोड़ और घटाव के समान हैं:

aR+bR=(a+b)R,

aR-bR=(a-b)R.

यह इस तथ्य का परिणाम है कि, क्योंकि $gcd(R, N) = 1$ , गुणा करके $R$ योज्य समूह पर समरूपता $Z / N Z$ है, उदाहरण के लिए, $(7 + 15) mod 17 = 5$ , जो मोंटगोमरी रूप $(3 + 4) mod 17 = 7$ में बन जाता है।

मॉन्टगोमरी रूप में गुणन, चूंकि, अधिक जटिल प्रतीत होता है। का सामान्य उत्पाद $aR$ और $bR$ के उत्पाद का प्रतिनिधित्व नहीं करता है, इस प्रकार $a$ और $b$ क्योंकि इसका अतिरिक्त कारक $R$ है :

(aR{\bmod {N}})(bR{\bmod {N}}){\bmod {N}}=(abR)R{\bmod {N}}.

मोंटगोमरी रूप में कंप्यूटिंग उत्पादों के अतिरिक्त कारक को $R$ द्वारा हटाने की आवश्यकता होती है, जबकि विभाजन द्वारा $R$ सस्ता है, मध्यवर्ती उत्पाद है, इस कारण $(aR mod N)(bR mod N)$ से विभाज्य नहीं है $R$ क्योंकि मॉडुलो ऑपरेशन ने उस संपत्ति को नष्ट कर दिया है। उदाहरण के लिए, 7 और 15 मॉड्यूल 17 के मोंटगोमरी रूपों का उत्पाद 3 और 4 का उत्पाद है, जो कि 12 है। चूंकि 12 100 से विभाज्य नहीं है, इसलिए अतिरिक्त कारक को हटाने के लिए $R$ के अतिरिक्त प्रयास की आवश्यकता है।

जिसके अतिरिक्त कारक को हटाना $R$ को पूर्णांक से गुणा करके $R'$ को प्राप्त किया जा सकता है, ऐसा है कि $RR' \equiv 1 (mod N)$ , अर्ताथ द्वारा $R'$ जिसका अवशेष वर्ग मॉड्यूलर व्युत्क्रम $R$ है, इसके विरुद्ध $N$ पुनः, कार्य कर रहे मॉड्यूल $N$ , को इस प्रकार प्राप्त करते हैं।

(aR{\bmod {N}})(bR{\bmod {N}})R'\equiv (aR)(bR)R^{-1}\equiv (ab)R{\pmod {N}}.

पूर्णांक $R'$ इस धारणा के कारण सम्मिलित है कि $R$ और $N$ को-प्राइम हैं। इसका निर्माण विस्तारित यूक्लिडियन कलन का उपयोग करके किया जा सकता है। विस्तारित यूक्लिडियन एल्गोरिथ्म कुशलतापूर्वक पूर्णांकों को निर्धारित करता है, इस प्रकार $R'$ और $N'$ जो बेज़ाउट की पहचान को संतुष्ट करते हैं:

$0 < R' < N$ , $0 < N' < R$ , और:

RR'-NN'=1.

इससे पता चलता है कि मोंटगोमरी रूप में गुणा करना संभव है। मोंटगोमरी रूप में संख्याओं को गुणा करने के लिए सीधा कलन इसलिए गुणा करना है, इस प्रकार $aR mod N$ , $bR mod N$ , और $R'$ पूर्णांक के रूप में और मॉड्यूल $N$ को कम करते हैं।

उदाहरण के लिए, 7 और 15 मॉड्यूल 17 को मोंटगोमरी फॉर्म में फिर से गुणा करने के लिए $R = 100$ , उपरोक्तानुसार 12 प्राप्त करने के लिए 3 और 4 के गुणनफल की गणना करते हैं। इस प्रकार विस्तारित यूक्लिडियन एल्गोरिथ्म का तात्पर्य है $8\cdot100 - 47\cdot17 = 1$ , इसलिए $R' = 8$ . 96 प्राप्त करने के लिए 12 को 8 से गुणा करें और 11 प्राप्त करने के लिए मॉडुलो 17 को कम करें। यह अपेक्षा के अनुरूप 3 का मोंटगोमरी रूप है।

आरईडीसी कलन

जबकि उपरोक्त कलन सही है, यह गुणा करने की आवश्यकता के कारण मानक प्रतिनिधित्व में गुणा $R'$ से कम है, और $N$ से विभाजित करते हैं। मोंटगोमरी रिडक्शन, जिसे आरईडीसी के रूप में भी जाना जाता है, एल्गोरिथ्म है जो साथ उत्पाद की गणना $R'$ करता है और मॉड्यूलो को कम करता है, $N$ विधि की तुलना में अधिक तेज़ी से किया जाता हैं। पारंपरिक मॉड्यूलर कमी के विपरीत, जो संख्या को इससे छोटा बनाने पर $N$ का मान केंद्रित रहता है, मोंटगोमरी के मान में कटौती के कारण यह संख्या को और अधिक विभाज्य बनाने पर $R$ केंद्रित रहता है, यह छोटे गुणक को $N$ द्वारा जोड़कर ऐसा करता है, जिसे अवशेष मोडुलो को निरस्त करने के लिए $R$ को चुना जाता है, जिससे परिणाम विभाजित करना $R$ बहुत कम संख्या देता है। यह संख्या इतनी कम है कि यह लगभग रिडक्शन मॉडुलो $N$ है, और कमी मोडुलो की गणना $N$ केवल अंतिम सशर्त घटाव की आवश्यकता है। क्योंकि सभी संगणनाओं के संबंध में केवल कमी और विभाजन का उपयोग करके किया जाता है $R$ , नहीं $N$ , एल्गोरिद्म विभाजन द्वारा सीधी मॉड्यूलर कमी की तुलना में तेज़ी से चलता है।

function REDC is
    input: Integers R and N with gcd(R, N) = 1,
           Integer N′ in [0, R − 1] such that NN′ ≡ −1 mod R,
           Integer T in the range [0, RN − 1].
    output: Integer S in the range [0, N − 1] such that S ≡ TR⁻¹ mod N

    m ← ((T mod R)N′) mod R
    t ← (T + mN) / R
    if t ≥ N then
        return t − N
    else
        return t
    end if

end function

यह देखने के लिए कि यह कलन सही है, पहले उसका निरीक्षण करें $m$ ठीक से चुना जाता है जिससे कि $T + mN$ मुख्य रूप से $R$ से विभाज्य है, इस प्रकार $R$ संख्या से विभाज्य है, यदि यह शून्य मॉड $R$ के अनुरूप है, इस प्रकार हमें उक्त समीकरण प्राप्त होता हैं:

T+mN\equiv T+(((T{\bmod {R}})N'){\bmod {R}})N\equiv T+TN'N\equiv T-T\equiv 0{\pmod {R}}.

इसलिए $t$ पूर्णांक है। इसका दूसरा मान आउटपुट या तो $t$ या $t - N$ है, दोनों के सर्वांगसम $t mod N$ हैं , तो यह प्रमाणित करने के लिए कि आउटपुट सर्वांगसम $TR -1 mod N$ है , यह प्रमाणित करने के लिए पर्याप्त है $t$ है। सापेक्ष $N$ , $t$ संतुष्ट करता है:

t\equiv (T+mN)R^{-1}\equiv TR^{-1}+(mR^{-1})N\equiv TR^{-1}{\pmod {N}}.

इसलिए, आउटपुट में सही अवशेष वर्ग है। $[0, R - 1]$ का तीसरा मान $m$ में है , और इसलिए $T + mN$ 0 और के बीच $(RN - 1) + (R - 1) N < 2 RN$ है, इस प्रकार $t$ मै रुक जाना $2 N$ , और क्योंकि यह पूर्णांक है, यह डालता है, इस प्रकार $t$ सीमा में $[0, 2 N - 1]$ को इसलिए कम कर रहा है, इस प्रकार $t$ वांछित सीमा में अधिकतम घटाव की आवश्यकता होती है, इसलिए कलन का आउटपुट सही सीमा में होता है।

7 और 15 मॉड्यूल 17 के उत्पाद की गणना करने के लिए आरईडीसी का उपयोग करने के लिए, पहले मोंटगोमेरी फॉर्म में कनवर्ट करें और उपरोक्त के रूप में 12 प्राप्त करने के लिए पूर्णांक के रूप में गुणा करें। इसके पश्चात आरईडीसी अप्लाई करें $R = 100$ , $N = 17$ , $N' = 47$ , और $T = 12$ हैं। इसके पहले चरण $m$ को $12 \cdot 47 mod 100 = 64$ पर तय किया जाता है, इसका दूसरा चरण $t$ को तय करते हैं, इस प्रकार $(12 + 64 \cdot 17) / 100$ जिसके लिए $12 + 64 \cdot 17$ का मान 1100 है, इसके अनुसार 100 का गुणक $t$ 11 पर समुच्चय है, जो 17 से कम है, इसलिए अंतिम परिणाम 11 है, जो पिछले अनुभाग की गणना से सहमत है।

एक अन्य उदाहरण के रूप में, उत्पाद पर विचार करें $7 \cdot 15 mod 17$ अपितु इसके साथ $R = 10$ . विस्तारित यूक्लिडियन कलन का उपयोग करके $-5 \cdot 10 + 3 \cdot 17 = 1$ की गणना करें, इसलिए $N'$ होगा $-3 mod 10 = 7$ . 7 और 15 के मोंटगोमरी रूप $70 mod 17 = 2$ और $150 mod 17 = 14$ हैं। $T$ आरईडीसी के लिए उनका उत्पाद 28 इनपुट है, और उसके पश्चात $28 < RN = 170$ , आरईडीसी की धारणाएं संतुष्ट हैं। इस प्रकार आरईडीसी चलाने के लिए, समुच्चय करें $m$ को $(28 mod 10) \cdot 7 mod 10 = 196 mod 10 = 6$ तथा इसके पश्चात $28 + 6 \cdot 17 = 130$ पर हल करते हैं, इसलिए $t = 13$ मान उपयोग करते हैं क्योंकि $30 mod 17 = 13$ , यह मोंटगोमरी $3 = 7 \cdot 15 mod 17$ का रूप है।

मोंटगोमरी रूप में अंकगणित

इन मॉड्यूल की कई संचालन $N$ मोंटगोमरी रूप में समान रूप से अच्छी तरह से व्यक्त किया जा सकता है। इस प्रकार जोड़, घटाव, निषेध, समानता के लिए तुलना, पूर्णांक द्वारा गुणा जो मोंटगोमरी रूप में नहीं है, और सबसे बड़ा सामान्य विभाजक है $N$ सभी मानक कलन के साथ किया जा सकता है। जैकोबी प्रतीक की गणना इस प्रकार की जा सकती है ${\big (}{\tfrac {a}{N}}{\big )}={\big (}{\tfrac {aR}{N}}{\big )}/{\big (}{\tfrac {R}{N}}{\big )}$ जब तक कि ${\big (}{\tfrac {R}{N}}{\big )}$ रखा है।

जब $R > N$ , अधिकांश अन्य अंकगणितीय संक्रियाएँ REDC के संदर्भ में व्यक्त की जा सकती हैं। इस धारणा का तात्पर्य है कि दो प्रतिनिधियों के उत्पाद मॉड $N$ मै रुक जाना $RN$ , सही आउटपुट उत्पन्न करने के लिए REDC के लिए आवश्यक सटीक परिकल्पना की जाती हैं। विशेष रूप से, का उत्पाद $aR mod N$ और $bR mod N$ है, जिसके लिए $REDC((aR mod N)(bR mod N))$ गुणा और आरईडीसी के संयुक्त संचालन को अधिकांशतः मोंटगोमरी गुणन कहा जाता है।

मोंटगोमरी रूप में रूपांतरण $REDC((a mod N)(R 2 mod N))$ कंप्यूटिंग द्वारा किया जाता है, इस प्रकार कंप्यूटिंग द्वारा मोंटगोमरी फॉर्म $REDC(aR mod N)$ से रूपांतरण किया जाता है, जिसका मॉड्यूलर व्युत्क्रम $aR mod N$ है $REDC((aR mod N) -1 (R 3 mod N))$ प्रारंभिक गुणनफल को 1 के मोंटगोमरी निरूपण के लिए प्रारंभ करके, वर्ग करके घातांक का उपयोग करके मॉड्यूलर घातांक किया जा सकता है, अर्थात $R mod N$ , और मोंटगोमरी गुणा द्वारा गुणा और वर्ग चरणों को प्रतिस्थापित करके प्राप्त होता हैं।

इन परिचालनों को करने के लिए कम से कम जानना आवश्यक है $N'$ और $R 2 mod N$ जब $R$ छोटे धनात्मक पूर्णांक की शक्ति है $b$ , $N'$ की गणना हेंसल लेम्मा द्वारा की जा सकती है: का व्युत्क्रम $N$ मापांक $b$ की गणना भोले कलन द्वारा की जाती है (उदाहरण के लिए, if $b = 2$ तो व्युत्क्रम 1 है), और हेंसल की लेम्मा का उपयोग बार-बार व्युत्क्रम मॉड्यूल $b$ उच्च और उच्च शक्तियों को खोजने के लिए किया जाता है, जब व्युत्क्रम मोडुल रुक जाता है $R$ ज्ञात है; $N'$ इस व्युत्क्रम का निषेध है। स्थिरांक $R mod N$ और $R 3 mod N$ के रूप में तथा $REDC(R 2 mod N)$ और के रूप में उत्पन्न किया जा सकता है। $REDC((R 2 mod N)(R 2 mod N))$ मौलिक ऑपरेशन किसी उत्पाद के आरईडीसी की गणना करना है। जब स्टैंडअलोन आरईडीसी की आवश्यकता होती है, तो इसकी गणना किसी उत्पाद के आरईडीसी के रूप $1 mod N$ में की जा सकती है, इसका एकमात्र स्थान जहां प्रत्यक्ष कमी $N$ मोडुल है आवश्यक है कि इसका पूर्वगणना $R 2 mod N$ में रखा जाता है।

मल्टीप्रिसिजन पूर्णांकों पर मोंटगोमरी अंकगणित

अधिकांश क्रिप्टोग्राफ़िक अनुप्रयोगों के लिए संख्याओं की आवश्यकता होती है जो सैकड़ों या हजारों बिट्स लंबी होती हैं। ऐसी संख्याएँ मशीन शब्द में संग्रहीत करने के लिए बहुत बड़ी हैं। सामान्यतः, हार्डवेयर गुणन मॉड को कुछ आधार करता है $B$ , इसलिए बड़े गुणा करने के लिए कई छोटे गुणाओं के संयोजन की आवश्यकता होती है। आधार $B$ सामान्यतः माइक्रोइलेक्ट्रॉनिक अनुप्रयोगों के लिए 2 होता है, इस कारण 2⁸ 8-बिट फ़र्मवेयर के लिए,^[4] या 2³² या 2⁶⁴ सॉफ्टवेयर अनुप्रयोगों के लिए करते हैं।

REDC एल्गोरिद्म के लिए उत्पाद मॉड्यूल $R$ की आवश्यकता होती है, और सामान्यतः $R > N$ जिससे कि उत्पादों की गणना करने के लिए आरईडीसी का उपयोग किया जा सके। चूंकि, कब $R$ की शक्ति है $B$ , REDC का प्रकार है जिसके लिए केवल मशीन शब्द आकार के पूर्णांकों के उत्पादों की आवश्यकता होती है। मान लीजिए कि धनात्मक बहु-परिशुद्धता पूर्णांक थोड़ा एंडियन संग्रहीत हैं, अर्थात, $x$ को सरणी $x [0], ..., x [ℓ - 1]$ के रूप में संग्रहीत किया जाता है, इसका मान इस प्रकार हैं कि $0 \leq x [i] < B$ सभी के लिए $i$ और $x = \sum x [i] B i$ . कलन बहु-परिशुद्धता पूर्णांक से प्रारंभ होता है $T$ और इसे बार में शब्द कम कर देता है। पहले का उपयुक्त गुणक $N$ बनाने के लिए $T$ द्वारा विभाज्य $B$ जोड़ा जाता है, फिर का गुणक $N$ बनाने के लिए जोड़ा जाता है, इस प्रकार $T$ द्वारा विभाज्य $B 2$ , और इसी प्रकार अंततः $T$ से विभाज्य है $R$ , और विभाजन के पश्चात $R$ कलन उसी स्थान पर है जहाँ REDC की गणना $t$ के पश्चात की गयी थी।

function MultiPrecisionREDC is
    Input: Integer N with gcd(B, N) = 1, stored as an array of p words,
           Integer R = B^r,     --thus, r = log_B R
           Integer N′ in [0, B − 1] such that NN′ ≡ −1 (mod B),
           Integer T in the range 0 ≤ T < RN, stored as an array of r + p words.

    Output: Integer S in [0, N − 1] such that TR⁻¹ ≡ S (mod N), stored as an array of p words.

    Set T[r + p] = 0  (extra carry word)
    for 0 ≤ i < r do
        --loop1- Make T divisible by Bⁱ⁺¹

        c ← 0
        m ← T[i] ⋅ N′ mod B
        for 0 ≤ j < p do
            --loop2- Add the low word of m ⋅ N[j] and the carry from earlier, and find the new carry

            x ← T[i + j] + m ⋅ N[j] + c
            T[i + j] ← x mod B
            c ← ⌊x / B⌋
        end for
        for p ≤ j ≤ r + p − i do
            --loop3- Continue carrying

            x ← T[i + j] + c
            T[i + j] ← x mod B
            c ← ⌊x / B⌋
        end for
    end for

    for 0 ≤ i < p do
        S[i] ← T[i + r]
    end for

    if S ≥ N then
        return S − N
    else
        return S
    end if

end function

अंतिम तुलना और घटाव मानक कलन द्वारा किया जाता है।

उपरोक्त एल्गोरिथ्म अनिवार्य रूप से उन्हीं कारणों से सही है जो REDC सही हैं। हर बार के माध्यम से $i$ कुंडली, $m$ चुना जाता है जिससे कि $T [i] + mN [0]$ से विभाज्य है $B$ . तब $mNB i$ जोड़ा जाता है $T$ . क्योंकि यह मात्रा जीरो मॉड है $N$ , इसे जोड़ने से का मान $T mod N$ प्रभावित नहीं होता है। इस प्रकार यदि $m i$ के मान को दर्शाता है $m$ में गणना की गई {{mvar|i}लूप का } वाँ पुनरावृत्ति, फिर कलन समुच्चय करता है जिसके लिए $S$ को $T + (\sum m i B i) N$ द्वारा दर्शाते हैं क्योंकि मल्टी प्रेसिजन REDC और REDC ही आउटपुट का उत्पादन करते हैं, यह योग विकल्प के समान है $m$ कि REDC कलन बना देगा।

का अंतिम शब्द $T$ , $T [r + p]$ (और इसके परिणामस्वरूप $S [p]$ ), का उपयोग केवल कैरी रखने के लिए किया जाता है, क्योंकि प्रारंभिक कमी का परिणाम की सीमा में परिणाम के लिए बाध्य होता है $0 \leq S < 2N$ . इससे यह निष्कर्ष निकलता है कि इस अतिरिक्त कैरी शब्द से पूर्ण रूप से बचा जा सकता है यदि यह पहले से ज्ञात हो $R \geq 2N$ जिसका विशिष्ट बाइनरी कार्यान्वयन पर, यह कहने के बराबर है कि यदि बिट्स की संख्या हो तो इस कैरी शब्द से बचा जा सकता है $N$ बिट्स की संख्या से छोटा है $R$ . अन्यथा, वहन या तो शून्य या होगा। प्रोसेसर के आधार पर, इस शब्द को पूर्ण आकार के शब्द के अतिरिक्त कैरी फ़्लैग के रूप में संग्रहीत करना संभव हो सकता है।

मल्टीप्रिसिजन गुणन और आरईडीसी को कलन में जोड़ना संभव है। इस संयुक्त एल्गोरिथ्म को सामान्यतः मोंटगोमरी गुणन कहा जाता है। इस प्रकार Koç, Acar, और Kaliski द्वारा कई अलग-अलग कार्यान्वयनों का वर्णन किया गया है।^[5] इस कारण $p + 2$ स्टोरेज के शब्द प्लस कैरी बिट के लिए एल्गोरिथ्म जितना कम उपयोग कर सकता है ।

एक उदाहरण के रूप में, चलो $B = 10$ , $N = 997$ , और $R = 1000$ के मान पर लगता है कि $a = 314$ और $b = 271$ मोंटगोमरी का प्रतिनिधित्व $a$ और $b$ हैं जिसका मान $314000 mod 997 = 942$ और $271000 mod 997 = 813$ प्राप्त होता हैं। जिसकी गणना करने पर $942 \cdot 813 = 765846$ मान प्राप्त होता हैं। इसका प्रारंभिक इनपुट $T$ से मल्टी प्रेसिजन REDC [6, 4, 8, 5, 6, 7] होगा। जो नंबर $N$ को [7, 9, 9] के रूप में दर्शाया जाता हैं। विस्तारित यूक्लिडियन एल्गोरिथ्म कहता है कि $-299 \cdot 10 + 3 \cdot 997 = 1$ , इसलिए $N'$ का मान 7 होता हैं।

i ← 0
m ← 6 ⋅ 7 mod 10 = 2

j T       c
- ------- -
0 0485670 2    (After first iteration of first loop)
1 0485670 2
2 0485670 2
3 0487670 0    (After first iteration of second loop)
4 0487670 0
5 0487670 0
6 0487670 0

i ← 1
m ← 4 ⋅ 7 mod 10 = 8

j T       c
- ------- -
0 0087670 6    (After first iteration of first loop)
1 0067670 8
2 0067670 8
3 0067470 1    (After first iteration of second loop)
4 0067480 0
5 0067480 0

i ← 2
m ← 6 ⋅ 7 mod 10 = 2

j T       c
- ------- -
0 0007480 2    (After first iteration of first loop)
1 0007480 2
2 0007480 2
3 0007400 1    (After first iteration of second loop)

4 0007401 0

इसलिए, अंतिम तुलना और घटाव से पहले, $S = 1047$ . अंतिम घटाव संख्या 50 देता है। मोंटगोमरी के प्रतिनिधित्व के पश्चात $314 \cdot 271 mod 997 = 349$ है $349000 mod 997 = 50$ , यह अपेक्षित परिणाम है।

बेस 2 में कार्य करते समय, सही का निर्धारण करना $m$ प्रत्येक चरण में विशेष रूप से सरल है: यदि वर्तमान फलन का मान बिट के रूप में सम संख्या के रूप में प्रदर्शित होता है, तो $m$ शून्य है और यदि यह विषम है, तो $m$ है। इसके अतिरिक्त, क्योंकि मल्टी प्रेसिजन REDC के प्रत्येक चरण को केवल सबसे कम बिट जानने की आवश्यकता होती है, मॉन्टगोमरी गुणन को कैरी-सेव योजक के साथ सरलता से जोड़ा जा सकता है।

साइड-चैनल अटैक

चूंकि भागफल अंकों के अनुमान गलत होने पर मॉन्टगोमरी कटौती पारंपरिक विभाजन में आवश्यक सुधार चरणों से बचती है, यह अधिकतम सशर्त शाखाओं से मुक्त है जो समय और पावर साइड-चैनल हमलों के प्राथमिक लक्ष्य हैं, निष्पादित निर्देशों का क्रम इनपुट ऑपरेंड मूल्यों से स्वतंत्र है। इसका एकमात्र अपवाद मापांक का अंतिम सशर्त घटाव है, अपितु इसे प्रतिरोधी बनाने के लिए इसे सरलता से संशोधित किया जाता है इसके लिए सदैव कुछ कमी होने से मापांक शून्य हो जाता हैं।^[4] यह निश्चित रूप से आवश्यक है कि गुणन के समीप निर्मित घातांक एल्गोरिथ्म भी प्रतिरोधी होता हैं।^[4]^[6]

यह भी देखें

बैरेट कमी

संदर्भ

↑ Montgomery, Peter (April 1985). "Modular Multiplication Without Trial Division" (PDF). Mathematics of Computation. 44 (170): 519–521. doi:10.1090/S0025-5718-1985-0777282-X.
↑ Martin Kochanski, "Montgomery Multiplication" Archived 2010-03-27 at the Wayback Machine a colloquial explanation.
↑ Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. ISBN 0-8493-8523-7, chapter 14.
↑ ^4.0 ^4.1 ^4.2 Liu, Zhe; Großschädl, Johann; Kizhvatov, Ilya (29 November 2010). Efficient and Side-Channel Resistant RSA Implementation for 8-bit AVR Microcontrollers (PDF). 1st International Workshop on the Security of the Internet of Things. Tokyo. (Presentation slides.)
↑ Çetin K. Koç; Tolga Acar; Burton S. Kaliski, Jr. (June 1996). "मोंटगोमरी गुणन एल्गोरिदम का विश्लेषण और तुलना" (PDF). IEEE Micro. 16 (3): 26–33. CiteSeerX 10.1.1.26.3120. doi:10.1109/40.502403.
↑ Marc Joye and Sung-Ming Yen. "The Montgomery Powering Ladder". 2002.

बाहरी संबंध

Henry S. Warren, Jr. (July 2012). "Theory and practice of Montgomery multiplication". CiteSeerX 10.1.1.450.6124. {{cite journal}}: Cite journal requires |journal= (help)

[montg1985-1] Montgomery, Peter (April 1985). "Modular Multiplication Without Trial Division" (PDF). Mathematics of Computation. 44 (170): 519–521. doi:10.1090/S0025-5718-1985-0777282-X.

[kochanski-2] Martin Kochanski, "Montgomery Multiplication" Archived 2010-03-27 at the Wayback Machine a colloquial explanation.

[3] Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. ISBN 0-8493-8523-7, chapter 14.

[kizhvatov-4] 4.0 ^4.1 ^4.2 Liu, Zhe; Großschädl, Johann; Kizhvatov, Ilya (29 November 2010). Efficient and Side-Channel Resistant RSA Implementation for 8-bit AVR Microcontrollers (PDF). 1st International Workshop on the Security of the Internet of Things. Tokyo. (Presentation slides.)

[5] Çetin K. Koç; Tolga Acar; Burton S. Kaliski, Jr. (June 1996). "मोंटगोमरी गुणन एल्गोरिदम का विश्लेषण और तुलना" (PDF). IEEE Micro. 16 (3): 26–33. CiteSeerX 10.1.1.26.3120. doi:10.1109/40.502403.

[6] Marc Joye and Sung-Ming Yen. "The Montgomery Powering Ladder". 2002.

[1]

[2]

[3]

[4]

[5]

[6]

Anonymous

Search

मोंटगोमरी मॉड्यूलर गुणन: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 16:16, 29 May 2023

Contents

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

मोंटगोमरी फॉर्म

आरईडीसी कलन

मोंटगोमरी रूप में अंकगणित

मल्टीप्रिसिजन पूर्णांकों पर मोंटगोमरी अंकगणित

साइड-चैनल अटैक

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

@@ Line 1: / Line 1: @@
 {{short description|Algorithm for fast modular multiplication}}
-[[मॉड्यूलर अंकगणित|मॉड्यूलर अंकगणितीय]] संगणना में, '''मोंटगोमरी मॉड्यूलर गुणन''', जिसे सामान्यतः मोंटगोमरी गुणन के रूप में संदर्भित किया जाता है, तेजी से मॉड्यूलर गुणन करने की विधि है। इसे 1985 में अमेरिकी गणितज्ञ पीटर मॉन्टगोमरी (गणितज्ञ) द्वारा प्रस्तुत किया गया था | पीटर एल. मॉन्टगोमरी।<ref name="montg1985">{{cite journal
+[[मॉड्यूलर अंकगणित|मॉड्यूलर अंकगणितीय]] संगणना में, '''मोंटगोमरी मॉड्यूलर गुणन''' जिसे प्रायः मोंटगोमरी गुणन के रूप से भी जाना जाता है, यह सफलता और तीव्रता से मॉड्यूलर गुणन करने की विधि है। इसे 1985 में अमेरिकी गणितज्ञ पीटर मॉन्टगोमरी (गणितज्ञ) द्वारा प्रस्तुत किया गया था।<ref name="montg1985">{{cite journal
 |authorlink=Peter Montgomery (mathematician) |first=Peter |last=Montgomery
 |doi=10.1090/S0025-5718-1985-0777282-X |doi-access=free
@@ Line 9: / Line 9: @@
 }}</ref><ref name="kochanski">Martin Kochanski, [http://www.nugae.com/encryption/fap4/montgomery.htm "Montgomery Multiplication"] {{Webarchive|url=https://web.archive.org/web/20100327211550/http://www.nugae.com/encryption/fap4/montgomery.htm |date=2010-03-27 }} a colloquial explanation.</ref>
-मोंटगोमरी मॉड्यूलर गुणन संख्याओं के विशेष प्रतिनिधित्व पर निर्भर करता है जिसे मोंटगोमरी फॉर्म कहा जाता है। एल्गोरिथ्म मोंटगोमरी रूपों का उपयोग करता है {{mvar|a}} और {{mvar|b}} के मोंटगोमरी रूप की कुशलतापूर्वक गणना करने के लिए {{math|''ab'' mod ''N''}}. दक्षता महंगे डिवीजन संचालन से बचने से आती है। मौलिक मॉड्यूलर गुणन डबल-चौड़ाई वाले उत्पाद को कम करता है {{math|''ab''}} विभाजन का उपयोग करके {{mvar|N}} और केवल शेष को रखते हुए। इस विभाजन के लिए भागफल अंकों के अनुमान और सुधार की आवश्यकता है। इसके विपरीत, मोंटगोमरी रूप स्थिरांक पर निर्भर करता है {{mvar|R > N}} जो कि [[कोप्राइम पूर्णांक]] है {{mvar|N}}, और मोंटगोमरी गुणन में आवश्यक एकमात्र विभाजन द्वारा विभाजन है {{mvar|R}}. अटल {{mvar|R}} चुना जा सकता है जिससे कि विभाजन द्वारा {{mvar|R}} आसान है, एल्गोरिथम की गति में काफी सुधार करता है। व्यवहार में, {{mvar|R}} सदैव दो की शक्ति होती है, क्योंकि दो की शक्तियों द्वारा विभाजन को [[ थोड़ा स्थानांतरण |थोड़ा स्थानांतरण]] द्वारा लागू किया जा सकता है।
+मोंटगोमरी मॉड्यूलर गुणन संख्याओं के विशेष प्रतिनिधित्व पर निर्भर करता है जिसे मोंटगोमरी फॉर्म कहा जाता है। यह एल्गोरिथ्म मोंटगोमरी रूपों का उपयोग करता है, इस प्रकार {{mvar|a}} और {{mvar|b}} के मोंटगोमरी रूप की कुशलतापूर्वक गणना करने के लिए {{math|''ab'' mod ''N''}} की दक्षता को भाजक के संचालन से प्रयुक्त होती है। मौलिक रूप से मॉड्यूलर गुणन डबल-चौड़ाई वाले उत्पाद को कम करता है, इस प्रकार {{math|''ab''}} विभाजन का उपयोग करके {{mvar|N}} और केवल शेष को रखते हुए इस विभाजन के लिए भागफल अंकों के अनुमान और सुधार की आवश्यकता है। इसके विपरीत मोंटगोमरी रूप स्थिरांक {{mvar|R > N}} पर निर्भर करता है, जो कि [[कोप्राइम पूर्णांक]] है मुख्य रूप से {{mvar|N}}, और मोंटगोमरी गुणन में आवश्यक एकमात्र विभाजन {{mvar|R}} है। इस प्रकार {{mvar|R}} को चुना जाता है जिससे कि विभाजन द्वारा {{mvar|R}} सरल है, कलन की गति में अधिक सुधार करता है। व्यवहारिक रूप से, {{mvar|R}} सदैव दो की घात को प्रकट करता हैं, क्योंकि दो की घात द्वारा विभाजन को [[ थोड़ा स्थानांतरण |लघु स्थानांतरण]] द्वारा लागू करता है।
-कन्वर्ट करने की जरूरत है {{mvar|a}} और {{mvar|b}} मोंटगोमरी रूप में और उनके उत्पाद मोंटगोमरी रूप से बाहर का मतलब है कि मोंटगोमरी गुणन द्वारा एकल उत्पाद की गणना पारंपरिक या बैरेट कटौती एल्गोरिदम की तुलना में धीमी है। हालांकि, पंक्ति में कई गुणन करते समय, जैसा कि [[मॉड्यूलर घातांक]] में होता है, मध्यवर्ती परिणाम मोंटगोमरी रूप में छोड़े जा सकते हैं। तब प्रारंभिक और अंतिम रूपांतरण समग्र संगणना का नगण्य अंश बन जाता है। [[आरएसए (क्रिप्टोसिस्टम)]] और डिफी-हेलमैन की एक्सचेंज जैसे कई महत्वपूर्ण क्रिप्टो सिस्टम अंकगणितीय संचालन मोडुलो बड़ी विषम संख्या पर आधारित हैं, और इन क्रिप्टोसिस्टम्स के लिए, मोंटगोमरी गुणन का उपयोग करके संगणना {{mvar|R}} a power of two उपलब्ध विकल्पों से तेज है।<ref>[[Alfred J. Menezes]], Paul C. van Oorschot, and [[Scott A. Vanstone]]. [http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf ''Handbook of Applied Cryptography'']. CRC Press, 1996. {{isbn|0-8493-8523-7}}, chapter 14.</ref>
+इस कारण इसे परिवर्तित करने की आवश्यकता है। इस प्रकार {{mvar|a}} और {{mvar|b}} मोंटगोमरी रूप में और उनके उत्पाद मोंटगोमरी रूप से बाहर का अर्थ है कि मोंटगोमरी गुणन द्वारा एकल उत्पाद की गणना पारंपरिक या बैरेट कटौती कलन की तुलना में धीमी है। चूंकि, पंक्ति में कई गुणन करते समय, जैसा कि [[मॉड्यूलर घातांक]] में होता है, मध्यवर्ती परिणाम मोंटगोमरी रूप में छोड़े जा सकते हैं। इसके कारण प्रारंभिक और अंतिम रूपांतरण समग्र संगणना का नगण्य अंश बन जाता है। इस प्रकार [[आरएसए (क्रिप्टोसिस्टम)]] और डिफी-हेलमैन की एक्सचेंज जैसे कई महत्वपूर्ण क्रिप्टो सिस्टम अंकगणितीय संचालन मोडुलो बड़ी विषम संख्या पर आधारित हैं, और इन क्रिप्टोसिस्टम्स के लिए, मोंटगोमरी गुणन का उपयोग करके संगणना {{mvar|R}} की घात दो को उपलब्ध विकल्पों से अधिक उपयोगी माना जाता है।<ref>[[Alfred J. Menezes]], Paul C. van Oorschot, and [[Scott A. Vanstone]]. [http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf ''Handbook of Applied Cryptography'']. CRC Press, 1996. {{isbn|0-8493-8523-7}}, chapter 14.</ref>
 == मॉड्यूलर अंकगणित ==
-होने देना {{mvar|N}} धनात्मक पूर्णांक मापांक दर्शाता है। [[भागफल की अंगूठी]] {{math|'''Z'''/''N'''''Z'''}} में अवशेष वर्ग मॉड्यूल सम्मिलित हैं {{mvar|N}}, अर्ताथ इसके तत्व फॉर्म के सेट हैं
+{{mvar|N}} धनात्मक पूर्णांक मापांक दर्शाता है। इस प्रकार [[भागफल की अंगूठी|भागफल की रिंग]] को {{math|'''Z'''/''N'''''Z'''}} में {{mvar|N}} अवशेषों वाले वर्ग मॉड्यूल सम्मिलित रहते हैं, अर्ताथ इसके तत्व फॉर्म के समुच्चय हैं, जो इस प्रकार हैं-
 :<math>\{ a + kN \colon k \in \mathbf{Z} \},</math>
-कहाँ {{mvar|a}} पूर्णांकों के बीच है। प्रत्येक अवशेष वर्ग पूर्णांकों का समूह है जैसे कि सेट में किसी भी दो पूर्णांकों का अंतर विभाज्य है {{mvar|N}} (और अवशेष वर्ग उस संपत्ति के संबंध में अधिकतम है; पूर्णांकों को अवशेष वर्ग से बाहर नहीं छोड़ा जाता है जब तक कि वे विभाज्यता की स्थिति का उल्लंघन नहीं करते)। अवशेष वर्ग के अनुरूप {{mvar|a}} अंकित है {{math|{{overline|''a''}}}}. अवशेष वर्गों की समानता को सर्वांगसमता कहा जाता है और निरूपित किया जाता है
+जहाँ {{mvar|a}} पूर्णांकों के बीच है। प्रत्येक अवशेष वर्ग पूर्णांकों का समूह है जैसे कि समुच्चय में किसी भी दो पूर्णांकों का अंतर विभाज्य {{mvar|N}} है और अवशेष वर्ग उस संपत्ति के संबंध में अधिकतम है; पूर्णांकों को अवशेष वर्ग से बाहर नहीं छोड़ा जाता है जब तक कि वे विभाज्यता की स्थिति का उल्लंघन नहीं करते हैं। इस प्रकार अवशेष वर्ग के अनुरूप {{mvar|a}} तथा {{math|{{overline|''a''}}}} द्वारा अंकित किया जाता है, इस प्रकार अवशेष वर्गों की समानता को सर्वांगसमता कहा जाता है और इसे इस प्रकार निरूपित किया जाता है।
 :<math>\bar a \equiv \bar b \pmod{N}.</math>
-कंप्यूटर पर संपूर्ण अवशेष वर्ग को संग्रहीत करना असंभव है क्योंकि अवशेष वर्ग में असीम रूप से कई तत्व होते हैं। इसके अतिरिक्त, अवशेष वर्गों को प्रतिनिधि के रूप में संग्रहीत किया जाता है। परंपरागत रूप से, ये प्रतिनिधि पूर्णांक होते हैं {{mvar|a}} जिसके लिए {{math|0 &le; ''a'' &le; ''N'' &minus; 1}}. अगर {{mvar|a}} पूर्णांक है, तो इसका प्रतिनिधि है {{math|{{overline|''a''}}}} लिखा है {{math|''a'' mod ''N''}}. सर्वांगसमता लिखते समय, पूर्णांक की पहचान उस अवशेष वर्ग के साथ करना आम है जो यह प्रतिनिधित्व करता है। इस परिपाटी के साथ उपरोक्त समानता लिखी जाती है {{math|''a'' ≡ ''b'' mod ''N''}}.
+कंप्यूटर पर संपूर्ण अवशेष वर्ग को संग्रहीत करना असंभव है क्योंकि अवशेष वर्ग में अधिकांशतः कई तत्व होते हैं। इसके अतिरिक्त अवशेष वर्गों को प्रतिनिधि के रूप में संग्रहीत किया जाता है। परंपरागत रूप से, ये प्रतिनिधि पूर्णांक होते हैं, जहाँ पर {{mvar|a}} जिसके लिए {{math|0 &le; ''a'' &le; ''N'' &minus; 1}} मान उपयोगी हैं जिसके अनुसार यदि {{mvar|a}} पूर्णांक है, तो इसका प्रतिनिधि {{math|{{overline|''a''}}}} है जिसको {{math|''a'' mod ''N''}} लिखा जाता है। इस प्रकार सर्वांगसमता लिखते समय, पूर्णांक की पहचान उस अवशेष वर्ग के साथ करना सरल है जो यह प्रतिनिधित्व करता है। इस परिपाटी के साथ उपरोक्त समानता  {{math|''a'' ≡ ''b'' mod ''N''}} लिखी जाती है।
-अवशेष वर्गों पर अंकगणित पहले उनके प्रतिनिधियों पर पूर्णांक अंकगणित करके किया जाता है। पूर्णांक ऑपरेशन का आउटपुट अवशेष वर्ग को निर्धारित करता है, और मॉड्यूलर ऑपरेशन का आउटपुट अवशेष वर्ग के प्रतिनिधि की गणना करके निर्धारित किया जाता है। उदाहरण के लिए, अगर {{math|1=''N'' = 17}}, फिर अवशेष वर्गों का योग {{math|{{overline|7}}}} और {{math|{{overline|15}}}} की गणना पूर्णांक योग ज्ञात करके की जाती है {{math|1=7 + 15 = 22}}, फिर निर्धारण {{math|22 mod 17}}, 0 और 16 के बीच का पूर्णांक जिसका अंतर 22 के साथ 17 का गुणक है। इस स्थिति में, वह पूर्णांक 5 है, इसलिए {{math|{{overline|7}} + {{overline|15}} ≡ {{overline|5}} mod 17}}.
+अवशेष वर्गों पर अंकगणित पहले उनके प्रतिनिधियों पर पूर्णांक अंकगणित करके किया जाता है। पूर्णांक ऑपरेशन का आउटपुट अवशेष वर्ग को निर्धारित करता है, और मॉड्यूलर ऑपरेशन का आउटपुट अवशेष वर्ग के प्रतिनिधि की गणना करके निर्धारित किया जाता है। उदाहरण के लिए, यदि {{math|1=''N'' = 17}}, फिर अवशेष वर्गों का योग {{math|{{overline|7}}}} और {{math|{{overline|15}}}} की गणना पूर्णांक योग {{math|1=7 + 15 = 22}} द्वारा ज्ञात करके की जाती है, इस कारण पुनः इसका  निर्धारण {{math|22 mod 17}}, 0 और 16 के बीच का पूर्णांक जिसका अंतर 22 के साथ 17 का गुणक है। इस स्थिति में, वह पूर्णांक 5 है, इसलिए {{math|{{overline|7}} + {{overline|15}} ≡ {{overline|5}} mod 17}} मान उपयोग किया जाता हैं।
 == मोंटगोमरी फॉर्म ==
-अगर {{mvar|a}} और {{mvar|b}} श्रेणी में पूर्णांक हैं {{math|[0, ''N'' &minus; 1]}}, तो उनका योग सीमा में है {{math|[0, 2''N'' &minus; 2]}} और उनका अंतर सीमा में है {{math|[&minus;''N'' + 1, ''N'' &minus; 1]}}, इसलिए प्रतिनिधि का निर्धारण करना {{math|[0, ''N'' &minus; 1]}} के लिए अधिकतम घटाव या जोड़ (क्रमशः) आवश्यक है {{mvar|N}}. हालाँकि, उत्पाद {{math|''ab''}} के दायरे में है {{math|[0, ''N''<sup>2</sup> &minus; 2''N'' + 1]}}. मध्यवर्ती पूर्णांक उत्पाद का भंडारण {{math|''ab''}} को या तो दोगुने बिट्स की आवश्यकता होती है {{mvar|a}} या {{mvar|b}}, और कुशलता से प्रतिनिधि का निर्धारण {{math|[0, ''N'' &minus; 1]}} विभाजन की आवश्यकता है। गणितीय रूप से, 0 और के बीच का पूर्णांक {{math|''N'' &minus; 1}} के अनुरूप है {{math|''ab''}} को यूक्लिडियन डिवीजन#प्रमेय के कथन को लागू करके व्यक्त किया जा सकता है:
+यदि {{mvar|a}} और {{mvar|b}} श्रेणी में पूर्णांक {{math|[0, ''N'' &minus; 1]}} हैं, तो उनका योग सीमा {{math|[0, 2''N'' &minus; 2]}} में है और उनका अंतर सीमा में {{math|[&minus;''N'' + 1, ''N'' &minus; 1]}} है, इसलिए प्रतिनिधि का निर्धारण करना {{math|[0, ''N'' &minus; 1]}} के लिए अधिकतम घटाव या जोड़ को क्रमशः {{mvar|N}} के लिए आवश्यक है, चूंकि, उत्पाद {{math|''ab''}} की सीमा {{math|[0, ''N''<sup>2</sup> &minus; 2''N'' + 1]}} में है। मध्यवर्ती पूर्णांक उत्पाद का भंडारण {{math|''ab''}} को या तो दोगुने बिट्स की आवश्यकता होती है इस प्रकार {{mvar|a}} या {{mvar|b}}, और कुशलता से प्रतिनिधि का निर्धारण {{math|[0, ''N'' &minus; 1]}} विभाजन की आवश्यकता है। गणितीय रूप से, 0 और के बीच का पूर्णांक {{math|''N'' &minus; 1}} के अनुरूप है {{math|''ab''}} को यूक्लिडियन डिवीजन प्रमेय के कथन को लागू करके व्यक्त किया जा सकता है:
 :<math>ab = qN + r,</math>
-कहाँ {{mvar|q}} भागफल है <math>\lfloor ab / N \rfloor</math> और {{mvar|r}}, शेष, अंतराल में है {{math|[0, ''N'' &minus; 1]}}. शेष {{mvar|r}} है {{math|''ab'' mod ''N''}}. निर्धारण {{mvar|r}} कंप्यूटिंग द्वारा किया जा सकता है {{mvar|q}}, फिर घटाना {{math|''qN''}} से {{math|''ab''}}. उदाहरण के लिए, फिर से <math>N=17</math>, उत्पाद {{math|{{overline|7}} ⋅ {{overline|15}}}} कंप्यूटिंग द्वारा निर्धारित किया जाता है <math>7 \cdot 15 = 105</math>, विभाजित करना <math>\lfloor 105 / 17 \rfloor = 6</math>, और घटाना <math>105 - 6 \cdot 17 = 105 - 102 = 3</math>.
+जहाँ {{mvar|q}} भागफल है <math>\lfloor ab / N \rfloor</math> और {{mvar|r}}, शेष, अंतराल में है {{math|[0, ''N'' &minus; 1]}}. शेष {{mvar|r}} है, इस कारण {{math|''ab'' mod ''N''}} के निर्धारण {{mvar|r}} कंप्यूटिंग {{mvar|q}} द्वारा किया जा सकता है, फिर घटाना {{math|''qN''}} से {{math|''ab''}}. उदाहरण के लिए, फिर से <math>N=17</math>, उत्पाद {{math|{{overline|7}} ⋅ {{overline|15}}}} कंप्यूटिंग द्वारा <math>7 \cdot 15 = 105</math> पर इसका निर्धारण किया जाता है, इसे विभाजित करना <math>\lfloor 105 / 17 \rfloor = 6</math>, और घटाना <math>105 - 6 \cdot 17 = 105 - 102 = 3</math> सरल हो जाता हैं।
-क्योंकि की गणना {{mvar|q}} विभाजन की आवश्यकता है, यह अधिकांश कंप्यूटर हार्डवेयर पर अवांछनीय रूप से महंगा है। मोंटगोमरी फॉर्म रिंग के तत्वों को व्यक्त करने का अलग तरीका है जिसमें मॉड्यूलर उत्पादों की गणना महंगे डिवीजनों के बिना की जा सकती है। जबकि विभाजन अभी भी जरूरी हैं, उन्हें अलग भाजक के संबंध में किया जा सकता है {{mvar|R}}. इस विभाजक को दो की शक्ति के रूप में चुना जा सकता है, जिसके लिए विभाजन को शिफ्टिंग, या मशीनी शब्दों की पूरी संख्या से परिवर्तित किया जा सकता है, जिसके लिए शब्दों को छोड़ कर विभाजन को परिवर्तित किया जा सकता है। ये विभाजन तेज़ हैं, इसलिए मोंटगोमरी फॉर्म का उपयोग करके मॉड्यूलर उत्पादों की गणना करने की अधिकांश लागत साधारण उत्पादों की गणना करने की लागत है।
+क्योंकि की गणना {{mvar|q}} विभाजन की आवश्यकता है, यह अधिकांश कंप्यूटर हार्डवेयर पर अवांछनीय रूप से महंगा है। मोंटगोमरी फॉर्म रिंग के तत्वों को व्यक्त करने का अलग तरीका है जिसमें मॉड्यूलर उत्पादों की गणना महंगे डिवीजनों के बिना की जा सकती है। जबकि विभाजन अभी भी आवश्यक हैं, उन्हें अलग भाजक {{mvar|R}} के संबंध में किया जा सकता है। इस विभाजक को दो की शक्ति के रूप में चुना जा सकता है, जिसके लिए विभाजन को शिफ्टिंग, या मशीनी शब्दों की पूरी संख्या से परिवर्तित किया जा सकता है, जिसके लिए शब्दों को छोड़ कर विभाजन को परिवर्तित किया जा सकता है। ये विभाजन तेज़ हैं, इसलिए मोंटगोमरी फॉर्म का उपयोग करके मॉड्यूलर उत्पादों की गणना करने की अधिकांश लागत साधारण उत्पादों की गणना करने की लागत है।
-सहायक मापांक {{mvar|R}} धनात्मक पूर्णांक होना चाहिए जैसे कि {{math|1=gcd(''R'', ''N'') = 1}}. कम्प्यूटेशनल उद्देश्यों के लिए यह भी आवश्यक है कि विभाजन और कमी मोडुलो {{mvar|R}} सस्ती हैं, और मॉड्यूलस मॉड्यूलर गुणन के लिए तब तक उपयोगी नहीं है जब तक {{math|''R'' &gt; ''N''}}. अवशेष वर्ग का मोंटगोमरी रूप {{math|{{overline|''a''}}}} इसके संबंध में {{mvar|R}} है {{math|''aR'' mod ''N''}}, अर्थात यह अवशेष वर्ग का प्रतिनिधि है {{math|{{overline|''aR''}}}}. उदाहरण के लिए, मान लीजिए {{math|1=''N'' = 17}} ओर वो {{math|1=''R'' = 100}}. 3, 5, 7 और 15 के मोंटगोमरी रूप हैं {{math|1=300 mod 17 = 11}}, {{math|1=500 mod 17 = 7}}, {{math|1=700 mod 17 = 3}}, और {{math|1=1500 mod 17 = 4}}.
+सहायक मापांक {{mvar|R}} धनात्मक पूर्णांक होना चाहिए जैसे कि {{math|1=gcd(''R'', ''N'') = 1}} इसका उदाहरण हैं। इस प्रकार कम्प्यूटरीकृत उद्देश्यों के लिए यह भी आवश्यक है कि विभाजन और कमी के लिए मोडुलो {{mvar|R}} सरल हैं, और मॉड्यूलस मॉड्यूलर गुणन के लिए तब तक उपयोगी नहीं है जब तक {{math|''R'' &gt; ''N''}} अवशेष वर्ग का मोंटगोमरी रूप {{math|{{overline|''a''}}}}  हैं। इसके संबंध में {{mvar|R}} है {{math|''aR'' mod ''N''}}, अर्थात यह अवशेष वर्ग  {{math|{{overline|''aR''}}}} का प्रतिनिधि है, उदाहरण के लिए, मान लीजिए {{math|1=''N'' = 17}} ओर वो {{math|1=''R'' = 100}}. 3, 5, 7 और 15 के मोंटगोमरी {{math|1=300 mod 17 = 11}}, {{math|1=500 mod 17 = 7}}, {{math|1=700 mod 17 = 3}}, और {{math|1=1500 mod 17 = 4}} का रूप हैं।
-मोंटगोमरी रूप में जोड़ और घटाव वितरण कानून के कारण सामान्य मॉड्यूलर जोड़ और घटाव के समान हैं:
+मोंटगोमरी रूप में जोड़ और घटाव वितरण नियम के कारण सामान्य मॉड्यूलर जोड़ और घटाव के समान हैं:
 :<math>aR + bR = (a + b)R,</math>
 :<math>aR - bR = (a - b)R.</math>
-यह इस तथ्य का परिणाम है कि, क्योंकि {{math|1=gcd(''R'', ''N'') = 1}}, गुणा करके {{mvar|R}} योज्य समूह पर समरूपता है {{math|'''Z'''/''N'''''Z'''}}. उदाहरण के लिए, {{math|1=(7 + 15) mod 17 = 5}}, जो मोंटगोमरी रूप में बन जाता है {{math|1=(3 + 4) mod 17 = 7}}.
+यह इस तथ्य का परिणाम है कि, क्योंकि {{math|1=gcd(''R'', ''N'') = 1}}, गुणा करके {{mvar|R}} योज्य समूह पर समरूपता {{math|'''Z'''/''N'''''Z'''}} है, उदाहरण के लिए, {{math|1=(7 + 15) mod 17 = 5}}, जो मोंटगोमरी रूप {{math|1=(3 + 4) mod 17 = 7}} में बन जाता है।
-मॉन्टगोमरी रूप में गुणन, हालांकि, अधिक जटिल प्रतीत होता है। का सामान्य उत्पाद {{math|''aR''}} और {{math|''bR''}} के उत्पाद का प्रतिनिधित्व नहीं करता है {{mvar|a}} और {{mvar|b}} क्योंकि इसका अतिरिक्त कारक है {{mvar|R}}:
+मॉन्टगोमरी रूप में गुणन, चूंकि, अधिक जटिल प्रतीत होता है। का सामान्य उत्पाद {{math|''aR''}} और {{math|''bR''}} के उत्पाद का प्रतिनिधित्व नहीं करता है, इस प्रकार {{mvar|a}} और {{mvar|b}} क्योंकि इसका अतिरिक्त कारक {{mvar|R}} है :
 :<math>(aR \bmod N)(bR \bmod N) \bmod N = (abR)R \bmod N.</math>
-मोंटगोमरी रूप में कंप्यूटिंग उत्पादों के अतिरिक्त कारक को हटाने की आवश्यकता है {{mvar|R}}. जबकि विभाजन द्वारा {{mvar|R}} सस्ता है, मध्यवर्ती उत्पाद है {{math|(''aR'' mod ''N'')(''bR'' mod ''N'')}} से विभाज्य नहीं है {{mvar|R}} क्योंकि मॉडुलो ऑपरेशन ने उस संपत्ति को नष्ट कर दिया है। उदाहरण के लिए, 7 और 15 मॉड्यूल 17 के मोंटगोमरी रूपों का उत्पाद 3 और 4 का उत्पाद है, जो कि 12 है। चूंकि 12 100 से विभाज्य नहीं है, इसलिए अतिरिक्त कारक को हटाने के लिए अतिरिक्त प्रयास की आवश्यकता है {{mvar|R}}.
+मोंटगोमरी रूप में कंप्यूटिंग उत्पादों के अतिरिक्त कारक को {{mvar|R}} द्वारा हटाने की आवश्यकता होती है, जबकि विभाजन द्वारा {{mvar|R}} सस्ता है, मध्यवर्ती उत्पाद है, इस कारण {{math|(''aR'' mod ''N'')(''bR'' mod ''N'')}} से विभाज्य नहीं है {{mvar|R}} क्योंकि मॉडुलो ऑपरेशन ने उस संपत्ति को नष्ट कर दिया है। उदाहरण के लिए, 7 और 15 मॉड्यूल 17 के मोंटगोमरी रूपों का उत्पाद 3 और 4 का उत्पाद है, जो कि 12 है। चूंकि 12 100 से विभाज्य नहीं है, इसलिए अतिरिक्त कारक को हटाने के लिए {{mvar|R}} के अतिरिक्त प्रयास की आवश्यकता है।
-के अतिरिक्त कारक को हटाना {{mvar|R}} को पूर्णांक से गुणा करके किया जा सकता है {{math|''R''&prime;}} ऐसा है कि {{math|''RR''&prime; &equiv; 1 (mod ''N'')}}, अर्ताथ द्वारा {{math|''R''&prime;}} जिसका अवशेष वर्ग मॉड्यूलर व्युत्क्रम है {{mvar|R}} ख़िलाफ़ {{mvar|N}}. फिर, कार्य कर रहे मॉड्यूलो {{mvar|N}},
+जिसके अतिरिक्त कारक को हटाना {{mvar|R}} को पूर्णांक से गुणा करके {{math|''R''&prime;}} को प्राप्त किया जा सकता है, ऐसा है कि {{math|''RR''&prime; &equiv; 1 (mod ''N'')}}, अर्ताथ द्वारा {{math|''R''&prime;}} जिसका अवशेष वर्ग मॉड्यूलर व्युत्क्रम {{mvar|R}} है, इसके विरुद्ध {{mvar|N}}  पुनः, कार्य कर रहे मॉड्यूल {{mvar|N}}, को इस प्रकार प्राप्त करते हैं।
 :<math>(aR \bmod N)(bR \bmod N)R' \equiv (aR)(bR)R^{-1} \equiv (ab)R \pmod{N}.</math>
-पूर्णांक {{math|''R''&prime;}} इस धारणा के कारण सम्मिलित है कि {{mvar|R}} और {{mvar|N}} कोप्राइम हैं। इसका निर्माण विस्तारित यूक्लिडियन एल्गोरिथम का उपयोग करके किया जा सकता है। [[विस्तारित यूक्लिडियन एल्गोरिथ्म]] कुशलतापूर्वक पूर्णांकों को निर्धारित करता है {{math|''R''&prime;}} और {{math|''N''&prime;}} जो बेज़ाउट की पहचान को संतुष्ट करते हैं:
+पूर्णांक {{math|''R''&prime;}} इस धारणा के कारण सम्मिलित है कि {{mvar|R}} और {{mvar|N}} को-प्राइम हैं। इसका निर्माण विस्तारित यूक्लिडियन कलन का उपयोग करके किया जा सकता है। [[विस्तारित यूक्लिडियन एल्गोरिथ्म]] कुशलतापूर्वक पूर्णांकों को निर्धारित करता है, इस प्रकार {{math|''R''&prime;}} और {{math|''N''&prime;}} जो बेज़ाउट की पहचान को संतुष्ट करते हैं:
 {{math|0 &lt; ''R''&prime; &lt; ''N''}}, {{math|0 &lt; ''N''&prime; &lt; ''R''}}, और:
 :<math>RR' - NN' = 1.</math>
-इससे पता चलता है कि मोंटगोमरी रूप में गुणा करना संभव है। मोंटगोमरी रूप में संख्याओं को गुणा करने के लिए सीधा एल्गोरिथम इसलिए गुणा करना है {{math|''aR'' mod ''N''}}, {{math|''bR'' mod ''N''}}, और {{math|''R''&prime;}} पूर्णांक के रूप में और मॉड्यूलो को कम करें {{mvar|N}}.
+इससे पता चलता है कि मोंटगोमरी रूप में गुणा करना संभव है। मोंटगोमरी रूप में संख्याओं को गुणा करने के लिए सीधा कलन इसलिए गुणा करना है, इस प्रकार {{math|''aR'' mod ''N''}}, {{math|''bR'' mod ''N''}}, और {{math|''R''&prime;}} पूर्णांक के रूप में और मॉड्यूल {{mvar|N}} को कम करते हैं।
-उदाहरण के लिए, 7 और 15 मॉड्यूल 17 को मोंटगोमरी फॉर्म में फिर से गुणा करने के लिए {{math|1=''R'' = 100}}, उपरोक्तानुसार 12 प्राप्त करने के लिए 3 और 4 के गुणनफल की गणना करें। विस्तारित यूक्लिडियन एल्गोरिथ्म का तात्पर्य है {{math|1=8⋅100 &minus; 47⋅17 = 1}}, इसलिए {{math|1=''R''&prime; = 8}}. 96 प्राप्त करने के लिए 12 को 8 से गुणा करें और 11 प्राप्त करने के लिए मॉडुलो 17 को कम करें। यह अपेक्षा के अनुरूप 3 का मोंटगोमरी रूप है।
+उदाहरण के लिए, 7 और 15 मॉड्यूल 17 को मोंटगोमरी फॉर्म में फिर से गुणा करने के लिए {{math|1=''R'' = 100}}, उपरोक्तानुसार 12 प्राप्त करने के लिए 3 और 4 के गुणनफल की गणना करते हैं। इस प्रकार विस्तारित यूक्लिडियन एल्गोरिथ्म का तात्पर्य है {{math|1=8⋅100 &minus; 47⋅17 = 1}}, इसलिए {{math|1=''R''&prime; = 8}}. 96 प्राप्त करने के लिए 12 को 8 से गुणा करें और 11 प्राप्त करने के लिए मॉडुलो 17 को कम करें। यह अपेक्षा के अनुरूप 3 का मोंटगोमरी रूप है।
-== आरईडीसी एल्गोरिदम ==
+== आरईडीसी कलन ==
-जबकि उपरोक्त एल्गोरिदम सही है, यह गुणा करने की आवश्यकता के कारण मानक प्रतिनिधित्व में गुणा से धीमा है {{math|''R''&prime;}} और विभाजित करें {{mvar|N}}. मोंटगोमरी रिडक्शन, जिसे आरईडीसी के रूप में भी जाना जाता है, एल्गोरिथ्म है जो साथ उत्पाद की गणना करता है {{math|''R''&prime;}} और मॉड्यूलो को कम करता है {{mvar|N}} भोली विधि की तुलना में अधिक तेज़ी से। पारंपरिक मॉड्यूलर कमी के विपरीत, जो संख्या को इससे छोटा बनाने पर केंद्रित है {{mvar|N}}, मोंटगोमरी कटौती संख्या को और अधिक विभाज्य बनाने पर केंद्रित है {{mvar|R}}. यह छोटे गुणक को जोड़कर ऐसा करता है {{mvar|N}} जिसे अवशेष मोडुलो को रद्द करने के लिए चुना जाता है {{mvar|R}}. से परिणाम विभाजित करना {{mvar|R}} बहुत कम संख्या देता है। यह संख्या इतनी कम है कि यह लगभग रिडक्शन मॉडुलो है {{mvar|N}}, और कमी मोडुलो की गणना {{mvar|N}} केवल अंतिम सशर्त घटाव की आवश्यकता है। क्योंकि सभी संगणनाओं के संबंध में केवल कमी और विभाजन का उपयोग करके किया जाता है {{mvar|R}}, नहीं {{mvar|N}}, एल्गोरिद्म विभाजन द्वारा सीधी मॉड्यूलर कमी की तुलना में तेज़ी से चलता है।
+जबकि उपरोक्त कलन सही है, यह गुणा करने की आवश्यकता के कारण मानक प्रतिनिधित्व में गुणा {{math|''R''&prime;}} से कम है, और {{mvar|N}} से विभाजित करते हैं। मोंटगोमरी रिडक्शन, जिसे आरईडीसी के रूप में भी जाना जाता है, एल्गोरिथ्म है जो साथ उत्पाद की गणना {{math|''R''&prime;}} करता है और मॉड्यूलो को कम करता है, {{mvar|N}} विधि की तुलना में अधिक तेज़ी से किया जाता हैं। पारंपरिक मॉड्यूलर कमी के विपरीत, जो संख्या को इससे छोटा बनाने पर {{mvar|N}} का मान केंद्रित रहता है, मोंटगोमरी के मान में कटौती के कारण यह संख्या को और अधिक विभाज्य बनाने पर {{mvar|R}} केंद्रित रहता है, यह छोटे गुणक को {{mvar|N}} द्वारा जोड़कर ऐसा करता है, जिसे अवशेष मोडुलो को निरस्त करने के लिए {{mvar|R}} को चुना जाता है, जिससे परिणाम विभाजित करना {{mvar|R}} बहुत कम संख्या देता है। यह संख्या इतनी कम है कि यह लगभग रिडक्शन मॉडुलो {{mvar|N}} है, और कमी मोडुलो की गणना {{mvar|N}} केवल अंतिम सशर्त घटाव की आवश्यकता है। क्योंकि सभी संगणनाओं के संबंध में केवल कमी और विभाजन का उपयोग करके किया जाता है {{mvar|R}}, नहीं {{mvar|N}}, एल्गोरिद्म विभाजन द्वारा सीधी मॉड्यूलर कमी की तुलना में तेज़ी से चलता है।
-  समारोह आरईडीसी है
+  '''function''' REDC '''is'''
-  इनपुट: पूर्णांक ''आर'' और ''एन'' के साथ {{nowrap|1=gcd(''R'', ''N'') = 1}},
+     '''input:''' Integers ''R'' and ''N'' with gcd(''R'', ''N'') = 1,
-    पूर्णांक एन' में {{nowrap|[0, ''R'' &minus; 1]}} ऐसा है कि {{nowrap|''NN''&prime; ≡ &minus;1 mod ''R''}},
+            Integer ''N''′ in [0, ''R'' − 1] such that ''NN''′ ≡ −1 mod ''R'',
-    सीमा में पूर्णांक टी {{nowrap|[0, ''RN'' &minus; 1]}}.
+            Integer ''T'' in the range [0, ''RN'' − 1].
-  आउटपुट: श्रेणी में पूर्णांक ''एस'' {{nowrap|[0, ''N'' &minus; 1]}} ऐसा है कि {{nowrap|''S'' ≡ ''TR''<sup>&minus;1</sup> mod ''N''}}
+     '''output:''' Integer ''S'' in the range [0, ''N'' − 1] such that ''S'' ≡ ''TR''<sup>−1</sup> mod ''N''
-  एम ← ((टी मॉड आर) एन ') मॉड आर
+     ''m'' ← ((''T'' mod ''R'')''N''′) mod ''R''
-  टी ← (टी + एमएन) / आर
+     ''t'' ← (''T'' + ''mN'') / ''R''
-  'अगर' टी ≥ एन 'फिर'
+     '''if''' ''t'' ≥ ''N'' '''then'''
-   'वापस करना' {{nowrap|''t'' &minus; ''N''}}
+         '''return''' ''t'' − ''N''
-  अन्य
+     '''else'''
-   वापसी ''टी''
+         '''return''' ''t''
-  अगर अंत
+     '''end if'''
- अंत समारोह
-यह देखने के लिए कि यह एल्गोरिदम सही है, पहले उसका निरीक्षण करें {{mvar|m}} ठीक से चुना जाता है जिससे कि {{math|''T'' + ''mN''}} से विभाज्य है {{mvar|R}}. संख्या से विभाज्य है {{mvar|R}} अगर और केवल अगर यह शून्य मॉड के अनुरूप है {{mvar|R}}, और हमारे पास है:
+ '''end function'''
+यह देखने के लिए कि यह कलन सही है, पहले उसका निरीक्षण करें {{mvar|m}} ठीक से चुना जाता है जिससे कि {{math|''T'' + ''mN''}}  मुख्य रूप से {{mvar|R}} से विभाज्य है, इस प्रकार {{mvar|R}} संख्या से विभाज्य है, यदि यह शून्य मॉड {{mvar|R}} के अनुरूप है, इस प्रकार हमें उक्त समीकरण प्राप्त होता हैं:
 :<math>T + mN \equiv T + (((T \bmod R)N') \bmod R)N \equiv T + T N' N \equiv T - T \equiv 0 \pmod{R}.</math>
-इसलिए, {{mvar|t}} पूर्णांक है। दूसरा, आउटपुट या तो है {{mvar|t}} या {{math|''t'' &minus; ''N''}}, दोनों के सर्वांगसम हैं {{math|''t'' mod ''N''}}, तो यह साबित करने के लिए कि आउटपुट सर्वांगसम है {{math|''TR''<sup>&minus;1</sup> mod ''N''}}, यह साबित करने के लिए पर्याप्त है {{mvar|t}} है। सापेक्ष {{mvar|N}}, {{mvar|t}} संतुष्ट करता है:
+इसलिए {{mvar|t}} पूर्णांक है। इसका दूसरा मान आउटपुट या तो {{mvar|t}} या {{math|''t'' &minus; ''N''}}  है, दोनों के सर्वांगसम {{math|''t'' mod ''N''}}  हैं , तो यह प्रमाणित करने के लिए कि आउटपुट सर्वांगसम {{math|''TR''<sup>&minus;1</sup> mod ''N''}} है , यह प्रमाणित करने के लिए पर्याप्त है {{mvar|t}} है। सापेक्ष {{mvar|N}}, {{mvar|t}} संतुष्ट करता है:
 :<math>t \equiv (T + mN)R^{-1} \equiv TR^{-1} + (mR^{-1})N \equiv TR^{-1} \pmod{N}.</math>
-इसलिए, आउटपुट में सही अवशेष वर्ग है। तीसरा, {{mvar|m}} में है {{math|[0, ''R'' &minus; 1]}}, और इसलिए {{math|''T'' + ''mN''}} 0 और के बीच है {{math|(''RN'' &minus; 1) + (''R'' &minus; 1)''N'' &lt; 2''RN''}}. इस तरह {{mvar|t}} मै रुक जाना {{math|2''N''}}, और क्योंकि यह पूर्णांक है, यह डालता है {{mvar|t}} सीमा में {{math|[0, 2''N'' &minus; 1]}}. इसलिए कम कर रहा है {{mvar|t}} वांछित सीमा में अधिकतम घटाव की आवश्यकता होती है, इसलिए एल्गोरिथम का आउटपुट सही सीमा में होता है।
+इसलिए, आउटपुट में सही अवशेष वर्ग है। {{math|[0, ''R'' &minus; 1]}} का तीसरा मान {{mvar|m}} में है , और इसलिए {{math|''T'' + ''mN''}} 0 और के बीच {{math|(''RN'' &minus; 1) + (''R'' &minus; 1)''N'' &lt; 2''RN''}} है, इस प्रकार {{mvar|t}} मै रुक जाना {{math|2''N''}}, और क्योंकि यह पूर्णांक है, यह डालता है, इस प्रकार {{mvar|t}} सीमा में {{math|[0, 2''N'' &minus; 1]}} को इसलिए कम कर रहा है, इस प्रकार {{mvar|t}} वांछित सीमा में अधिकतम घटाव की आवश्यकता होती है, इसलिए कलन का आउटपुट सही सीमा में होता है।
-और 15 मॉड्यूल 17 के उत्पाद की गणना करने के लिए आरईडीसी का उपयोग करने के लिए, पहले मोंटगोमेरी फॉर्म में कनवर्ट करें और उपरोक्त के रूप में 12 प्राप्त करने के लिए पूर्णांक के रूप में गुणा करें। इसके बाद आरईडीसी अप्लाई करें {{math|1=''R'' = 100}}, {{math|1=''N'' = 17}}, {{math|1=''N''&prime; = 47}}, और {{math|1=''T'' = 12}}. पहला कदम तय है {{mvar|m}} को {{math|1=12 ⋅ 47 mod 100 = 64}}. दूसरा चरण तय है {{mvar|t}} को {{math|(12 + 64 ⋅ 17) / 100}}. नोटिस जो {{math|12 + 64 ⋅ 17}} 1100 है, उम्मीद के मुताबिक 100 का गुणक। {{mvar|t}} 11 पर सेट है, जो 17 से कम है, इसलिए अंतिम परिणाम 11 है, जो पिछले अनुभाग की गणना से सहमत है।
+और 15 मॉड्यूल 17 के उत्पाद की गणना करने के लिए आरईडीसी का उपयोग करने के लिए, पहले मोंटगोमेरी फॉर्म में कनवर्ट करें और उपरोक्त के रूप में 12 प्राप्त करने के लिए पूर्णांक के रूप में गुणा करें। इसके पश्चात आरईडीसी अप्लाई करें {{math|1=''R'' = 100}}, {{math|1=''N'' = 17}}, {{math|1=''N''&prime; = 47}}, और {{math|1=''T'' = 12}} हैं। इसके पहले चरण {{mvar|m}} को {{math|1=12 ⋅ 47 mod 100 = 64}} पर तय किया जाता है, इसका दूसरा चरण {{mvar|t}} को तय करते हैं,  इस प्रकार {{math|(12 + 64 ⋅ 17) / 100}} जिसके लिए {{math|12 + 64 ⋅ 17}} का मान 1100 है, इसके अनुसार 100 का गुणक {{mvar|t}} 11 पर समुच्चय है, जो 17 से कम है, इसलिए अंतिम परिणाम 11 है, जो पिछले अनुभाग की गणना से सहमत है।
-एक अन्य उदाहरण के रूप में, उत्पाद पर विचार करें {{math|7 ⋅ 15 mod 17}} अपितु इसके साथ {{math|1=''R'' = 10}}. विस्तारित यूक्लिडियन एल्गोरिथम का उपयोग करके गणना करें {{math|1=&minus;5 ⋅ 10 + 3 ⋅ 17 = 1}}, इसलिए {{math|''N''&prime;}} होगा {{math|1=&minus;3 mod 10 = 7}}. 7 और 15 के मोंटगोमरी रूप हैं {{math|1=70 mod 17 = 2}} और {{math|1=150 mod 17 = 14}}, क्रमश। उनका उत्पाद 28 इनपुट है {{mvar|T}} आरईडीसी के लिए, और उसके बाद से {{math|1=28 &lt; ''RN'' = 170}}, आरईडीसी की धारणाएं संतुष्ट हैं। आरईडीसी चलाने के लिए, सेट करें {{mvar|m}} को {{math|1=(28 mod 10) ⋅ 7 mod 10 = 196 mod 10 {{=}} 6}}. तब {{math|1=28 + 6 ⋅ 17 = 130}}, इसलिए {{math|1=''t'' = 13}}. क्योंकि {{math|1=30 mod 17 = 13}}, यह मोंटगोमरी का रूप है {{math|1=3 = 7 ⋅ 15 mod 17}}.
+एक अन्य उदाहरण के रूप में, उत्पाद पर विचार करें {{math|7 ⋅ 15 mod 17}} अपितु इसके साथ {{math|1=''R'' = 10}}. विस्तारित यूक्लिडियन कलन का उपयोग करके {{math|1=&minus;5 ⋅ 10 + 3 ⋅ 17 = 1}} की गणना करें, इसलिए {{math|''N''&prime;}} होगा {{math|1=&minus;3 mod 10 = 7}}. 7 और 15 के मोंटगोमरी रूप {{math|1=70 mod 17 = 2}} और {{math|1=150 mod 17 = 14}} हैं। {{mvar|T}} आरईडीसी के लिए उनका उत्पाद 28 इनपुट है, और उसके पश्चात {{math|1=28 &lt; ''RN'' = 170}}, आरईडीसी की धारणाएं संतुष्ट हैं। इस प्रकार आरईडीसी चलाने के लिए, समुच्चय करें {{mvar|m}} को {{math|1=(28 mod 10) ⋅ 7 mod 10 = 196 mod 10 {{=}} 6}} तथा इसके पश्चात {{math|1=28 + 6 ⋅ 17 = 130}} पर हल करते हैं, इसलिए {{math|1=''t'' = 13}} मान उपयोग करते हैं क्योंकि {{math|1=30 mod 17 = 13}}, यह मोंटगोमरी {{math|1=3 = 7 ⋅ 15 mod 17}} का रूप है।
 == मोंटगोमरी रूप में अंकगणित ==
-ब्याज मॉड्यूलो के कई संचालन {{mvar|N}} मोंटगोमरी रूप में समान रूप से अच्छी तरह से व्यक्त किया जा सकता है। जोड़, घटाव, निषेध, समानता के लिए तुलना, पूर्णांक द्वारा गुणा जो मोंटगोमरी रूप में नहीं है, और सबसे बड़ा सामान्य विभाजक है {{mvar|N}} सभी मानक एल्गोरिदम के साथ किया जा सकता है। [[जैकोबी प्रतीक]] की गणना इस प्रकार की जा सकती है <math>\big(\tfrac{a}{N}\big) = \big(\tfrac{aR}{N}\big) / \big(\tfrac{R}{N}\big)</math> जब तक कि <math>\big(\tfrac{R}{N}\big)</math> रखा है।
+इन मॉड्यूल की कई संचालन {{mvar|N}} मोंटगोमरी रूप में समान रूप से अच्छी तरह से व्यक्त किया जा सकता है। इस प्रकार जोड़, घटाव, निषेध, समानता के लिए तुलना, पूर्णांक द्वारा गुणा जो मोंटगोमरी रूप में नहीं है, और सबसे बड़ा सामान्य विभाजक है {{mvar|N}} सभी मानक कलन के साथ किया जा सकता है। [[जैकोबी प्रतीक]] की गणना इस प्रकार की जा सकती है <math>\big(\tfrac{a}{N}\big) = \big(\tfrac{aR}{N}\big) / \big(\tfrac{R}{N}\big)</math> जब तक कि <math>\big(\tfrac{R}{N}\big)</math> रखा है।
-कब {{math|''R'' &gt; ''N''}}, अधिकांश अन्य अंकगणितीय संक्रियाएँ REDC के संदर्भ में व्यक्त की जा सकती हैं। इस धारणा का तात्पर्य है कि दो प्रतिनिधियों के उत्पाद मॉड {{mvar|N}} मै रुक जाना {{mvar|RN}}, सही आउटपुट उत्पन्न करने के लिए REDC के लिए आवश्यक सटीक परिकल्पना। विशेष रूप से, का उत्पाद {{math|''aR'' mod ''N''}} और {{math|''bR'' mod ''N''}} है {{math|REDC((''aR'' mod ''N'')(''bR'' mod ''N''))}}. गुणा और आरईडीसी के संयुक्त संचालन को अधिकांशतः मोंटगोमरी गुणन कहा जाता है।
+जब {{math|''R'' &gt; ''N''}}, अधिकांश अन्य अंकगणितीय संक्रियाएँ REDC के संदर्भ में व्यक्त की जा सकती हैं। इस धारणा का तात्पर्य है कि दो प्रतिनिधियों के उत्पाद मॉड {{mvar|N}} मै रुक जाना {{mvar|RN}}, सही आउटपुट उत्पन्न करने के लिए REDC के लिए आवश्यक सटीक परिकल्पना की जाती हैं। विशेष रूप से, का उत्पाद {{math|''aR'' mod ''N''}} और {{math|''bR'' mod ''N''}} है, जिसके लिए {{math|REDC((''aR'' mod ''N'')(''bR'' mod ''N''))}} गुणा और आरईडीसी के संयुक्त संचालन को अधिकांशतः मोंटगोमरी गुणन कहा जाता है।
-मोंटगोमरी रूप में रूपांतरण कंप्यूटिंग द्वारा किया जाता है {{math|REDC((''a'' mod ''N'')(''R''<sup>2</sup> mod ''N''))}}. कंप्यूटिंग द्वारा मोंटगोमरी फॉर्म से रूपांतरण किया जाता है {{math|REDC(''aR'' mod ''N'')}}. का मॉड्यूलर व्युत्क्रम {{math|''aR'' mod ''N''}} है {{math|REDC((''aR'' mod ''N'')<sup>&minus;1</sup>(''R''<sup>3</sup> mod ''N''))}}. प्रारंभिक गुणनफल को 1 के मोंटगोमरी निरूपण के लिए प्रारंभ करके, वर्ग करके घातांक का उपयोग करके मॉड्यूलर घातांक किया जा सकता है, अर्थात {{math|''R'' mod ''N''}}, और मोंटगोमरी गुणा द्वारा गुणा और वर्ग चरणों को प्रतिस्थापित करके।
+मोंटगोमरी रूप में रूपांतरण {{math|REDC((''a'' mod ''N'')(''R''<sup>2</sup> mod ''N''))}} कंप्यूटिंग द्वारा किया जाता है, इस प्रकार कंप्यूटिंग द्वारा मोंटगोमरी फॉर्म {{math|REDC(''aR'' mod ''N'')}} से रूपांतरण किया जाता है, जिसका मॉड्यूलर व्युत्क्रम {{math|''aR'' mod ''N''}} है {{math|REDC((''aR'' mod ''N'')<sup>&minus;1</sup>(''R''<sup>3</sup> mod ''N''))}} प्रारंभिक गुणनफल को 1 के मोंटगोमरी निरूपण के लिए प्रारंभ करके, वर्ग करके घातांक का उपयोग करके मॉड्यूलर घातांक किया जा सकता है, अर्थात {{math|''R'' mod ''N''}}, और मोंटगोमरी गुणा द्वारा गुणा और वर्ग चरणों को प्रतिस्थापित करके प्राप्त होता हैं।
-इन परिचालनों को करने के लिए कम से कम जानना आवश्यक है {{math|''N''&prime;}} और {{math|''R''<sup>2</sup> mod ''N''}}. कब {{mvar|R}} छोटे सकारात्मक पूर्णांक की शक्ति है {{mvar|b}}, {{math|''N''&prime;}} की गणना हेंसल लेम्मा द्वारा की जा सकती है: का व्युत्क्रम {{mvar|N}} मापांक {{mvar|b}} की गणना भोले एल्गोरिथम द्वारा की जाती है (उदाहरण के लिए, if {{math|1=''b'' = 2}} तो व्युत्क्रम 1 है), और हेंसल की लेम्मा का उपयोग बार-बार व्युत्क्रम मॉड्यूल उच्च और उच्च शक्तियों को खोजने के लिए किया जाता है {{mvar|b}}, जब उलटा मोडुलो रुक जाता है {{mvar|R}} ज्ञात है; {{math|''N''&prime;}} इस व्युत्क्रम का निषेध है। स्थिरांक {{math|''R'' mod ''N''}} और {{math|''R''<sup>3</sup> mod ''N''}} के रूप में उत्पन्न किया जा सकता है {{math|REDC(''R''<sup>2</sup> mod ''N'')}} और के रूप में {{math|REDC((''R''<sup>2</sup> mod ''N'')(''R''<sup>2</sup> mod ''N''))}}. मौलिक ऑपरेशन किसी उत्पाद के आरईडीसी की गणना करना है। जब स्टैंडअलोन आरईडीसी की आवश्यकता होती है, तो इसकी गणना किसी उत्पाद के आरईडीसी के रूप में की जा सकती है {{math|1 mod ''N''}}. एकमात्र स्थान जहां प्रत्यक्ष कमी मोडुलो है {{mvar|N}} आवश्यक है के पूर्वगणना में है {{math|''R''<sup>2</sup> mod ''N''}}.
+इन परिचालनों को करने के लिए कम से कम जानना आवश्यक है {{math|''N''&prime;}} और {{math|''R''<sup>2</sup> mod ''N''}} जब {{mvar|R}} छोटे धनात्मक पूर्णांक की शक्ति है {{mvar|b}}, {{math|''N''&prime;}} की गणना हेंसल लेम्मा द्वारा की जा सकती है: का व्युत्क्रम {{mvar|N}} मापांक {{mvar|b}} की गणना भोले कलन द्वारा की जाती है (उदाहरण के लिए, if {{math|1=''b'' = 2}} तो व्युत्क्रम 1 है), और हेंसल की लेम्मा का उपयोग बार-बार व्युत्क्रम मॉड्यूल {{mvar|b}} उच्च और उच्च शक्तियों को खोजने के लिए किया जाता है, जब व्युत्क्रम मोडुल रुक जाता है {{mvar|R}} ज्ञात है; {{math|''N''&prime;}} इस व्युत्क्रम का निषेध है। स्थिरांक {{math|''R'' mod ''N''}} और {{math|''R''<sup>3</sup> mod ''N''}} के रूप में तथा {{math|REDC(''R''<sup>2</sup> mod ''N'')}} और के रूप में उत्पन्न किया जा सकता है।  {{math|REDC((''R''<sup>2</sup> mod ''N'')(''R''<sup>2</sup> mod ''N''))}} मौलिक ऑपरेशन किसी उत्पाद के आरईडीसी की गणना करना है। जब स्टैंडअलोन आरईडीसी की आवश्यकता होती है, तो इसकी गणना किसी उत्पाद के आरईडीसी के रूप {{math|1 mod ''N''}} में की जा सकती है, इसका एकमात्र स्थान जहां प्रत्यक्ष कमी {{mvar|N}} मोडुल है आवश्यक है कि इसका पूर्वगणना {{math|''R''<sup>2</sup> mod ''N''}} में रखा जाता है।
 == मल्टीप्रिसिजन पूर्णांकों पर मोंटगोमरी अंकगणित ==
-अधिकांश क्रिप्टोग्राफ़िक अनुप्रयोगों के लिए संख्याओं की आवश्यकता होती है जो सैकड़ों या हजारों बिट्स लंबी होती हैं। ऐसी संख्याएँ मशीन शब्द में संग्रहीत करने के लिए बहुत बड़ी हैं। सामान्यतः, हार्डवेयर गुणन मॉड को कुछ आधार करता है {{mvar|B}}, इसलिए बड़े गुणा करने के लिए कई छोटे गुणाओं के संयोजन की आवश्यकता होती है। आधार {{mvar|B}} सामान्यतः माइक्रोइलेक्ट्रॉनिक अनुप्रयोगों के लिए 2 होता है, 2<sup>8</sup> 8-बिट फ़र्मवेयर के लिए,<ref name="kizhvatov" />या 2<sup>32</sup> या 2<sup>64</sup> सॉफ्टवेयर अनुप्रयोगों के लिए।
+अधिकांश क्रिप्टोग्राफ़िक अनुप्रयोगों के लिए संख्याओं की आवश्यकता होती है जो सैकड़ों या हजारों बिट्स लंबी होती हैं। ऐसी संख्याएँ मशीन शब्द में संग्रहीत करने के लिए बहुत बड़ी हैं। सामान्यतः, हार्डवेयर गुणन मॉड को कुछ आधार करता है {{mvar|B}}, इसलिए बड़े गुणा करने के लिए कई छोटे गुणाओं के संयोजन की आवश्यकता होती है। आधार {{mvar|B}} सामान्यतः माइक्रोइलेक्ट्रॉनिक अनुप्रयोगों के लिए 2 होता है, इस कारण 2<sup>8</sup> 8-बिट फ़र्मवेयर के लिए,<ref name="kizhvatov" /> या 2<sup>32</sup> या 2<sup>64</sup> सॉफ्टवेयर अनुप्रयोगों के लिए करते हैं।
-REDC एल्गोरिद्म के लिए उत्पाद मॉड्यूल की आवश्यकता होती है {{mvar|R}}, और सामान्यतः {{math|''R'' &gt; ''N''}} जिससे कि उत्पादों की गणना करने के लिए आरईडीसी का उपयोग किया जा सके। हालाँकि, कब {{mvar|R}} की शक्ति है {{mvar|B}}, REDC का प्रकार है जिसके लिए केवल मशीन शब्द आकार के पूर्णांकों के उत्पादों की आवश्यकता होती है। मान लीजिए कि सकारात्मक बहु-परिशुद्धता पूर्णांक थोड़ा एंडियन संग्रहीत हैं, अर्थात, {{mvar|x}} को सरणी के रूप में संग्रहीत किया जाता है {{math|''x''[0], ..., ''x''[ℓ - 1]}} ऐसा है कि {{math|0 &le; ''x''[''i''] &lt; ''B''}} सभी के लिए {{mvar|i}} और {{math|1=''x'' = &sum; ''x''[''i''] ''B<sup>i</sup>''}}. एल्गोरिदम बहु-परिशुद्धता पूर्णांक से शुरू होता है {{mvar|T}} और इसे बार में शब्द कम कर देता है। पहले का उपयुक्त गुणक {{mvar|N}} बनाने के लिए जोड़ा जाता है {{mvar|T}} द्वारा विभाज्य {{mvar|B}}. फिर का गुणक {{mvar|N}} बनाने के लिए जोड़ा जाता है {{mvar|T}} द्वारा विभाज्य {{math|''B''<sup>2</sup>}}, और इसी तरह। अंततः {{mvar|T}} से विभाज्य है {{mvar|R}}, और विभाजन के बाद {{mvar|R}}एल्गोरिदम उसी स्थान पर है जहाँ REDC की गणना के बाद थी {{mvar|t}}.
+REDC एल्गोरिद्म के लिए उत्पाद मॉड्यूल {{mvar|R}} की आवश्यकता होती है, और सामान्यतः {{math|''R'' &gt; ''N''}} जिससे कि उत्पादों की गणना करने के लिए आरईडीसी का उपयोग किया जा सके। चूंकि, कब {{mvar|R}} की शक्ति है {{mvar|B}}, REDC का प्रकार है जिसके लिए केवल मशीन शब्द आकार के पूर्णांकों के उत्पादों की आवश्यकता होती है। मान लीजिए कि धनात्मक बहु-परिशुद्धता पूर्णांक थोड़ा एंडियन संग्रहीत हैं, अर्थात, {{mvar|x}} को सरणी {{math|''x''[0], ..., ''x''[ℓ - 1]}} के रूप में संग्रहीत किया जाता है, इसका मान इस प्रकार हैं कि {{math|0 &le; ''x''[''i''] &lt; ''B''}} सभी के लिए {{mvar|i}} और {{math|1=''x'' = &sum; ''x''[''i''] ''B<sup>i</sup>''}}. कलन बहु-परिशुद्धता पूर्णांक से प्रारंभ होता है {{mvar|T}} और इसे बार में शब्द कम कर देता है। पहले का उपयुक्त गुणक {{mvar|N}} बनाने के लिए {{mvar|T}} द्वारा विभाज्य {{mvar|B}} जोड़ा जाता है, फिर का गुणक {{mvar|N}} बनाने के लिए जोड़ा जाता है, इस प्रकार {{mvar|T}} द्वारा विभाज्य {{math|''B''<sup>2</sup>}}, और इसी प्रकार अंततः {{mvar|T}} से विभाज्य है {{mvar|R}}, और विभाजन के पश्चात {{mvar|R}} कलन उसी स्थान पर है जहाँ REDC की गणना {{mvar|t}} के पश्चात की गयी थी।
-  फंक्शन मल्टीप्रिसिजनआरईडीसी है
+  '''function''' MultiPrecisionREDC '''is'''
-  इनपुट: पूर्णांक ''एन'' के साथ {{nowrap|1=gcd(''B'', ''N'') = 1}}, पी शब्दों की सरणी के रूप में संग्रहीत,
+     '''Input:''' Integer ''N'' with gcd(''B'', ''N'') = 1, stored as an array of ''p'' words,
-    पूर्णांक {{nowrap|1=''R'' = ''B''<sup>''r''</sup>}}, --इस प्रकार, आर = लॉग<sub>''B''</sub> आर
+            Integer ''R'' = ''B<sup>r</sup>'',     --thus, ''r'' = ''log<sub>B</sub>'' ''R''
-    पूर्णांक एन' में {{nowrap|[0, ''B'' &minus; 1]}} ऐसा है कि {{nowrap|''NN''&prime; ≡ &minus;1 (mod ''B'')}},
+            Integer ''N''′ in [0, ''B'' − 1] such that ''NN''′ ≡ −1 (mod ''B''),
-    सीमा में पूर्णांक टी {{nowrap|0 &le; ''T'' &lt; ''RN''}}, की सरणी के रूप में संग्रहीत {{nowrap|''r'' + ''p''}} शब्द।
+            Integer ''T'' in the range 0 ≤ ''T'' < ''RN'', stored as an array of ''r'' + ''p'' words.
-  आउटपुट: पूर्णांक ''S'' in {{nowrap|[0, ''N'' &minus; 1]}} ऐसा है कि {{nowrap|''TR''<sup>&minus;1</sup> ≡ ''S'' (mod ''N'')}}, पी शब्दों की सरणी के रूप में संग्रहीत।
+     '''Output:''' Integer ''S'' in [0, ''N'' − 1] such that ''TR''<sup>−1</sup> ≡ ''S'' (mod ''N''), stored as an array of ''p'' words.
-  तय करना {{nowrap|1=''T''[''r'' + ''p''] = 0}} (अतिरिक्त कैरी शब्द)
+     Set ''T''[''r'' + ''p''] = 0  ''(extra carry word)''
-  'के लिए' {{nowrap|0 &le; ''i'' &lt; ''r''}} करना
+     '''for''' 0 ≤ ''i'' < ''r'' '''do'''
-   ''--loop1- टी को विभाज्य बनाएं {{nowrap|B<sup>i+1</sup>}}
+         ''--loop1- Make T divisible by B<sup>i+1</sup>''
-   सी ← 0
+         ''c'' ← 0
-   एम ← {{nowrap|''T''[''i''] ⋅ ''N''&prime; mod ''B''}}
+         ''m'' ← ''T''[''i''] ⋅ ''N''′ mod ''B''
-   के लिए {{nowrap|0 &le; ''j'' &lt; ''p''}} करना
+         '''for''' 0 ≤ ''j'' < ''p'' '''do'''
-    ''--लूप2- का निम्न शब्द जोड़ें {{nowrap|m ⋅ N[j]}} और पहले से कैरी करें, और नया कैरी ढूंढें
+             ''--loop2- Add the low word of m ⋅ N[j] and the carry from earlier, and find the new carry''
-    एक्स ← {{nowrap|''T''[''i'' + ''j''] + ''m'' ⋅ ''N''[''j''] + ''c''}}
+             ''x'' ← ''T''[''i'' + ''j''] + ''m'' ⋅ ''N''[''j''] + ''c''
-    टी [आई + जे] ← {{nowrap|''x'' mod ''B''}}
+             ''T''[''i'' + ''j''] ← ''x'' mod ''B''
-    सी ← {{nowrap|⌊''x'' / ''B''⌋}}
+             ''c'' ← ⌊''x'' / ''B''⌋
-   के लिए समाप्त
+         '''end for'''
-   के लिए {{nowrap|''p'' &le; ''j'' &le; ''r'' + ''p'' &minus; ''i''}} करना
+         '''for''' ''p'' ≤ ''j'' ≤ ''r'' + ''p'' − ''i'' '''do'''
-    ''--लूप3- ले जाना जारी रखें''
+             ''--loop3- Continue carrying''
-    ''एक्स'' ← {{nowrap|''T''[''i'' + ''j''] + ''c''}}
+             ''x'' ← ''T''[''i'' + ''j''] + ''c''
-    टी [आई + जे] ← {{nowrap|''x'' mod ''B''}}
+             ''T''[''i'' + ''j''] ← ''x'' mod ''B''
-    सी ← {{nowrap|⌊''x'' / ''B''⌋}}
+             ''c'' ← ⌊''x'' / ''B''⌋
-   के लिए समाप्त
+         '''end for'''
-  के लिए समाप्त
+     '''end for'''
-  के लिए {{nowrap|0 &le; ''i'' &lt; ''p''}} करना
+     '''for''' 0 ≤ ''i'' < ''p'' '''do'''
-   ''एस''[''आई''] ← ''टी''[''आई'' + ''आर'']
+         ''S''[''i''] ← ''T''[''i'' + ''r'']
-  के लिए समाप्त
+     '''end for'''
-  अगर {{nowrap|''S'' &ge; ''N''}} तब
+     '''if''' ''S'' ≥ ''N'' '''then'''
-   वापस करना {{nowrap|''S'' &minus; ''N''}}
+         '''return''' ''S'' − ''N''
-  अन्य
+     '''else'''
-   वापस करना {{var|S}}
+         '''return''' <var>S</var>
-  अगर अंत
+     '''end if'''
-  अंत समारोह
-अंतिम तुलना और घटाव मानक एल्गोरिदम द्वारा किया जाता है।
+  '''end function'''
+अंतिम तुलना और घटाव मानक कलन द्वारा किया जाता है।
-उपरोक्त एल्गोरिथ्म अनिवार्य रूप से उन्हीं कारणों से सही है जो REDC सही हैं। हर बार के माध्यम से {{mvar|i}} कुंडली, {{mvar|m}} चुना जाता है जिससे कि {{math|''T''[''i''] + ''mN''[0]}} से विभाज्य है {{mvar|B}}. तब {{mvar|mNB<sup>i</sup>}} जोड़ा जाता है {{mvar|T}}. क्योंकि यह मात्रा जीरो मॉड है {{mvar|N}}, इसे जोड़ने से का मान प्रभावित नहीं होता है {{math|''T'' mod ''N''}}. अगर {{mvar|m<sub>i</sub>}} के मान को दर्शाता है {{mvar|m}} में गणना की गई {{mvar|i}लूप का } वाँ पुनरावृत्ति, फिर एल्गोरिथम सेट करता है {{mvar|S}} को {{math|''T'' + (&sum; ''m<sub>i</sub> B<sup>i</sup>'')''N''}}. क्योंकि मल्टी प्रेसिजन REDC और REDC ही आउटपुट का उत्पादन करते हैं, यह योग विकल्प के समान है {{mvar|m}} कि REDC एल्गोरिथम बना देगा।
+उपरोक्त एल्गोरिथ्म अनिवार्य रूप से उन्हीं कारणों से सही है जो REDC सही हैं। हर बार के माध्यम से {{mvar|i}} कुंडली, {{mvar|m}} चुना जाता है जिससे कि {{math|''T''[''i''] + ''mN''[0]}} से विभाज्य है {{mvar|B}}. तब {{mvar|mNB<sup>i</sup>}} जोड़ा जाता है {{mvar|T}}. क्योंकि यह मात्रा जीरो मॉड है {{mvar|N}}, इसे जोड़ने से का मान {{math|''T'' mod ''N''}} प्रभावित नहीं होता है। इस प्रकार यदि {{mvar|m<sub>i</sub>}} के मान को दर्शाता है {{mvar|m}}<nowiki> में गणना की गई {{mvar|i}लूप का } वाँ पुनरावृत्ति, फिर कलन समुच्चय करता है जिसके लिए </nowiki>{{mvar|S}} को {{math|''T'' + (&sum; ''m<sub>i</sub> B<sup>i</sup>'')''N''}}  द्वारा दर्शाते हैं क्योंकि मल्टी प्रेसिजन REDC और REDC ही आउटपुट का उत्पादन करते हैं, यह योग विकल्प के समान है {{mvar|m}} कि REDC कलन बना देगा।
-का अंतिम शब्द {{mvar|T}}, {{math|''T''[''r'' + ''p'']}} (और इसके परिणामस्वरूप {{math|''S''[''p'']}}), का उपयोग केवल कैरी रखने के लिए किया जाता है, क्योंकि प्रारंभिक कमी का परिणाम की सीमा में परिणाम के लिए बाध्य होता है {{math|0 &le; ''S'' &lt; ''2N''}}. इससे यह निष्कर्ष निकलता है कि इस अतिरिक्त कैरी शब्द से पूरी तरह बचा जा सकता है यदि यह पहले से ज्ञात हो {{math|''R'' &ge; ''2N''}}. विशिष्ट बाइनरी कार्यान्वयन पर, यह कहने के बराबर है कि यदि बिट्स की संख्या हो तो इस कैरी शब्द से बचा जा सकता है {{mvar|N}} बिट्स की संख्या से छोटा है {{mvar|R}}. अन्यथा, वहन या तो शून्य या होगा। प्रोसेसर के आधार पर, इस शब्द को पूर्ण आकार के शब्द के अतिरिक्त कैरी फ़्लैग के रूप में संग्रहीत करना संभव हो सकता है।
+का अंतिम शब्द {{mvar|T}}, {{math|''T''[''r'' + ''p'']}} (और इसके परिणामस्वरूप {{math|''S''[''p'']}}), का उपयोग केवल कैरी रखने के लिए किया जाता है, क्योंकि प्रारंभिक कमी का परिणाम की सीमा में परिणाम के लिए बाध्य होता है {{math|0 &le; ''S'' &lt; ''2N''}}. इससे यह निष्कर्ष निकलता है कि इस अतिरिक्त कैरी शब्द से पूर्ण रूप से बचा जा सकता है यदि यह पहले से ज्ञात हो {{math|''R'' &ge; ''2N''}} जिसका विशिष्ट बाइनरी कार्यान्वयन पर, यह कहने के बराबर है कि यदि बिट्स की संख्या हो तो इस कैरी शब्द से बचा जा सकता है {{mvar|N}} बिट्स की संख्या से छोटा है {{mvar|R}}. अन्यथा, वहन या तो शून्य या होगा। प्रोसेसर के आधार पर, इस शब्द को पूर्ण आकार के शब्द के अतिरिक्त कैरी फ़्लैग के रूप में संग्रहीत करना संभव हो सकता है।
-मल्टीप्रिसिजन गुणन और आरईडीसी को एल्गोरिथम में जोड़ना संभव है। इस संयुक्त एल्गोरिथ्म को सामान्यतः मोंटगोमरी गुणन कहा जाता है। Koç, Acar, और Kaliski द्वारा कई अलग-अलग कार्यान्वयनों का वर्णन किया गया है।<ref>{{cite journal |author1=Çetin K. Koç |author2=Tolga Acar |author3=Burton S. Kaliski, Jr. |title=मोंटगोमरी गुणन एल्गोरिदम का विश्लेषण और तुलना|journal=[[IEEE Micro]] |date=June 1996 |volume=16 |number=3 |pages=26–33 |doi=10.1109/40.502403 |citeseerx=10.1.1.26.3120 |url=https://www.microsoft.com/en-us/research/wp-content/uploads/1996/01/j37acmon.pdf}}</ref> एल्गोरिथ्म जितना कम उपयोग कर सकता है {{math|''p'' + 2}} स्टोरेज के शब्द (प्लस कैरी बिट)।
+मल्टीप्रिसिजन गुणन और आरईडीसी को कलन में जोड़ना संभव है। इस संयुक्त एल्गोरिथ्म को सामान्यतः मोंटगोमरी गुणन कहा जाता है। इस प्रकार Koç, Acar, और Kaliski द्वारा कई अलग-अलग कार्यान्वयनों का वर्णन किया गया है।<ref>{{cite journal |author1=Çetin K. Koç |author2=Tolga Acar |author3=Burton S. Kaliski, Jr. |title=मोंटगोमरी गुणन एल्गोरिदम का विश्लेषण और तुलना|journal=[[IEEE Micro]] |date=June 1996 |volume=16 |number=3 |pages=26–33 |doi=10.1109/40.502403 |citeseerx=10.1.1.26.3120 |url=https://www.microsoft.com/en-us/research/wp-content/uploads/1996/01/j37acmon.pdf}}</ref> इस कारण {{math|''p'' + 2}} स्टोरेज के शब्द प्लस कैरी बिट के लिए एल्गोरिथ्म जितना कम उपयोग कर सकता है ।
-एक उदाहरण के रूप में, चलो {{math|1=''B'' = 10}}, {{math|1=''N'' = 997}}, और {{math|1=''R'' = 1000}}. लगता है कि {{math|1=''a'' = 314}} और {{math|1=''b'' = 271}}. मोंटगोमरी का प्रतिनिधित्व {{mvar|a}} और {{mvar|b}} हैं {{math|1=314000 mod 997 = 942}} और {{math|1=271000 mod 997 = 813}}. गणना करना {{math|1=942 ⋅ 813 = 765846}}. प्रारंभिक इनपुट {{mvar|T}} से मल्टी प्रेसिजन REDC होगा [6, 4, 8, 5, 6, 7]। जो नंबर {{mvar|N}} को [7, 9, 9] के रूप में दर्शाया जाएगा। विस्तारित यूक्लिडियन एल्गोरिथ्म कहता है कि {{math|1=&minus;299 ⋅ 10 + 3 ⋅ 997 = 1}}, इसलिए {{math|''N''&prime;}} 7 होगा।
+एक उदाहरण के रूप में, चलो {{math|1=''B'' = 10}}, {{math|1=''N'' = 997}}, और {{math|1=''R'' = 1000}} के मान पर लगता है कि {{math|1=''a'' = 314}} और {{math|1=''b'' = 271}} मोंटगोमरी का प्रतिनिधित्व {{mvar|a}} और {{mvar|b}} हैं जिसका मान {{math|1=314000 mod 997 = 942}} और {{math|1=271000 mod 997 = 813}} प्राप्त होता हैं। जिसकी गणना करने पर {{math|1=942 ⋅ 813 = 765846}} मान प्राप्त होता हैं। इसका प्रारंभिक इनपुट {{mvar|T}} से मल्टी प्रेसिजन REDC [6, 4, 8, 5, 6, 7] होगा। जो नंबर {{mvar|N}} को [7, 9, 9] के रूप में दर्शाया जाता हैं। विस्तारित यूक्लिडियन एल्गोरिथ्म कहता है कि {{math|1=&minus;299 ⋅ 10 + 3 ⋅ 997 = 1}}, इसलिए {{math|''N''&prime;}} का मान 7 होता हैं।
-  मैं ← 0
+  i ← 0
-  एम ← {{nowrap|1=6 ⋅ 7 mod 10 = 2}}
+  m ← 6 ⋅ 7 mod 10 = 2
-  जे टी सी
+  j T       c
   - ------- -
-0485670 2 (पहले पाश की पहली पुनरावृत्ति के बाद)
+0485670 2    ''(After first iteration of first loop)''
 0485670 2
 0485670 2
-0487670 0 (दूसरे लूप के पहले पुनरावृत्ति के बाद)
+0487670 0    ''(After first iteration of second loop)''
 0487670 0
 0487670 0
 0487670 0
-  मैं ← 1
+  i ← 1
-  एम ← {{nowrap|1=4 ⋅ 7 mod 10 = 8}}
+  m ← 4 ⋅ 7 mod 10 = 8
-  जे टी सी
+  j T       c
   - ------- -
-0087670 6 (पहले पाश की पहली पुनरावृत्ति के बाद)
+0087670 6    ''(After first iteration of first loop)''
 0067670 8
 0067670 8
-0067470 1 (दूसरे लूप के पहले पुनरावृत्ति के बाद)
+0067470 1    ''(After first iteration of second loop)''
 0067480 0
 0067480 0
-  मैं ← 2
+  i ← 2
-  एम ← {{nowrap|1=6 ⋅ 7 mod 10 = 2}}
+  m ← 6 ⋅ 7 mod 10 = 2
-  जे टी सी
+  j T       c
   - ------- -
-0007480 2 (पहले लूप की पहली पुनरावृत्ति के बाद)
+0007480 2    ''(After first iteration of first loop)''
 0007480 2
 0007480 2
-0007400 1 (दूसरे लूप की पहली पुनरावृत्ति के बाद)
+0007400 1    ''(After first iteration of second loop)''
 0007401 0
+इसलिए, अंतिम तुलना और घटाव से पहले, {{math|1=''S'' = 1047}}. अंतिम घटाव संख्या 50 देता है। मोंटगोमरी के प्रतिनिधित्व के पश्चात {{math|1=314 ⋅ 271 mod 997 = 349}} है {{math|1=349000 mod 997 = 50}}, यह अपेक्षित परिणाम है।
-इसलिए, अंतिम तुलना और घटाव से पहले, {{math|1=''S'' = 1047}}. अंतिम घटाव संख्या 50 देता है। मोंटगोमरी के प्रतिनिधित्व के बाद से {{math|1=314 ⋅ 271 mod 997 = 349}} है {{math|1=349000 mod 997 = 50}}, यह अपेक्षित परिणाम है।
+बेस 2 में कार्य करते समय, सही का निर्धारण करना {{mvar|m}} प्रत्येक चरण में विशेष रूप से सरल है: यदि वर्तमान फलन का मान बिट के रूप में सम संख्या के रूप में प्रदर्शित होता है, तो {{mvar|m}} शून्य है और यदि यह विषम है, तो {{mvar|m}} है। इसके अतिरिक्त, क्योंकि मल्टी प्रेसिजन REDC के प्रत्येक चरण को केवल सबसे कम बिट जानने की आवश्यकता होती है, मॉन्टगोमरी गुणन को [[कैरी-सेव योजक]] के साथ सरलता से जोड़ा जा सकता है।
-बेस 2 में कार्य करते समय, सही का निर्धारण करना {{mvar|m}} प्रत्येक चरण में विशेष रूप से आसान है: यदि वर्तमान कार्यकाजी बिट सम है, तो {{mvar|m}} शून्य है और यदि यह विषम है, तो {{mvar|m}} है। इसके अतिरिक्त, क्योंकि मल्टी प्रेसिजन REDC के प्रत्येक चरण को केवल सबसे कम बिट जानने की आवश्यकता होती है, मॉन्टगोमरी गुणन को [[कैरी-सेव योजक]] के साथ सरलता से जोड़ा जा सकता है।
-== साइड-चैनल हमले ==
+== साइड-चैनल अटैक ==
-चूंकि भागफल अंकों के अनुमान गलत होने पर मॉन्टगोमरी कटौती पारंपरिक विभाजन में आवश्यक सुधार चरणों से बचती है, यह ज्यादातर सशर्त शाखाओं से मुक्त है जो समय और पावर साइड-चैनल हमलों के प्राथमिक लक्ष्य हैं; निष्पादित निर्देशों का क्रम इनपुट ऑपरेंड मूल्यों से स्वतंत्र है। एकमात्र अपवाद मापांक का अंतिम सशर्त घटाव है, अपितु इसे प्रतिरोधी बनाने के लिए इसे सरलता से संशोधित किया जाता है (सदैव कुछ घटाना, या तो मापांक या शून्य)।<ref name="kizhvatov">{{cite conference
+चूंकि भागफल अंकों के अनुमान गलत होने पर मॉन्टगोमरी कटौती पारंपरिक विभाजन में आवश्यक सुधार चरणों से बचती है, यह अधिकतम सशर्त शाखाओं से मुक्त है जो समय और पावर साइड-चैनल हमलों के प्राथमिक लक्ष्य हैं, निष्पादित निर्देशों का क्रम इनपुट ऑपरेंड मूल्यों से स्वतंत्र है। इसका एकमात्र अपवाद मापांक का अंतिम सशर्त घटाव है, अपितु इसे प्रतिरोधी बनाने के लिए इसे सरलता से संशोधित किया जाता है इसके लिए सदैव कुछ कमी होने से मापांक शून्य हो जाता हैं।<ref name="kizhvatov">{{cite conference
   |first1=Zhe |last1=Liu  |first2=Johann |last2=Großschädl  |first3=Ilya |last3=Kizhvatov
   |url=https://www.nics.uma.es/seciot10/files/pdf/liu_seciot10_paper.pdf
@@ Line 193: / Line 195: @@
   |date=29 November 2010 |location=Tokyo
   |conference-url=https://www.nics.uma.es/pub/seciot10/
-}}  ([https://www.nics.uma.es/pub/seciot10/files/ppt/liu_seciot10.pdf Presentation slides].)</ref> यह निश्चित रूप से आवश्यक है कि गुणन के समीप निर्मित घातांक एल्गोरिथ्म भी प्रतिरोधी हो।{{r|kizhvatov}}<ref>Marc Joye and Sung-Ming Yen. [http://cr.yp.to/bib/2003/joye-ladder.pdf "The Montgomery Powering Ladder"]. 2002.</ref>
+}}  ([https://www.nics.uma.es/pub/seciot10/files/ppt/liu_seciot10.pdf Presentation slides].)</ref> यह निश्चित रूप से आवश्यक है कि गुणन के समीप निर्मित घातांक एल्गोरिथ्म भी प्रतिरोधी होता हैं।{{r|kizhvatov}}<ref>Marc Joye and Sung-Ming Yen. [http://cr.yp.to/bib/2003/joye-ladder.pdf "The Montgomery Powering Ladder"]. 2002.</ref>
 == यह भी देखें ==
 * बैरेट कमी
@@ Line 205: / Line 205: @@
 ==बाहरी संबंध==
 * {{cite document |title=Theory and practice of Montgomery multiplication |author=Henry S. Warren, Jr. |date=July 2012|citeseerx=10.1.1.450.6124 }}
-[[Category: कंप्यूटर अंकगणित]] [[Category: क्रिप्टोग्राफिक एल्गोरिदम]] [[Category: मॉड्यूलर अंकगणित]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 errors]]
 [[Category:Created On 18/05/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with maths render errors]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Webarchive template wayback links]]
+[[Category:कंप्यूटर अंकगणित]]
+[[Category:क्रिप्टोग्राफिक एल्गोरिदम]]
+[[Category:मॉड्यूलर अंकगणित]]

Anonymous

Search

मोंटगोमरी मॉड्यूलर गुणन: Difference between revisions

Latest revision as of 16:16, 29 May 2023

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

मोंटगोमरी फॉर्म

आरईडीसी कलन

मोंटगोमरी रूप में अंकगणित

मल्टीप्रिसिजन पूर्णांकों पर मोंटगोमरी अंकगणित

साइड-चैनल अटैक

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories