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

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

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

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

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

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

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

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

कंप्यूटर पर संपूर्ण अवशेष वर्ग को संग्रहीत करना असंभव है क्योंकि अवशेष वर्ग में असीम रूप से कई तत्व होते हैं। इसके बजाय, अवशेष वर्गों को प्रतिनिधि के रूप में संग्रहीत किया जाता है। परंपरागत रूप से, ये प्रतिनिधि पूर्णांक होते हैं a जिसके लिए 0 ≤ a ≤ N − 1. अगर a एक पूर्णांक है, तो इसका प्रतिनिधि है a लिखा है a mod N. सर्वांगसमता लिखते समय, एक पूर्णांक की पहचान उस अवशेष वर्ग के साथ करना आम है जो यह प्रतिनिधित्व करता है। इस परिपाटी के साथ उपरोक्त समानता लिखी जाती है a ≡ b mod N.

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

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

अगर a और b श्रेणी में पूर्णांक हैं [0, N − 1], तो उनका योग सीमा में है [0, 2N − 2] और उनका अंतर सीमा में है [−N + 1, N − 1], इसलिए प्रतिनिधि का निर्धारण करना [0, N − 1] के लिए अधिकतम एक घटाव या जोड़ (क्रमशः) आवश्यक है N. हालाँकि, उत्पाद ab के दायरे में है [0, N² − 2N + 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 ⋅ 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/NZ. उदाहरण के लिए, (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′ ≡ 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⋅100 − 47⋅17 = 1, इसलिए R′ = 8. 96 प्राप्त करने के लिए 12 को 8 से गुणा करें और 11 प्राप्त करने के लिए मॉडुलो 17 को कम करें। यह अपेक्षा के अनुरूप 3 का मोंटगोमरी रूप है।

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

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

समारोह आरईडीसी है
    इनपुट: पूर्णांक आर और एन के साथ gcd(R, N) = 1,
           पूर्णांक एन' में [0, R − 1] ऐसा है कि NN′ ≡ −1 mod R,
           सीमा में पूर्णांक टी [0, RN − 1].
    आउटपुट: श्रेणी में पूर्णांक एस [0, N − 1] ऐसा है कि S ≡ TR−1 mod N

    एम ← ((टी मॉड आर) एन ') मॉड आर
    टी ← (टी + एमएन) / आर
    'अगर' टी ≥ एन 'फिर'
        'वापस करना' t − N
    अन्य
        वापसी टी
    अगर अंत
अंत समारोह

यह देखने के लिए कि यह एल्गोरिदम सही है, पहले उसका निरीक्षण करें 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⁻¹ 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 < 2RN. इस तरह t मै रुक जाना 2N, और क्योंकि यह एक पूर्णांक है, यह डालता है t सीमा में [0, 2N − 1]. इसलिए कम कर रहा है t वांछित सीमा में अधिकतम एक घटाव की आवश्यकता होती है, इसलिए एल्गोरिथम का आउटपुट सही सीमा में होता है।

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

एक अन्य उदाहरण के रूप में, उत्पाद पर विचार करें 7 ⋅ 15 mod 17 लेकिन इसके साथ R = 10. विस्तारित यूक्लिडियन एल्गोरिथम का उपयोग करके गणना करें −5 ⋅ 10 + 3 ⋅ 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) ⋅ 7 mod 10 = 196 mod 10 = 6. तब 28 + 6 ⋅ 17 = 130, इसलिए t = 13. क्योंकि 30 mod 17 = 13, यह मोंटगोमरी का रूप है 3 = 7 ⋅ 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² mod N)). कंप्यूटिंग द्वारा मोंटगोमरी फॉर्म से रूपांतरण किया जाता है REDC(aR mod N). का मॉड्यूलर व्युत्क्रम aR mod N है REDC((aR mod N)⁻¹(R³ mod N)). प्रारंभिक गुणनफल को 1 के मोंटगोमरी निरूपण के लिए प्रारंभ करके, वर्ग करके घातांक का उपयोग करके मॉड्यूलर घातांक किया जा सकता है, अर्थात R mod N, और मोंटगोमरी गुणा द्वारा गुणा और वर्ग चरणों को प्रतिस्थापित करके।

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

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

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

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

फंक्शन मल्टीप्रिसिजनआरईडीसी है
    इनपुट: पूर्णांक एन के साथ gcd(B, N) = 1, पी शब्दों की एक सरणी के रूप में संग्रहीत,
           पूर्णांक R = Br, --इस प्रकार, आर = लॉगB आर
           पूर्णांक एन' में [0, B − 1] ऐसा है कि NN′ ≡ −1 (mod B),
           सीमा में पूर्णांक टी 0 ≤ T < RN, की एक सरणी के रूप में संग्रहीत r + p शब्द।

    आउटपुट: पूर्णांक S in [0, N − 1] ऐसा है कि TR−1 ≡ S (mod N), पी शब्दों की एक सरणी के रूप में संग्रहीत।

    तय करना T[r + p] = 0 (अतिरिक्त कैरी शब्द)
    'के लिए' 0 ≤ i < r करना
        --loop1- टी को विभाज्य बनाएं Bi+1

        सी ← 0
        एम ← T[i] ⋅ N′ mod B
        के लिए 0 ≤ j < p करना
            --लूप2- का निम्न शब्द जोड़ें m ⋅ N[j] और पहले से कैरी करें, और नया कैरी ढूंढें

            एक्स ← T[i + j] + m ⋅ N[j] + c
            टी [आई + जे] ← x mod B
            सी ← ⌊x / B⌋
        के लिए समाप्त
        के लिए p ≤ j ≤ r + p − i करना
            --लूप3- ले जाना जारी रखें

            एक्स ← T[i + j] + c
            टी [आई + जे] ← x mod B
            सी ← ⌊x / B⌋
        के लिए समाप्त
    के लिए समाप्त

    के लिए 0 ≤ i < p करना
        एस[आई] ← टी[आई + आर]
    के लिए समाप्त

    अगर S ≥ N तब
        वापस करना S − N
    अन्य
        वापस करना S
    अगर अंत
अंत समारोह

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

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

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

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

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

मैं ← 0
एम ← 6 ⋅ 7 mod 10 = 2

जे टी सी
- ------- -
0 0485670 2 (पहले पाश की पहली पुनरावृत्ति के बाद)
1 0485670 2
2 0485670 2
3 0487670 0 (दूसरे लूप के पहले पुनरावृत्ति के बाद)
4 0487670 0
5 0487670 0
6 0487670 0

मैं ← 1
एम ← 4 ⋅ 7 mod 10 = 8

जे टी सी
- ------- -
0 0087670 6 (पहले पाश की पहली पुनरावृत्ति के बाद)
1 0067670 8
2 0067670 8
3 0067470 1 (दूसरे लूप के पहले पुनरावृत्ति के बाद)
4 0067480 0
5 0067480 0

मैं ← 2
एम ← 6 ⋅ 7 mod 10 = 2

जे टी सी
- ------- -
0 0007480 2 (पहले लूप की पहली पुनरावृत्ति के बाद)
1 0007480 2
2 0007480 2
3 0007400 1 (दूसरे लूप की पहली पुनरावृत्ति के बाद)
4 0007401 0

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

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

साइड-चैनल हमले

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

यह भी देखें

• बैरेट कमी

बाहरी संबंध

• 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)