बैरेट रिडक्शन: Difference between revisions
No edit summary |
No edit summary |
||
Line 32: | Line 32: | ||
== सामान्य विचार == | == सामान्य विचार == | ||
हम | हम फलन कहते हैं <math>\left[ \, \right]: \mathbb{R} \to \mathbb{Z}</math> पूर्णांक सन्निकटन। यदि <math>|\left[z\right] - z| \leq 1</math>. | ||
हम परिभाषित करते हैं <math>\text{mod}^{\left[\,\right]} \, n: \mathbb{Z} \to (\mathbb{Z}/n\mathbb{Z}) </math> जैसा | इस प्रकार मापांक <math>n</math> के लिए और एक पूर्णांक सन्निकटन <math>\left[\,\right]</math>, | ||
हम परिभाषित करते हैं- <math>\text{mod}^{\left[\,\right]} \, n: \mathbb{Z} \to (\mathbb{Z}/n\mathbb{Z}) </math> जैसा | |||
:<math> a \, \text{mod}^{\left[\,\right]} \, n = a - \left[a / n\right] n </math>. | :<math> a \, \text{mod}^{\left[\,\right]} \, n = a - \left[a / n\right] n </math>. | ||
के सामान्य विकल्प <math>\left[\,\right]</math> [[फर्श समारोह]], [[छत समारोह]] और [[ गोलाई ]] | के सामान्य विकल्प <math>\left[\,\right]</math> [[फर्श समारोह|फ्लोर]], [[छत समारोह|छत]] और[[ गोलाई | गोलाई]] फलन हैं। | ||
सामान्यतः बैरेट रिडक्शन दो पूर्णांक सन्निकटन <math>\left[\,\right]_0, \left[\,\right]_1</math> निर्दिष्ट करके प्रारम्भ होता है और यथोचित <math>ab \, \bmod \, n</math> निकट सन्निकटन की गणना करता है। जैसा | |||
:<math> a b - \left[ \frac{a \, \left[ \frac{b R}{n} \right]_0 }{R} \right]_1 n</math>. | :<math> a b - \left[ \frac{a \, \left[ \frac{b R}{n} \right]_0 }{R} \right]_1 n</math>. | ||
स्थिति <math>b = 1</math> पी.डी. द्वारा प्रस्तुत किया गया था। बैरेट<ref name="Barrett1986" /> फ़्लोर फलन स्थिति के लिए <math>\left[\,\right]_0 = \left[\,\right]_1 = \lfloor \, \rfloor</math>. सामान्य स्थिति <math>b</math> के लिए [[संख्या सिद्धांत पुस्तकालय]] में पाया गया था।<ref name="ShoupNTL" /> पूर्णांक सन्निकटन दृश्य और [[मोंटगोमरी गुणन]] और बैरेट गुणन के बीच पत्राचार की खोज हनो बेकर, विंसेंट ह्वांग, मैथियास जे. कन्नविशर, बो-यिन यांग और शांग-यी यांग द्वारा की गई थी।<ref name="NeonNTT2022" /> | |||
== एकल-शब्द बैरेट रिडक्शन == | |||
जब मान मशीनी शब्दों में फिट होते हैं। तो बैरेट ने प्रारम्भ में उपरोक्त एल्गोरिदम के पूर्णांक संस्करण पर विचार किया। | |||
हम फ़्लोर-फलन केस के विचार का वर्णन करते हैं। | |||
हम फ़्लोर- | |||
गणना करते समय <math>a \,\bmod\, n</math> अहस्ताक्षरित पूर्णांकों के लिए | गणना करते समय <math>a \,\bmod\, n</math> अहस्ताक्षरित पूर्णांकों के लिए स्पष्ट एनालॉग <math>n</math> के लिए विभाजन का उपयोग करना होगा : | ||
<syntaxhighlight lang="go"> | <syntaxhighlight lang="go"> | ||
Line 60: | Line 63: | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
चूंकि विभाजन का मूल्य अधिक हो सकता है और क्रिप्टोग्राफ़िक सेटिंग्स में कुछ सीपीयू पर निरंतर-समय निर्देश नहीं हो सकता है। जो ऑपरेशन को [[ समय पर हमला |समय पर आक्रमण]] के अधीन करता है। इस प्रकार बैरेट रिडक्शन <math>1/n</math> मूल्य के साथ <math>m/2^k</math> अनुमानित है क्योंकि विभाजन द्वारा <math>2^k</math> यह केवल राइट-शिफ्ट है और इसलिए यह अधिक मूल्यवान नहीं है। | |||
के लिए सर्वोत्तम मूल्य की गणना करने के लिए <math>m</math> दिया गया <math>2^k</math> विचार करना: | के लिए सर्वोत्तम मूल्य की गणना करने के लिए <math>m</math> दिया गया <math>2^k</math> विचार करना: | ||
Line 68: | Line 71: | ||
निकटतम पूर्णांक तक पूर्णांकित करने से सर्वोत्तम सन्निकटन मिलेगा, लेकिन इसका परिणाम हो सकता है <math>m/2^k</math> से बड़ा होना <math>1/n</math>, जो अंडरफ्लो का कारण बन सकता है। इस प्रकार <math>m = \lfloor {2^k}/{n} \rfloor</math> अहस्ताक्षरित अंकगणित के लिए उपयोग किया जाता है। | निकटतम पूर्णांक तक पूर्णांकित करने से सर्वोत्तम सन्निकटन मिलेगा, लेकिन इसका परिणाम हो सकता है <math>m/2^k</math> से बड़ा होना <math>1/n</math>, जो अंडरफ्लो का कारण बन सकता है। इस प्रकार <math>m = \lfloor {2^k}/{n} \rfloor</math> अहस्ताक्षरित अंकगणित के लिए उपयोग किया जाता है। | ||
इस प्रकार हम निम्नलिखित के साथ उपरोक्त | इस प्रकार हम निम्नलिखित के साथ उपरोक्त फलन का अनुमान लगा सकते हैं: | ||
<syntaxhighlight lang="go"> | <syntaxhighlight lang="go"> | ||
Line 76: | Line 79: | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
चूंकि, जब से <math>m/2^k \le 1/n</math>, का मान है <code>q</code> उस फलन में अंत में एक बहुत छोटा हो सकता है, और इस प्रकार <code>a</code> केवल भीतर होने की गारंटी है <math>[0, 2n)</math> इसके बजाय <math>[0, n)</math> जैसा कि आम तौर पर आवश्यक है. एक सशर्त घटाव इसे ठीक करेगा: | |||
<syntaxhighlight lang="go"> | <syntaxhighlight lang="go"> | ||
Line 157: | Line 160: | ||
अन्य प्रकार के पूर्णांक सन्निकटन कार्यों के लिए भी समान सीमाएँ लागू होती हैं। | अन्य प्रकार के पूर्णांक सन्निकटन कार्यों के लिए भी समान सीमाएँ लागू होती हैं। | ||
उदाहरण के लिए, यदि हम चुनते हैं <math>\left[\,\right]_0 = \left[\,\right]_1 = \left\lfloor\,\right\rceil</math>, [[गोलाई समारोह]] | उदाहरण के लिए, यदि हम चुनते हैं <math>\left[\,\right]_0 = \left[\,\right]_1 = \left\lfloor\,\right\rceil</math>, [[गोलाई समारोह]] फलन, | ||
तो हमारे पास हैं | तो हमारे पास हैं | ||
:<math> | :<math> | ||
Line 173: | Line 176: | ||
== बहु-शब्द बैरेट | == बहु-शब्द बैरेट रिडक्शन == | ||
कटौती पर विचार करने के लिए बैरेट की प्राथमिक प्रेरणा [[आरएसए (क्रिप्टोसिस्टम)]] का कार्यान्वयन था, जहां प्रश्न में मूल्य लगभग निश्चित रूप से एक मशीन शब्द के आकार से अधिक होगा। इस स्थिति में, बैरेट ने एक एल्गोरिदम प्रदान किया जो उपरोक्त एकल-शब्द संस्करण का अनुमान लगाता है लेकिन बहु-शब्द मानों के लिए। विवरण के लिए एप्लाइड क्रिप्टोग्राफी की हैंडबुक का खंड 14.3.3 देखें।<ref>{{cite book | first1 = Alfred | last1 = Menezes | first2 = Paul | last2 = Oorschot | first3 = Scott | last3 = Vanstone | title = एप्लाइड क्रिप्टोग्राफी की हैंडबुक| year = 1997 | isbn = 0-8493-8523-7 | url = https://archive.org/details/handbookofapplie0000mene | url-access = registration }}</ref> | कटौती पर विचार करने के लिए बैरेट की प्राथमिक प्रेरणा [[आरएसए (क्रिप्टोसिस्टम)]] का कार्यान्वयन था, जहां प्रश्न में मूल्य लगभग निश्चित रूप से एक मशीन शब्द के आकार से अधिक होगा। इस स्थिति में, बैरेट ने एक एल्गोरिदम प्रदान किया जो उपरोक्त एकल-शब्द संस्करण का अनुमान लगाता है लेकिन बहु-शब्द मानों के लिए। विवरण के लिए एप्लाइड क्रिप्टोग्राफी की हैंडबुक का खंड 14.3.3 देखें।<ref>{{cite book | first1 = Alfred | last1 = Menezes | first2 = Paul | last2 = Oorschot | first3 = Scott | last3 = Vanstone | title = एप्लाइड क्रिप्टोग्राफी की हैंडबुक| year = 1997 | isbn = 0-8493-8523-7 | url = https://archive.org/details/handbookofapplie0000mene | url-access = registration }}</ref> |
Revision as of 02:14, 8 August 2023
मॉड्यूलर अंकगणित में बैरेट रिडक्शन 1986 में पी.डी. द्वारा प्रारम्भ किया गया एक रिडक्शन कलन विधि है। बैरेट[1] कंप्यूटिंग का सरल उपाय
इस प्रकार यह तेज़ विभाजन एल्गोरिथ्म का उपयोग करना होगा। बैरेट रिडक्शन एल्गोरिदम है। जिसे इस ऑपरेशन को अनुकूलित करने के लिए डिज़ाइन किया गया है, इसमे स्थिर है और भाग को गुणन से प्रतिस्थापित करना है।
ऐतिहासिक रूप से वैल्यू के लिए , बैरेट रिडक्शन को संचालित करके सम्पूर्ण प्रोडक्ट ab की गणना की गई। हाल ही में यह दिखाया गया कि यदि हम किसी ऑपरेंड पर पूर्वगणना कर सकते हैं। तो पूर्ण उत्पाद अनावश्यक होता है।[2][3]
सामान्य विचार
हम फलन कहते हैं पूर्णांक सन्निकटन। यदि .
इस प्रकार मापांक के लिए और एक पूर्णांक सन्निकटन ,
हम परिभाषित करते हैं- जैसा
- .
के सामान्य विकल्प फ्लोर, छत और गोलाई फलन हैं।
सामान्यतः बैरेट रिडक्शन दो पूर्णांक सन्निकटन निर्दिष्ट करके प्रारम्भ होता है और यथोचित निकट सन्निकटन की गणना करता है। जैसा
- .
स्थिति पी.डी. द्वारा प्रस्तुत किया गया था। बैरेट[1] फ़्लोर फलन स्थिति के लिए . सामान्य स्थिति के लिए संख्या सिद्धांत पुस्तकालय में पाया गया था।[2] पूर्णांक सन्निकटन दृश्य और मोंटगोमरी गुणन और बैरेट गुणन के बीच पत्राचार की खोज हनो बेकर, विंसेंट ह्वांग, मैथियास जे. कन्नविशर, बो-यिन यांग और शांग-यी यांग द्वारा की गई थी।[3]
एकल-शब्द बैरेट रिडक्शन
जब मान मशीनी शब्दों में फिट होते हैं। तो बैरेट ने प्रारम्भ में उपरोक्त एल्गोरिदम के पूर्णांक संस्करण पर विचार किया।
हम फ़्लोर-फलन केस के विचार का वर्णन करते हैं।
गणना करते समय अहस्ताक्षरित पूर्णांकों के लिए स्पष्ट एनालॉग के लिए विभाजन का उपयोग करना होगा :
func reduce(a uint) uint {
q:= a / n // Division implicitly returns the floor of the result.
return a - q * n
}
चूंकि विभाजन का मूल्य अधिक हो सकता है और क्रिप्टोग्राफ़िक सेटिंग्स में कुछ सीपीयू पर निरंतर-समय निर्देश नहीं हो सकता है। जो ऑपरेशन को समय पर आक्रमण के अधीन करता है। इस प्रकार बैरेट रिडक्शन मूल्य के साथ अनुमानित है क्योंकि विभाजन द्वारा यह केवल राइट-शिफ्ट है और इसलिए यह अधिक मूल्यवान नहीं है।
के लिए सर्वोत्तम मूल्य की गणना करने के लिए दिया गया विचार करना:
के लिए पूर्णांक होने के लिए, हमें पूर्णांक बनाना होगा किसी तरह। निकटतम पूर्णांक तक पूर्णांकित करने से सर्वोत्तम सन्निकटन मिलेगा, लेकिन इसका परिणाम हो सकता है से बड़ा होना , जो अंडरफ्लो का कारण बन सकता है। इस प्रकार अहस्ताक्षरित अंकगणित के लिए उपयोग किया जाता है।
इस प्रकार हम निम्नलिखित के साथ उपरोक्त फलन का अनुमान लगा सकते हैं:
func reduce(a uint) uint {
q := (a * m) >> k // ">> k" denotes bitshift by k.
return a - q * n
}
चूंकि, जब से , का मान है q
उस फलन में अंत में एक बहुत छोटा हो सकता है, और इस प्रकार a
केवल भीतर होने की गारंटी है इसके बजाय जैसा कि आम तौर पर आवश्यक है. एक सशर्त घटाव इसे ठीक करेगा:
func reduce(a uint) uint {
q := (a * m) >> k
a -= q * n
if a >= n {
a -= n
}
return a
}
एकल-शब्द बैरेट गुणन
कल्पना करना पूर्व से ज्ञात है. यह हमें पूर्व-गणना करने की अनुमति देता है तक पहुँचने से पहले . बैरेट गुणन गणना , के उच्च भाग का अनुमान लगाता है साथ
,
और सन्निकटन को घटा देता है। तब से
का गुणज है ,
परिणामी मूल्य
का प्रतिनिधि है .
बैरेट और मोंटगोमरी गुणन के बीच पत्राचार
याद रखें कि अहस्ताक्षरित मोंटगोमरी गुणन एक प्रतिनिधि की गणना करता है जैसा
- .
वास्तव में, यह मान बराबर है .
हम दावे को इस प्रकार साबित करते हैं।
आम तौर पर, पूर्णांक सन्निकटन के लिए , अपने पास
- .[3]
बैरेट गुणन की सीमा
हमने आउटपुट को इससे बांध दिया है .
अन्य प्रकार के पूर्णांक सन्निकटन कार्यों के लिए भी समान सीमाएँ लागू होती हैं। उदाहरण के लिए, यदि हम चुनते हैं , गोलाई समारोह फलन, तो हमारे पास हैं
बहु-शब्द बैरेट रिडक्शन
कटौती पर विचार करने के लिए बैरेट की प्राथमिक प्रेरणा आरएसए (क्रिप्टोसिस्टम) का कार्यान्वयन था, जहां प्रश्न में मूल्य लगभग निश्चित रूप से एक मशीन शब्द के आकार से अधिक होगा। इस स्थिति में, बैरेट ने एक एल्गोरिदम प्रदान किया जो उपरोक्त एकल-शब्द संस्करण का अनुमान लगाता है लेकिन बहु-शब्द मानों के लिए। विवरण के लिए एप्लाइड क्रिप्टोग्राफी की हैंडबुक का खंड 14.3.3 देखें।[4]
बहुपदों के लिए बैरेट एल्गोरिथ्म
बहुपदों को उलट कर और एक्स-एडिक अंकगणित का उपयोग करके, बहुपद विभाजन के लिए बैरेट एल्गोरिथ्म का उपयोग करना भी संभव है।[5]
यह भी देखें
- मोंटगोमरी कमी एक और समान एल्गोरिदम है।
संदर्भ
- ↑ 1.0 1.1 Barrett, P. (1986). "Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor". Advances in Cryptology – CRYPTO' 86. Lecture Notes in Computer Science. Vol. 263. pp. 311–323. doi:10.1007/3-540-47721-7_24. ISBN 978-3-540-18047-0.
- ↑ 2.0 2.1 Shoup, Victor. "Number Theory Library".
- ↑ 3.0 3.1 3.2 Becker, Hanno; Hwang, Vincent; Kannwischer, Matthias J.; Yang, Bo-Yin; Yang, Shang-Yi, "Neon NTT: Faster Dilithium, Kyber, and Saber on Cortex-A72 and Apple M1", Transactions on Cryptographic Hardware and Embedded Systems, 2022 (1): 221–244
- ↑ Menezes, Alfred; Oorschot, Paul; Vanstone, Scott (1997). एप्लाइड क्रिप्टोग्राफी की हैंडबुक. ISBN 0-8493-8523-7.
- ↑ "बहुपदों के लिए बैरेट न्यूनीकरण". www.corsix.org. Retrieved 2022-09-07.
स्रोत
- Bosselaers, A.; Govaerts, R.; Vandewalle, J. (1993). "Comparison of Three Modular Reduction Functions". In Stinson, Douglas R. (ed.). क्रिप्टोलॉजी में प्रगति - क्रिप्टो'93. Lecture Notes in Computer Science. Vol. 773. Springer. pp. 175–186. CiteSeerX 10.1.1.40.3779. ISBN 3540483292.
- Hasenplaugh, W.; Gaubatz, G.; Gopal, V. (2007). "Fast Modular Reduction" (PDF). कंप्यूटर अंकगणित पर 18वीं आईईईई संगोष्ठी (ARITH'07). pp. 225–229. doi:10.1109/ARITH.2007.18. ISBN 978-0-7695-2854-0. S2CID 14801112.
श्रेणी:कंप्यूटर अंकगणित श्रेणी:मॉड्यूलर अंकगणित