मोंटगोमरी मॉड्यूलर गुणन: Difference between revisions
No edit summary |
No edit summary |
||
| 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> | }}</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|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|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}} धनात्मक पूर्णांक मापांक दर्शाता है। [[भागफल की अंगूठी|भागफल की रिंग]] {{math|'''Z'''/''N'''''Z'''}} में {{mvar|N}} अवशेषों वाले वर्ग मॉड्यूल सम्मिलित रहते हैं , अर्ताथ इसके तत्व फॉर्म के समुच्चय हैं, जो इस प्रकार हैं- | ||
:<math>\{ a + kN \colon k \in \mathbf{Z} \},</math> | :<math>\{ a + kN \colon k \in \mathbf{Z} \},</math> | ||
जहाँ {{mvar|a}} पूर्णांकों के बीच है। प्रत्येक अवशेष वर्ग पूर्णांकों का समूह है जैसे कि समुच्चय में किसी भी दो पूर्णांकों का अंतर विभाज्य {{mvar|N}} है और अवशेष वर्ग उस संपत्ति के संबंध में अधिकतम है; पूर्णांकों को अवशेष वर्ग से बाहर नहीं छोड़ा जाता है जब तक कि वे विभाज्यता की स्थिति का उल्लंघन नहीं करते हैं। इस प्रकार अवशेष वर्ग के अनुरूप {{mvar|a}} | जहाँ {{mvar|a}} पूर्णांकों के बीच है। प्रत्येक अवशेष वर्ग पूर्णांकों का समूह है जैसे कि समुच्चय में किसी भी दो पूर्णांकों का अंतर विभाज्य {{mvar|N}} है और अवशेष वर्ग उस संपत्ति के संबंध में अधिकतम है; पूर्णांकों को अवशेष वर्ग से बाहर नहीं छोड़ा जाता है जब तक कि वे विभाज्यता की स्थिति का उल्लंघन नहीं करते हैं। इस प्रकार अवशेष वर्ग के अनुरूप {{mvar|a}} तथा {{math|{{overline|''a''}}}} द्वारा अंकित किया जाता है, इस प्रकार अवशेष वर्गों की समानता को सर्वांगसमता कहा जाता है और इसे इस प्रकार निरूपित किया जाता है। | ||
:<math>\bar a \equiv \bar b \pmod{N}.</math> | :<math>\bar a \equiv \bar b \pmod{N}.</math> | ||
कंप्यूटर पर संपूर्ण अवशेष वर्ग को संग्रहीत करना असंभव है क्योंकि अवशेष वर्ग में असीम रूप से कई तत्व होते हैं। इसके अतिरिक्त | कंप्यूटर पर संपूर्ण अवशेष वर्ग को संग्रहीत करना असंभव है क्योंकि अवशेष वर्ग में असीम रूप से कई तत्व होते हैं। इसके अतिरिक्त अवशेष वर्गों को प्रतिनिधि के रूप में संग्रहीत किया जाता है। परंपरागत रूप से, ये प्रतिनिधि पूर्णांक होते हैं, जहाँ पर {{mvar|a}} जिसके लिए {{math|0 ≤ ''a'' ≤ ''N'' − 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=''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'' − 1]}} हैं, तो उनका योग सीमा {{math|[0, 2''N'' − 2]}} में है और उनका अंतर सीमा में {{math|[−''N'' + 1, ''N'' − 1]}} है, इसलिए प्रतिनिधि का निर्धारण करना {{math|[0, ''N'' − 1]}} के लिए अधिकतम घटाव या जोड़ क्रमशः {{mvar|N}} के लिए आवश्यक है, चूंकि, उत्पाद {{math|''ab''}} की सीमा {{math|[0, ''N''<sup>2</sup> − 2''N'' + 1]}} में है। मध्यवर्ती पूर्णांक उत्पाद का भंडारण {{math|''ab''}} को या तो दोगुने बिट्स की आवश्यकता होती है इस प्रकार {{mvar|a}} या {{mvar|b}}, और कुशलता से प्रतिनिधि का निर्धारण {{math|[0, ''N'' − 1]}} विभाजन की आवश्यकता है। गणितीय रूप से, 0 और के बीच का पूर्णांक {{math|''N'' − 1}} के अनुरूप है {{math|''ab''}} को यूक्लिडियन डिवीजन प्रमेय के कथन को लागू करके व्यक्त किया जा सकता है: | |||
:<math>ab = qN + r,</math> | :<math>ab = qN + r,</math> | ||
जहाँ {{mvar|q}} भागफल है <math>\lfloor ab / N \rfloor</math> और {{mvar|r}}, शेष, अंतराल में है {{math|[0, ''N'' − 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'' − 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> सरल हो जाता हैं। | ||
| Line 30: | Line 30: | ||
क्योंकि की गणना {{mvar|q}} विभाजन की आवश्यकता है, यह अधिकांश कंप्यूटर हार्डवेयर पर अवांछनीय रूप से महंगा है। मोंटगोमरी फॉर्म रिंग के तत्वों को व्यक्त करने का अलग तरीका है जिसमें मॉड्यूलर उत्पादों की गणना महंगे डिवीजनों के बिना की जा सकती है। जबकि विभाजन अभी भी आवश्यक हैं, उन्हें अलग भाजक {{mvar|R}} के संबंध में किया जा सकता है। इस विभाजक को दो की शक्ति के रूप में चुना जा सकता है, जिसके लिए विभाजन को शिफ्टिंग, या मशीनी शब्दों की पूरी संख्या से परिवर्तित किया जा सकता है, जिसके लिए शब्दों को छोड़ कर विभाजन को परिवर्तित किया जा सकता है। ये विभाजन तेज़ हैं, इसलिए मोंटगोमरी फॉर्म का उपयोग करके मॉड्यूलर उत्पादों की गणना करने की अधिकांश लागत साधारण उत्पादों की गणना करने की लागत है। | क्योंकि की गणना {{mvar|q}} विभाजन की आवश्यकता है, यह अधिकांश कंप्यूटर हार्डवेयर पर अवांछनीय रूप से महंगा है। मोंटगोमरी फॉर्म रिंग के तत्वों को व्यक्त करने का अलग तरीका है जिसमें मॉड्यूलर उत्पादों की गणना महंगे डिवीजनों के बिना की जा सकती है। जबकि विभाजन अभी भी आवश्यक हैं, उन्हें अलग भाजक {{mvar|R}} के संबंध में किया जा सकता है। इस विभाजक को दो की शक्ति के रूप में चुना जा सकता है, जिसके लिए विभाजन को शिफ्टिंग, या मशीनी शब्दों की पूरी संख्या से परिवर्तित किया जा सकता है, जिसके लिए शब्दों को छोड़ कर विभाजन को परिवर्तित किया जा सकता है। ये विभाजन तेज़ हैं, इसलिए मोंटगोमरी फॉर्म का उपयोग करके मॉड्यूलर उत्पादों की गणना करने की अधिकांश लागत साधारण उत्पादों की गणना करने की लागत है। | ||
सहायक मापांक {{mvar|R}} धनात्मक पूर्णांक होना चाहिए जैसे कि {{math|1=gcd(''R'', ''N'') = 1}} | सहायक मापांक {{mvar|R}} धनात्मक पूर्णांक होना चाहिए जैसे कि {{math|1=gcd(''R'', ''N'') = 1}} इसका उदाहरण हैं। इस प्रकार कम्प्यूटरीकृत उद्देश्यों के लिए यह भी आवश्यक है कि विभाजन और कमी मोडुलो {{mvar|R}} सरल हैं, और मॉड्यूलस मॉड्यूलर गुणन के लिए तब तक उपयोगी नहीं है जब तक {{math|''R'' > ''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>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=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 \bmod N)(bR \bmod N) \bmod N = (abR)R \bmod N.</math> | :<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''′}} को प्राप्त किया जा सकता है, ऐसा है कि {{math|''RR''′ ≡ 1 (mod ''N'')}}, अर्ताथ द्वारा {{math|''R''′}} जिसका अवशेष वर्ग मॉड्यूलर व्युत्क्रम {{mvar|R}} है, इसके विरुद्ध {{mvar|N}} पुनः, कार्य कर रहे मॉड्यूल {{mvar|N}}, को इस प्रकार प्राप्त करते | जिसके अतिरिक्त कारक को हटाना {{mvar|R}} को पूर्णांक से गुणा करके {{math|''R''′}} को प्राप्त किया जा सकता है, ऐसा है कि {{math|''RR''′ ≡ 1 (mod ''N'')}}, अर्ताथ द्वारा {{math|''R''′}} जिसका अवशेष वर्ग मॉड्यूलर व्युत्क्रम {{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>(aR \bmod N)(bR \bmod N)R' \equiv (aR)(bR)R^{-1} \equiv (ab)R \pmod{N}.</math> | ||
पूर्णांक {{math|''R''′}} इस धारणा के कारण सम्मिलित है कि {{mvar|R}} और {{mvar|N}} को-प्राइम हैं। इसका निर्माण विस्तारित यूक्लिडियन एल्गोरिथम का उपयोग करके किया जा सकता है। [[विस्तारित यूक्लिडियन एल्गोरिथ्म]] कुशलतापूर्वक पूर्णांकों को निर्धारित करता है, इस प्रकार {{math|''R''′}} और {{math|''N''′}} जो बेज़ाउट की पहचान को संतुष्ट करते हैं: | पूर्णांक {{math|''R''′}} इस धारणा के कारण सम्मिलित है कि {{mvar|R}} और {{mvar|N}} को-प्राइम हैं। इसका निर्माण विस्तारित यूक्लिडियन एल्गोरिथम का उपयोग करके किया जा सकता है। [[विस्तारित यूक्लिडियन एल्गोरिथ्म]] कुशलतापूर्वक पूर्णांकों को निर्धारित करता है, इस प्रकार {{math|''R''′}} और {{math|''N''′}} जो बेज़ाउट की पहचान को संतुष्ट करते हैं: | ||
| Line 51: | Line 51: | ||
उदाहरण के लिए, 7 और 15 मॉड्यूल 17 को मोंटगोमरी फॉर्म में फिर से गुणा करने के लिए {{math|1=''R'' = 100}}, उपरोक्तानुसार 12 प्राप्त करने के लिए 3 और 4 के गुणनफल की गणना करें। विस्तारित यूक्लिडियन एल्गोरिथ्म का तात्पर्य है {{math|1=8⋅100 − 47⋅17 = 1}}, इसलिए {{math|1=''R''′ = 8}}. 96 प्राप्त करने के लिए 12 को 8 से गुणा करें और 11 प्राप्त करने के लिए मॉडुलो 17 को कम करें। यह अपेक्षा के अनुरूप 3 का मोंटगोमरी रूप है। | उदाहरण के लिए, 7 और 15 मॉड्यूल 17 को मोंटगोमरी फॉर्म में फिर से गुणा करने के लिए {{math|1=''R'' = 100}}, उपरोक्तानुसार 12 प्राप्त करने के लिए 3 और 4 के गुणनफल की गणना करें। विस्तारित यूक्लिडियन एल्गोरिथ्म का तात्पर्य है {{math|1=8⋅100 − 47⋅17 = 1}}, इसलिए {{math|1=''R''′ = 8}}. 96 प्राप्त करने के लिए 12 को 8 से गुणा करें और 11 प्राप्त करने के लिए मॉडुलो 17 को कम करें। यह अपेक्षा के अनुरूप 3 का मोंटगोमरी रूप है। | ||
== आरईडीसी | == आरईडीसी कलन == | ||
जबकि उपरोक्त | जबकि उपरोक्त कलन सही है, यह गुणा करने की आवश्यकता के कारण मानक प्रतिनिधित्व में गुणा {{math|''R''′}} से कम है, और {{mvar|N}} से विभाजित करते हैं। मोंटगोमरी रिडक्शन, जिसे आरईडीसी के रूप में भी जाना जाता है, एल्गोरिथ्म है जो साथ उत्पाद की गणना {{math|''R''′}} करता है और मॉड्यूलो को कम करता है, {{mvar|N}} विधि की तुलना में अधिक तेज़ी से। पारंपरिक मॉड्यूलर कमी के विपरीत, जो संख्या को इससे छोटा बनाने पर केंद्रित है {{mvar|N}}, मोंटगोमरी कटौती संख्या को और अधिक विभाज्य बनाने पर {{mvar|R}} केंद्रित रहता है, यह छोटे गुणक को {{mvar|N}} द्वारा जोड़कर ऐसा करता है, जिसे अवशेष मोडुलो को रद्द करने के लिए {{mvar|R}} को चुना जाता है, जिससे परिणाम विभाजित करना {{mvar|R}} बहुत कम संख्या देता है। यह संख्या इतनी कम है कि यह लगभग रिडक्शन मॉडुलो है {{mvar|N}}, और कमी मोडुलो की गणना {{mvar|N}} केवल अंतिम सशर्त घटाव की आवश्यकता है। क्योंकि सभी संगणनाओं के संबंध में केवल कमी और विभाजन का उपयोग करके किया जाता है {{mvar|R}}, नहीं {{mvar|N}}, एल्गोरिद्म विभाजन द्वारा सीधी मॉड्यूलर कमी की तुलना में तेज़ी से चलता है। | ||
'''function''' REDC '''is''' | '''function''' REDC '''is''' | ||
'''input:''' Integers ''R'' and ''N'' with gcd(''R'', ''N'') = 1, | '''input:''' Integers ''R'' and ''N'' with gcd(''R'', ''N'') = 1, | ||
| Line 69: | Line 69: | ||
'''end function''' | '''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> | :<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}} पूर्णांक है। दूसरा, आउटपुट या तो {{mvar|t}} या {{math|''t'' − ''N''}} है, दोनों के सर्वांगसम {{math|''t'' mod ''N''}} हैं , तो यह प्रमाणित करने के लिए कि आउटपुट सर्वांगसम {{math|''TR''<sup>−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> | :<math>t \equiv (T + mN)R^{-1} \equiv TR^{-1} + (mR^{-1})N \equiv TR^{-1} \pmod{N}.</math> | ||
इसलिए, आउटपुट में सही अवशेष वर्ग है। तीसरा, {{mvar|m}} में है {{math|[0, ''R'' − 1]}}, और इसलिए {{math|''T'' + ''mN''}} 0 और के बीच {{math|(''RN'' − 1) + (''R'' − 1)''N'' < 2''RN''}} है, इस प्रकार {{mvar|t}} मै रुक जाना {{math|2''N''}}, और क्योंकि यह पूर्णांक है, यह डालता है {{mvar|t}} सीमा में {{math|[0, 2''N'' − 1]}} को इसलिए कम कर रहा है, इस प्रकार {{mvar|t}} वांछित सीमा में अधिकतम घटाव की आवश्यकता होती है, इसलिए एल्गोरिथम का आउटपुट सही सीमा में होता है। | इसलिए, आउटपुट में सही अवशेष वर्ग है। तीसरा, {{mvar|m}} में है {{math|[0, ''R'' − 1]}}, और इसलिए {{math|''T'' + ''mN''}} 0 और के बीच {{math|(''RN'' − 1) + (''R'' − 1)''N'' < 2''RN''}} है, इस प्रकार {{mvar|t}} मै रुक जाना {{math|2''N''}}, और क्योंकि यह पूर्णांक है, यह डालता है {{mvar|t}} सीमा में {{math|[0, 2''N'' − 1]}} को इसलिए कम कर रहा है, इस प्रकार {{mvar|t}} वांछित सीमा में अधिकतम घटाव की आवश्यकता होती है, इसलिए एल्गोरिथम का आउटपुट सही सीमा में होता है। | ||
7 और 15 मॉड्यूल 17 के उत्पाद की गणना करने के लिए आरईडीसी का उपयोग करने के लिए, पहले मोंटगोमेरी फॉर्म में कनवर्ट करें और उपरोक्त के रूप में 12 प्राप्त करने के लिए पूर्णांक के रूप में गुणा करें। इसके बाद आरईडीसी अप्लाई करें {{math|1=''R'' = 100}}, {{math|1=''N'' = 17}}, {{math|1=''N''′ = 47}}, और {{math|1=''T'' = 12}} हैं। इसका पहला कदम {{mvar|m}} को {{math|1=12 ⋅ 47 mod 100 = 64}} पर तय किया जाता है, इसका दूसरा चरण | 7 और 15 मॉड्यूल 17 के उत्पाद की गणना करने के लिए आरईडीसी का उपयोग करने के लिए, पहले मोंटगोमेरी फॉर्म में कनवर्ट करें और उपरोक्त के रूप में 12 प्राप्त करने के लिए पूर्णांक के रूप में गुणा करें। इसके बाद आरईडीसी अप्लाई करें {{math|1=''R'' = 100}}, {{math|1=''N'' = 17}}, {{math|1=''N''′ = 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|7 ⋅ 15 mod 17}} अपितु इसके साथ {{math|1=''R'' = 10}}. विस्तारित यूक्लिडियन एल्गोरिथम का उपयोग करके {{math|1=−5 ⋅ 10 + 3 ⋅ 17 = 1}} की गणना करें, इसलिए {{math|''N''′}} होगा {{math|1=−3 mod 10 = 7}}. 7 और 15 के मोंटगोमरी रूप {{math|1=70 mod 17 = 2}} और {{math|1=150 mod 17 = 14}} हैं। {{mvar|T}} आरईडीसी के लिए उनका उत्पाद 28 इनपुट है, और उसके पश्चात {{math|1=28 < ''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}} सभी मानक | ब्याज मॉड्यूलो के कई संचालन {{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'' > ''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'' > ''N''}}, अधिकांश अन्य अंकगणितीय संक्रियाएँ REDC के संदर्भ में व्यक्त की जा सकती हैं। इस धारणा का तात्पर्य है कि दो प्रतिनिधियों के उत्पाद मॉड {{mvar|N}} मै रुक जाना {{mvar|RN}}, सही आउटपुट उत्पन्न करने के लिए REDC के लिए आवश्यक सटीक परिकल्पना की जाती हैं। विशेष रूप से, का उत्पाद {{math|''aR'' mod ''N''}} और {{math|''bR'' mod ''N''}} है, जिसके लिए {{math|REDC((''aR'' mod ''N'')(''bR'' mod ''N''))}} गुणा और आरईडीसी के संयुक्त संचालन को अधिकांशतः मोंटगोमरी गुणन कहा जाता है। | ||
| Line 87: | Line 87: | ||
मोंटगोमरी रूप में रूपांतरण कंप्यूटिंग द्वारा किया जाता है {{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>−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>−1</sup>(''R''<sup>3</sup> mod ''N''))}}. प्रारंभिक गुणनफल को 1 के मोंटगोमरी निरूपण के लिए प्रारंभ करके, वर्ग करके घातांक का उपयोग करके मॉड्यूलर घातांक किया जा सकता है, अर्थात {{math|''R'' mod ''N''}}, और मोंटगोमरी गुणा द्वारा गुणा और वर्ग चरणों को प्रतिस्थापित करके प्राप्त होता हैं। | ||
इन परिचालनों को करने के लिए कम से कम जानना आवश्यक है {{math|''N''′}} और {{math|''R''<sup>2</sup> mod ''N''}}. कब {{mvar|R}} छोटे धनात्मक पूर्णांक की शक्ति है {{mvar|b}}, {{math|''N''′}} की गणना हेंसल लेम्मा द्वारा की जा सकती है: का व्युत्क्रम {{mvar|N}} मापांक {{mvar|b}} की गणना भोले एल्गोरिथम द्वारा की जाती है (उदाहरण के लिए, if {{math|1=''b'' = 2}} तो व्युत्क्रम 1 है), और हेंसल की लेम्मा का उपयोग बार-बार व्युत्क्रम मॉड्यूल उच्च और उच्च शक्तियों को खोजने के लिए किया जाता है {{mvar|b}}, जब उलटा मोडुलो रुक जाता है {{mvar|R}} ज्ञात है; {{math|''N''′}} इस व्युत्क्रम का निषेध है। स्थिरांक {{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|''N''′}} और {{math|''R''<sup>2</sup> mod ''N''}}. कब {{mvar|R}} छोटे धनात्मक पूर्णांक की शक्ति है {{mvar|b}}, {{math|''N''′}} की गणना हेंसल लेम्मा द्वारा की जा सकती है: का व्युत्क्रम {{mvar|N}} मापांक {{mvar|b}} की गणना भोले एल्गोरिथम द्वारा की जाती है (उदाहरण के लिए, if {{math|1=''b'' = 2}} तो व्युत्क्रम 1 है), और हेंसल की लेम्मा का उपयोग बार-बार व्युत्क्रम मॉड्यूल उच्च और उच्च शक्तियों को खोजने के लिए किया जाता है {{mvar|b}}, जब उलटा मोडुलो रुक जाता है {{mvar|R}} ज्ञात है; {{math|''N''′}} इस व्युत्क्रम का निषेध है। स्थिरांक {{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'' > ''N''}} जिससे कि उत्पादों की गणना करने के लिए आरईडीसी का उपयोग किया जा सके। चूंकि, कब {{mvar|R}} की शक्ति है {{mvar|B}}, REDC का प्रकार है जिसके लिए केवल मशीन शब्द आकार के पूर्णांकों के उत्पादों की आवश्यकता होती है। मान लीजिए कि धनात्मक बहु-परिशुद्धता पूर्णांक थोड़ा एंडियन संग्रहीत हैं, अर्थात, {{mvar|x}} को सरणी के रूप में संग्रहीत किया जाता है {{math|''x''[0], ..., ''x''[ℓ - 1]}} ऐसा है कि {{math|0 ≤ ''x''[''i''] < ''B''}} सभी के लिए {{mvar|i}} और {{math|1=''x'' = ∑ ''x''[''i''] ''B<sup>i</sup>''}}. | REDC एल्गोरिद्म के लिए उत्पाद मॉड्यूल {{mvar|R}} की आवश्यकता होती है, और सामान्यतः {{math|''R'' > ''N''}} जिससे कि उत्पादों की गणना करने के लिए आरईडीसी का उपयोग किया जा सके। चूंकि, कब {{mvar|R}} की शक्ति है {{mvar|B}}, REDC का प्रकार है जिसके लिए केवल मशीन शब्द आकार के पूर्णांकों के उत्पादों की आवश्यकता होती है। मान लीजिए कि धनात्मक बहु-परिशुद्धता पूर्णांक थोड़ा एंडियन संग्रहीत हैं, अर्थात, {{mvar|x}} को सरणी के रूप में संग्रहीत किया जाता है {{math|''x''[0], ..., ''x''[ℓ - 1]}} ऐसा है कि {{math|0 ≤ ''x''[''i''] < ''B''}} सभी के लिए {{mvar|i}} और {{math|1=''x'' = ∑ ''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''' | '''function''' MultiPrecisionREDC '''is''' | ||
| Line 136: | Line 136: | ||
'''end function''' | '''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}}<nowiki> में गणना की गई {{mvar|i}लूप का } वाँ पुनरावृत्ति, फिर एल्गोरिथम समुच्चय करता है जिसके लिए </nowiki>{{mvar|S}} को {{math|''T'' + (∑ ''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'' + (∑ ''m<sub>i</sub> B<sup>i</sup>'')''N''}} द्वारा दर्शाते हैं क्योंकि मल्टी प्रेसिजन REDC और REDC ही आउटपुट का उत्पादन करते हैं, यह योग विकल्प के समान है {{mvar|m}} कि REDC एल्गोरिथम बना देगा। | ||
| Line 142: | Line 142: | ||
का अंतिम शब्द {{mvar|T}}, {{math|''T''[''r'' + ''p'']}} (और इसके परिणामस्वरूप {{math|''S''[''p'']}}), का उपयोग केवल कैरी रखने के लिए किया जाता है, क्योंकि प्रारंभिक कमी का परिणाम की सीमा में परिणाम के लिए बाध्य होता है {{math|0 ≤ ''S'' < ''2N''}}. इससे यह निष्कर्ष निकलता है कि इस अतिरिक्त कैरी शब्द से पूरी तरह बचा जा सकता है यदि यह पहले से ज्ञात हो {{math|''R'' ≥ ''2N''}} जिसका विशिष्ट बाइनरी कार्यान्वयन पर, यह कहने के बराबर है कि यदि बिट्स की संख्या हो तो इस कैरी शब्द से बचा जा सकता है {{mvar|N}} बिट्स की संख्या से छोटा है {{mvar|R}}. अन्यथा, वहन या तो शून्य या होगा। प्रोसेसर के आधार पर, इस शब्द को पूर्ण आकार के शब्द के अतिरिक्त कैरी फ़्लैग के रूप में संग्रहीत करना संभव हो सकता है। | का अंतिम शब्द {{mvar|T}}, {{math|''T''[''r'' + ''p'']}} (और इसके परिणामस्वरूप {{math|''S''[''p'']}}), का उपयोग केवल कैरी रखने के लिए किया जाता है, क्योंकि प्रारंभिक कमी का परिणाम की सीमा में परिणाम के लिए बाध्य होता है {{math|0 ≤ ''S'' < ''2N''}}. इससे यह निष्कर्ष निकलता है कि इस अतिरिक्त कैरी शब्द से पूरी तरह बचा जा सकता है यदि यह पहले से ज्ञात हो {{math|''R'' ≥ ''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> | मल्टीप्रिसिजन गुणन और आरईडीसी को एल्गोरिथम में जोड़ना संभव है। इस संयुक्त एल्गोरिथ्म को सामान्यतः मोंटगोमरी गुणन कहा जाता है। 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=−299 ⋅ 10 + 3 ⋅ 997 = 1}}, इसलिए {{math|''N''′}} 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=−299 ⋅ 10 + 3 ⋅ 997 = 1}}, इसलिए {{math|''N''′}} 7 होगा। | ||
| Line 182: | Line 182: | ||
4 0007401 0 | 4 0007401 0 | ||
इसलिए, अंतिम तुलना और घटाव से पहले, {{math|1=''S'' = 1047}}. अंतिम घटाव संख्या 50 देता है। मोंटगोमरी के प्रतिनिधित्व के | इसलिए, अंतिम तुलना और घटाव से पहले, {{math|1=''S'' = 1047}}. अंतिम घटाव संख्या 50 देता है। मोंटगोमरी के प्रतिनिधित्व के पश्चात {{math|1=314 ⋅ 271 mod 997 = 349}} है {{math|1=349000 mod 997 = 50}}, यह अपेक्षित परिणाम है। | ||
बेस 2 में कार्य करते समय, सही का निर्धारण करना {{mvar|m}} प्रत्येक चरण में विशेष रूप से | बेस 2 में कार्य करते समय, सही का निर्धारण करना {{mvar|m}} प्रत्येक चरण में विशेष रूप से सरल है: यदि वर्तमान कार्यकाजी बिट सम है, तो {{mvar|m}} शून्य है और यदि यह विषम है, तो {{mvar|m}} है। इसके अतिरिक्त, क्योंकि मल्टी प्रेसिजन REDC के प्रत्येक चरण को केवल सबसे कम बिट जानने की आवश्यकता होती है, मॉन्टगोमरी गुणन को [[कैरी-सेव योजक]] के साथ सरलता से जोड़ा जा सकता है। | ||
== साइड-चैनल अटैक == | == साइड-चैनल अटैक == | ||
| Line 195: | Line 195: | ||
|date=29 November 2010 |location=Tokyo | |date=29 November 2010 |location=Tokyo | ||
|conference-url=https://www.nics.uma.es/pub/seciot10/ | |conference-url=https://www.nics.uma.es/pub/seciot10/ | ||
}} ([https://www.nics.uma.es/pub/seciot10/files/ppt/liu_seciot10.pdf Presentation slides].)</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> | ||
== यह भी देखें == | == यह भी देखें == | ||
* बैरेट कमी | * बैरेट कमी | ||
Revision as of 07:47, 23 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/NZ में N अवशेषों वाले वर्ग मॉड्यूल सम्मिलित रहते हैं , अर्ताथ इसके तत्व फॉर्म के समुच्चय हैं, जो इस प्रकार हैं-
जहाँ a पूर्णांकों के बीच है। प्रत्येक अवशेष वर्ग पूर्णांकों का समूह है जैसे कि समुच्चय में किसी भी दो पूर्णांकों का अंतर विभाज्य N है और अवशेष वर्ग उस संपत्ति के संबंध में अधिकतम है; पूर्णांकों को अवशेष वर्ग से बाहर नहीं छोड़ा जाता है जब तक कि वे विभाज्यता की स्थिति का उल्लंघन नहीं करते हैं। इस प्रकार अवशेष वर्ग के अनुरूप a तथा a द्वारा अंकित किया जाता है, इस प्रकार अवशेष वर्गों की समानता को सर्वांगसमता कहा जाता है और इसे इस प्रकार निरूपित किया जाता है।
कंप्यूटर पर संपूर्ण अवशेष वर्ग को संग्रहीत करना असंभव है क्योंकि अवशेष वर्ग में असीम रूप से कई तत्व होते हैं। इसके अतिरिक्त अवशेष वर्गों को प्रतिनिधि के रूप में संग्रहीत किया जाता है। परंपरागत रूप से, ये प्रतिनिधि पूर्णांक होते हैं, जहाँ पर 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, N2 − 2N + 1] में है। मध्यवर्ती पूर्णांक उत्पाद का भंडारण ab को या तो दोगुने बिट्स की आवश्यकता होती है इस प्रकार a या b, और कुशलता से प्रतिनिधि का निर्धारण [0, N − 1] विभाजन की आवश्यकता है। गणितीय रूप से, 0 और के बीच का पूर्णांक N − 1 के अनुरूप है ab को यूक्लिडियन डिवीजन प्रमेय के कथन को लागू करके व्यक्त किया जा सकता है:
जहाँ q भागफल है और r, शेष, अंतराल में है [0, N − 1]. शेष r है, इस कारण ab mod N के निर्धारण r कंप्यूटिंग द्वारा किया जा सकता है q, फिर घटाना qN से ab. उदाहरण के लिए, फिर से , उत्पाद 7 ⋅ 15 कंप्यूटिंग द्वारा पर इसका निर्धारण किया जाता है, इसे विभाजित करना , और घटाना सरल हो जाता हैं।
क्योंकि की गणना 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 का रूप हैं।
मोंटगोमरी रूप में जोड़ और घटाव वितरण नियम के कारण सामान्य मॉड्यूलर जोड़ और घटाव के समान हैं:
यह इस तथ्य का परिणाम है कि, क्योंकि gcd(R, N) = 1, गुणा करके R योज्य समूह पर समरूपता Z/NZ है, उदाहरण के लिए, (7 + 15) mod 17 = 5, जो मोंटगोमरी रूप (3 + 4) mod 17 = 7 में बन जाता है।
मॉन्टगोमरी रूप में गुणन, चूंकि, अधिक जटिल प्रतीत होता है। का सामान्य उत्पाद aR और bR के उत्पाद का प्रतिनिधित्व नहीं करता है, इस प्रकार a और b क्योंकि इसका अतिरिक्त कारक R है :
मोंटगोमरी रूप में कंप्यूटिंग उत्पादों के अतिरिक्त कारक को 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, को इस प्रकार प्राप्त करते हैं।
पूर्णांक R′ इस धारणा के कारण सम्मिलित है कि R और N को-प्राइम हैं। इसका निर्माण विस्तारित यूक्लिडियन एल्गोरिथम का उपयोग करके किया जा सकता है। विस्तारित यूक्लिडियन एल्गोरिथ्म कुशलतापूर्वक पूर्णांकों को निर्धारित करता है, इस प्रकार R′ और N′ जो बेज़ाउट की पहचान को संतुष्ट करते हैं:
0 < R′ < N, 0 < N′ < R, और:
इससे पता चलता है कि मोंटगोमरी रूप में गुणा करना संभव है। मोंटगोमरी रूप में संख्याओं को गुणा करने के लिए सीधा एल्गोरिथम इसलिए गुणा करना है, इस प्रकार 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, एल्गोरिद्म विभाजन द्वारा सीधी मॉड्यूलर कमी की तुलना में तेज़ी से चलता है।
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−1 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 पूर्णांक है। दूसरा, आउटपुट या तो t या t − N है, दोनों के सर्वांगसम t mod N हैं , तो यह प्रमाणित करने के लिए कि आउटपुट सर्वांगसम TR−1 mod N है , यह प्रमाणित करने के लिए पर्याप्त है t है। सापेक्ष N, t संतुष्ट करता है:
इसलिए, आउटपुट में सही अवशेष वर्ग है। तीसरा, 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 हैं। T आरईडीसी के लिए उनका उत्पाद 28 इनपुट है, और उसके पश्चात 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 सभी मानक कलन के साथ किया जा सकता है। जैकोबी प्रतीक की गणना इस प्रकार की जा सकती है जब तक कि रखा है।
कब R > N, अधिकांश अन्य अंकगणितीय संक्रियाएँ REDC के संदर्भ में व्यक्त की जा सकती हैं। इस धारणा का तात्पर्य है कि दो प्रतिनिधियों के उत्पाद मॉड N मै रुक जाना RN, सही आउटपुट उत्पन्न करने के लिए REDC के लिए आवश्यक सटीक परिकल्पना की जाती हैं। विशेष रूप से, का उत्पाद aR mod N और bR mod N है, जिसके लिए REDC((aR mod N)(bR mod N)) गुणा और आरईडीसी के संयुक्त संचालन को अधिकांशतः मोंटगोमरी गुणन कहा जाता है।
मोंटगोमरी रूप में रूपांतरण कंप्यूटिंग द्वारा किया जाता है REDC((a mod N)(R2 mod N)). कंप्यूटिंग द्वारा मोंटगोमरी फॉर्म से रूपांतरण किया जाता है REDC(aR mod N). का मॉड्यूलर व्युत्क्रम aR mod N है REDC((aR mod N)−1(R3 mod N)). प्रारंभिक गुणनफल को 1 के मोंटगोमरी निरूपण के लिए प्रारंभ करके, वर्ग करके घातांक का उपयोग करके मॉड्यूलर घातांक किया जा सकता है, अर्थात R mod N, और मोंटगोमरी गुणा द्वारा गुणा और वर्ग चरणों को प्रतिस्थापित करके प्राप्त होता हैं।
इन परिचालनों को करने के लिए कम से कम जानना आवश्यक है N′ और R2 mod N. कब R छोटे धनात्मक पूर्णांक की शक्ति है b, N′ की गणना हेंसल लेम्मा द्वारा की जा सकती है: का व्युत्क्रम N मापांक b की गणना भोले एल्गोरिथम द्वारा की जाती है (उदाहरण के लिए, if b = 2 तो व्युत्क्रम 1 है), और हेंसल की लेम्मा का उपयोग बार-बार व्युत्क्रम मॉड्यूल उच्च और उच्च शक्तियों को खोजने के लिए किया जाता है b, जब उलटा मोडुलो रुक जाता है R ज्ञात है; N′ इस व्युत्क्रम का निषेध है। स्थिरांक R mod N और R3 mod N के रूप में तथा REDC(R2 mod N) और के रूप में उत्पन्न किया जा सकता है। REDC((R2 mod N)(R2 mod N)) मौलिक ऑपरेशन किसी उत्पाद के आरईडीसी की गणना करना है। जब स्टैंडअलोन आरईडीसी की आवश्यकता होती है, तो इसकी गणना किसी उत्पाद के आरईडीसी के रूप 1 mod N में की जा सकती है, इसका एकमात्र स्थान जहां प्रत्यक्ष कमी N मोडुल है आवश्यक है कि इसका पूर्वगणना R2 mod N में रखा जाता है।
मल्टीप्रिसिजन पूर्णांकों पर मोंटगोमरी अंकगणित
अधिकांश क्रिप्टोग्राफ़िक अनुप्रयोगों के लिए संख्याओं की आवश्यकता होती है जो सैकड़ों या हजारों बिट्स लंबी होती हैं। ऐसी संख्याएँ मशीन शब्द में संग्रहीत करने के लिए बहुत बड़ी हैं। सामान्यतः, हार्डवेयर गुणन मॉड को कुछ आधार करता है B, इसलिए बड़े गुणा करने के लिए कई छोटे गुणाओं के संयोजन की आवश्यकता होती है। आधार B सामान्यतः माइक्रोइलेक्ट्रॉनिक अनुप्रयोगों के लिए 2 होता है, 28 8-बिट फ़र्मवेयर के लिए,[4]या 232 या 264 सॉफ्टवेयर अनुप्रयोगों के लिए करते हैं।
REDC एल्गोरिद्म के लिए उत्पाद मॉड्यूल R की आवश्यकता होती है, और सामान्यतः R > N जिससे कि उत्पादों की गणना करने के लिए आरईडीसी का उपयोग किया जा सके। चूंकि, कब R की शक्ति है B, REDC का प्रकार है जिसके लिए केवल मशीन शब्द आकार के पूर्णांकों के उत्पादों की आवश्यकता होती है। मान लीजिए कि धनात्मक बहु-परिशुद्धता पूर्णांक थोड़ा एंडियन संग्रहीत हैं, अर्थात, x को सरणी के रूप में संग्रहीत किया जाता है x[0], ..., x[ℓ - 1] ऐसा है कि 0 ≤ x[i] < B सभी के लिए i और x = ∑ x[i] Bi. कलन बहु-परिशुद्धता पूर्णांक से शुरू होता है T और इसे बार में शब्द कम कर देता है। पहले का उपयुक्त गुणक N बनाने के लिए T द्वारा विभाज्य B जोड़ा जाता है, फिर का गुणक N बनाने के लिए जोड़ा जाता है T द्वारा विभाज्य B2, और इसी प्रकार अंततः 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 = Br, --thus, r = logB 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−1 ≡ 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 Bi+1
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. तब mNBi जोड़ा जाता है T. क्योंकि यह मात्रा जीरो मॉड है N, इसे जोड़ने से का मान T mod N प्रभावित नहीं होता है। इस प्रकार यदि mi के मान को दर्शाता है m में गणना की गई {{mvar|i}लूप का } वाँ पुनरावृत्ति, फिर एल्गोरिथम समुच्चय करता है जिसके लिए S को T + (∑ mi Bi)N द्वारा दर्शाते हैं क्योंकि मल्टी प्रेसिजन REDC और REDC ही आउटपुट का उत्पादन करते हैं, यह योग विकल्प के समान है m कि REDC एल्गोरिथम बना देगा।
का अंतिम शब्द T, T[r + p] (और इसके परिणामस्वरूप S[p]), का उपयोग केवल कैरी रखने के लिए किया जाता है, क्योंकि प्रारंभिक कमी का परिणाम की सीमा में परिणाम के लिए बाध्य होता है 0 ≤ S < 2N. इससे यह निष्कर्ष निकलता है कि इस अतिरिक्त कैरी शब्द से पूरी तरह बचा जा सकता है यदि यह पहले से ज्ञात हो R ≥ 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 ⋅ 813 = 765846 मान प्राप्त होता हैं। इसका प्रारंभिक इनपुट T से मल्टी प्रेसिजन REDC होगा [6, 4, 8, 5, 6, 7]। जो नंबर N को [7, 9, 9] के रूप में दर्शाया जाता हैं। विस्तारित यूक्लिडियन एल्गोरिथ्म कहता है कि −299 ⋅ 10 + 3 ⋅ 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 ⋅ 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)
