बैरेट रिडक्शन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(11 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[मॉड्यूलर अंकगणित]] में '''बैरेट रिडक्शन''' 1986 में पी.डी. द्वारा प्रारम्भ किया गया एक रिडक्शन [[कलन विधि]] है। बैरेट<ref name = Barrett1986>
[[मॉड्यूलर अंकगणित]] में '''बैरेट रिडक्शन''' 1986 में पी.डी. द्वारा प्रारम्भ किया गया रिडक्शन [[विभाजन एल्गोरिथ्म|एल्गोरिथ्म]] है। बैरेट<ref name = Barrett1986>
{{Cite book | last1 = Barrett | first1 = P. | chapter = Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor | doi = 10.1007/3-540-47721-7_24 | title = Advances in Cryptology – CRYPTO' 86 | series = Lecture Notes in Computer Science | volume = 263 | pages = 311–323 | year = 1986 | isbn = 978-3-540-18047-0 }}
{{Cite book | last1 = Barrett | first1 = P. | chapter = Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor | doi = 10.1007/3-540-47721-7_24 | title = Advances in Cryptology – CRYPTO' 86 | series = Lecture Notes in Computer Science | volume = 263 | pages = 311–323 | year = 1986 | isbn = 978-3-540-18047-0 }}
</ref> कंप्यूटिंग का सरल उपाय
</ref> कंप्यूटिंग का सरल उपाय


:<math>c = a \,\bmod\, n \, </math>
:<math>c = a \,\bmod\, n \, </math>
इस प्रकार यह तेज़ [[विभाजन एल्गोरिथ्म]] का उपयोग करना होगा। बैरेट रिडक्शन एल्गोरिदम है। जिसे इस ऑपरेशन को अनुकूलित करने के लिए डिज़ाइन किया गया है, इसमे <math>n</math> स्थिर है और <math>a<n^2</math> भाग को गुणन से प्रतिस्थापित करना है।
इस प्रकार यह तेज़ [[विभाजन एल्गोरिथ्म]] का उपयोग करना होगा। बैरेट रिडक्शन एल्गोरिदम है। जिसे इस ऑपरेशन को अनुकूलित करने के लिए डिज़ाइन किया गया है। इसमे <math>n</math> स्थिर है और <math>a<n^2</math> भाग को गुणन से प्रतिस्थापित करना है।


ऐतिहासिक रूप से वैल्यू के लिए <math>a, b < n</math>, बैरेट रिडक्शन <math>a b \, \bmod\, n \, </math> को संचालित करके सम्पूर्ण प्रोडक्ट ab की गणना की गई। हाल ही में यह दिखाया गया कि यदि हम किसी ऑपरेंड पर पूर्वगणना कर सकते हैं। तो पूर्ण उत्पाद अनावश्यक होता है।<ref name="ShoupNTL">
ऐतिहासिक रूप से वैल्यू के लिए <math>a, b < n</math>, बैरेट रिडक्शन <math>a b \, \bmod\, n \, </math> को संचालित करके सम्पूर्ण प्रोडक्ट ab की गणना की गई। वर्तमान में यह प्रदर्शित किया गया है कि यदि हम किसी ऑपरेंड पर पूर्वगणना कर सकते हैं। जिससे पूर्ण उत्पाद अनावश्यक होता है।<ref name="ShoupNTL">
{{cite web
{{cite web
| last = Shoup | first = Victor
| last = Shoup | first = Victor
Line 32: Line 32:
== सामान्य विचार ==
== सामान्य विचार ==


हम फलन कहते हैं <math>\left[ \, \right]: \mathbb{R} \to \mathbb{Z}</math> पूर्णांक सन्निकटन। यदि <math>|\left[z\right] - z| \leq 1</math>.
यदि <math>\left[ \, \right]: \mathbb{R} \to \mathbb{Z}</math> हो तो हम फलन <math>|\left[z\right] - z| \leq 1</math> को पूर्णांक सन्निकटन कहते हैं। एक मापांक <math>n</math> और एक पूर्णांक सन्निकटन <math>\left[\,\right]</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>\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>.
Line 51: Line 47:
== एकल-शब्द बैरेट रिडक्शन ==
== एकल-शब्द बैरेट रिडक्शन ==


जब मान मशीनी शब्दों में फिट होते हैं। तो बैरेट ने प्रारम्भ में उपरोक्त एल्गोरिदम के पूर्णांक संस्करण पर विचार किया।
जब मान मशीनी शब्दों में फिट होते हैं। तो बैरेट ने प्रारम्भ में उपरोक्त एल्गोरिदम के पूर्णांक संस्करण पर विचार किया था।


हम फ़्लोर-फलन केस के विचार का वर्णन करते हैं।
हम फ़्लोर-फलन केस के विचार का वर्णन करते हैं।
Line 63: Line 59:
}
}
</syntaxhighlight>
</syntaxhighlight>
चूंकि विभाजन का मूल्य अधिक हो सकता है और क्रिप्टोग्राफ़िक सेटिंग्स में कुछ सीपीयू पर निरंतर-समय निर्देश नहीं हो सकता है। जो ऑपरेशन को [[ समय पर हमला |समय पर आक्रमण]] के अधीन करता है। इस प्रकार बैरेट रिडक्शन <math>1/n</math> मूल्य के साथ <math>m/2^k</math> अनुमानित है क्योंकि विभाजन द्वारा <math>2^k</math> यह केवल राइट-शिफ्ट है और इसलिए यह अधिक मूल्यवान नहीं है।
चूंकि विभाजन का मूल्य अधिक हो सकता है और क्रिप्टोग्राफ़िक सेटिंग्स में कुछ सीपीयू पर निरंतर-समय निर्देश नहीं हो सकता है। जो ऑपरेशन को [[ समय पर हमला |समय पर आक्रमण]] के अधीन करता है। इस प्रकार बैरेट रिडक्शन <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> दिया गया है। जिस पर विचार करें:


:<math>\frac{m}{2^k} = \frac{1}{n} \;\Longleftrightarrow\; m = \frac{2^k}{n}</math>
:<math>\frac{m}{2^k} = \frac{1}{n} \;\Longleftrightarrow\; m = \frac{2^k}{n}</math>
के लिए <math>m</math> पूर्णांक होने के लिए, हमें पूर्णांक बनाना होगा <math>{2^k}/{n}</math> किसी तरह।
<math>m</math> पूर्णांक होने के लिए, हमें किसी प्रकार <math>{2^k}/{n}</math> पूर्णांक बनाना होगा। निकटतम पूर्णांक तक पूर्णांकित करने से सर्वोत्तम सन्निकटन प्राप्त होगा। किन्तु इसका परिणाम <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> अहस्ताक्षरित अंकगणित के लिए उपयोग किया जाता है।


इस प्रकार हम निम्नलिखित के साथ उपरोक्त फलन का अनुमान लगा सकते हैं:
इस प्रकार हम निम्नलिखित के साथ उपरोक्त फलन का अनुमान लगा सकते हैं:
Line 79: Line 74:
}
}
</syntaxhighlight>
</syntaxhighlight>
चूंकि, जब से <math>m/2^k \le 1/n</math>, का मान है <code>q</code> उस फलन में अंत में एक बहुत छोटा हो सकता है, और इस प्रकार <code>a</code> केवल भीतर होने की गारंटी है <math>[0, 2n)</math> इसके बजाय <math>[0, n)</math> जैसा कि आम तौर पर आवश्यक है. एक सशर्त घटाव इसे ठीक करेगा:
चूंकि जब से <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 95: Line 90:
== एकल-शब्द बैरेट गुणन ==
== एकल-शब्द बैरेट गुणन ==


कल्पना करना <math>b</math> पूर्व से ज्ञात है.
माना कि <math>b</math> पूर्व से ज्ञात है।
यह हमें पूर्व-गणना करने की अनुमति देता है <math>\left\lfloor \frac{b R}{n} \right\rfloor</math> तक पहुँचने से पहले <math>a</math>.
 
बैरेट गुणन गणना <math>a b</math>, के उच्च भाग का अनुमान लगाता है <math>a b</math>
यह <math>a</math> तक पहुँचने से पहले हमें पूर्व-गणना <math>\left\lfloor \frac{b R}{n} \right\rfloor</math> करने की अनुमति प्रदान करता है। बैरेट गुणन गणना <math>a b</math>, <math>a b</math> के उच्च भाग का अनुमान लगाता है।
साथ
  <math> \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n </math>,
  <math> \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n </math>,
और सन्निकटन को घटा देता है।
दिये गये फलन के साथ और सन्निकटन को घटा देता है। तब से
तब से
  <math>\left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n</math> का गुणज <math>n</math>है,
  <math>\left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n</math> का गुणज है <math>n</math>,
परिणामी मूल्य
परिणामी मूल्य
  <math>a b - \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n</math>
  <math>a b - \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n</math>
का प्रतिनिधि है <math>a b \, \bmod \, n</math>.
का प्रतिनिधि <math>a b \, \bmod \, n</math> है।


== बैरेट और मोंटगोमरी गुणन के बीच पत्राचार ==
== बैरेट और मोंटगोमरी गुणन के बीच पत्राचार ==


याद रखें कि अहस्ताक्षरित मोंटगोमरी गुणन एक प्रतिनिधि की गणना करता है <math>a b \, \bmod \, n</math>
याद रखें कि मोंटगोमरी गुणन <math>a b \, \bmod \, n</math> प्रतिनिधि की गणना करता है। जैसा
जैसा
:<math>
:<math>
\frac{a \left(b R \, \bmod \, n \right) + \left( a \left( - b R \, \bmod \, n \right) n^{-1} \, \bmod \, R \right) n}{R}
\frac{a \left(b R \, \bmod \, n \right) + \left( a \left( - b R \, \bmod \, n \right) n^{-1} \, \bmod \, R \right) n}{R}
</math>.
</math>.


वास्तव में, यह मान बराबर है <math>a b - \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n</math>.
वास्तव में यह मान <math>a b - \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n</math> के समान है।


हम दावे को इस प्रकार साबित करते हैं।
हम इसे पूर्णतयः प्रमाणित करते हैं कि
:<math>
:<math>
\begin{align}
\begin{align}
Line 136: Line 128:
\end{align}
\end{align}
</math>
</math>
आम तौर पर, पूर्णांक सन्निकटन के लिए <math>\left[\,\right]_0, \left[\,\right]_1</math>,
सामान्यतः पूर्णांक सन्निकटन के लिए <math>\left[\,\right]_0, \left[\,\right]_1</math>, अपने पास-
अपने पास


:<math>
:<math>
Line 148: Line 139:
== बैरेट गुणन की सीमा ==
== बैरेट गुणन की सीमा ==


हमने आउटपुट को इससे बांध दिया है
हमने आउटपुट को इससे बाउंड कर दिया है।<math>
<math>
a b - \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n
a b - \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rfloor}{R} \right\rfloor \, n
=
=
Line 159: Line 149:
</math>.
</math>.


अन्य प्रकार के पूर्णांक सन्निकटन कार्यों के लिए भी समान सीमाएँ लागू होती हैं।
अन्य प्रकार के पूर्णांक सन्निकटन कार्यों के लिए भी समान लिमिट निर्धारित होती हैं। उदाहरण के लिए यदि हम <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>
\left| a b - \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rceil}{R} \right\rceil \, n \right|
\left| a b - \left\lfloor \frac{a \left\lfloor \frac{b R}{n} \right\rceil}{R} \right\rceil \, n \right|
Line 176: Line 164:




== बहु-शब्द बैरेट रिडक्शन ==
== मल्टी वर्ल्ड बैरेट रिडक्शन ==


कटौती पर विचार करने के लिए बैरेट की प्राथमिक प्रेरणा [[आरएसए (क्रिप्टोसिस्टम)]] का कार्यान्वयन था, जहां प्रश्न में मूल्य लगभग निश्चित रूप से एक मशीन शब्द के आकार से अधिक होगा। इस स्थिति में, बैरेट ने एक एल्गोरिदम प्रदान किया जो उपरोक्त एकल-शब्द संस्करण का अनुमान लगाता है लेकिन बहु-शब्द मानों के लिए। विवरण के लिए एप्लाइड क्रिप्टोग्राफी की हैंडबुक का खंड 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>




== बहुपदों के लिए बैरेट एल्गोरिथ्म ==
== बहुपदों के लिए बैरेट एल्गोरिथ्म ==


बहुपदों को उलट कर और एक्स-एडिक अंकगणित का उपयोग करके, बहुपद विभाजन के लिए बैरेट एल्गोरिथ्म का उपयोग करना भी संभव है।<ref>{{Cite web |title=बहुपदों के लिए बैरेट न्यूनीकरण|url=https://www.corsix.org/content/barrett-reduction-polynomials |access-date=2022-09-07 |website=www.corsix.org}}</ref>
बहुपद विभाजन के लिए बैरेट एल्गोरिदम का उपयोग करना, बहुपदों को विपरीत करके और X-एडिक अंकगणित का उपयोग करना भी संभव है।<ref>{{Cite web |title=बहुपदों के लिए बैरेट न्यूनीकरण|url=https://www.corsix.org/content/barrett-reduction-polynomials |access-date=2022-09-07 |website=www.corsix.org}}</ref>




== यह भी देखें ==
== यह भी देखें ==


* [[ मोंटगोमरी कमी ]] एक और समान एल्गोरिदम है।
* [[ मोंटगोमरी कमी | मोंटगोमरी रिडक्शन]] अन्य समान एल्गोरिदम है।


==संदर्भ==
==संदर्भ==
Line 204: Line 192:
श्रेणी:मॉड्यूलर अंकगणित
श्रेणी:मॉड्यूलर अंकगणित


[[Category: Machine Translated Page]]
[[Category:Created On 27/07/2023]]
[[Category:Created On 27/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]

Latest revision as of 16:09, 22 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
}


एकल-शब्द बैरेट गुणन

माना कि पूर्व से ज्ञात है।

यह तक पहुँचने से पहले हमें पूर्व-गणना करने की अनुमति प्रदान करता है। बैरेट गुणन गणना , के उच्च भाग का अनुमान लगाता है।

,

दिये गये फलन के साथ और सन्निकटन को घटा देता है। तब से

 का गुणज है,

परिणामी मूल्य


का प्रतिनिधि है।

बैरेट और मोंटगोमरी गुणन के बीच पत्राचार

याद रखें कि मोंटगोमरी गुणन प्रतिनिधि की गणना करता है। जैसा

.

वास्तव में यह मान के समान है।

हम इसे पूर्णतयः प्रमाणित करते हैं कि