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

मॉड्यूलर अंकगणितीय संगणना में, मोंटगोमरी मॉड्यूलर गुणन, जिसे सामान्यतः मोंटगोमरी गुणन के रूप में संदर्भित किया जाता है, तेजी से मॉड्यूलर गुणन करने की विधि है। इसे 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}}.

इसलिए, आउटपुट में सही अवशेष वर्ग है। तीसरा, $m$ में है $[0, R - 1]$ , और इसलिए $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$ , क्रमश। उनका उत्पाद 28 इनपुट है $T$ आरईडीसी के लिए, और उसके बाद से $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

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

Namespaces

More

Page actions

Contents

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

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

आरईडीसी एल्गोरिदम

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

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

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

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

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

आरईडीसी एल्गोरिदम

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

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

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories