बैरेट रिडक्शन

मॉड्यूलर अंकगणित में बैरेट रिडक्शन 1986 में पी.डी. द्वारा प्रारम्भ किया गया एक रिडक्शन कलन विधि है। बैरेट कंप्यूटिंग का सरल उपाय

$c=a\,{\bmod {\,}}n\,$

इस प्रकार यह तेज़ विभाजन एल्गोरिथ्म का उपयोग करना होगा। बैरेट रिडक्शन एल्गोरिदम है। जिसे इस ऑपरेशन को अनुकूलित करने के लिए डिज़ाइन किया गया है, इसमे $n$ स्थिर है और $a<n^{2}$ भाग को गुणन से प्रतिस्थापित करना है।

ऐतिहासिक रूप से वैल्यू के लिए $a,b<n$, बैरेट रिडक्शन $ab\,{\bmod {\,}}n\,$ को संचालित करके सम्पूर्ण प्रोडक्ट ab की गणना की गई। हाल ही में यह दिखाया गया कि यदि हम किसी ऑपरेंड पर पूर्वगणना कर सकते हैं। तो पूर्ण उत्पाद अनावश्यक होता है।

सामान्य विचार

हम फलन कहते हैं $\left[\,\right]:\mathbb {R} \to \mathbb {Z}$ पूर्णांक सन्निकटन। यदि $|\left[z\right]-z|\leq 1$.

इस प्रकार मापांक $n$ के लिए और एक पूर्णांक सन्निकटन $\left[\,\right]$,

हम परिभाषित करते हैं- ${\text{mod}}^{\left[\,\right]}\,n:\mathbb {Z} \to (\mathbb {Z} /n\mathbb {Z} )$ जैसा

$a\,{\text{mod}}^{\left[\,\right]}\,n=a-\left[a/n\right]n$.

के सामान्य विकल्प $\left[\,\right]$ फ्लोर, छत और गोलाई फलन हैं।

सामान्यतः बैरेट रिडक्शन दो पूर्णांक सन्निकटन $\left[\,\right]_{0},\left[\,\right]_{1}$ निर्दिष्ट करके प्रारम्भ होता है और यथोचित $ab\,{\bmod {\,}}n$ निकट सन्निकटन की गणना करता है। जैसा

$ab-\left[{\frac {a\,\left[{\frac {bR}{n}}\right]_{0}}{R}}\right]_{1}n$.

स्थिति $b=1$ पी.डी. द्वारा प्रस्तुत किया गया था। बैरेट फ़्लोर फलन स्थिति के लिए $\left[\,\right]_{0}=\left[\,\right]_{1}=\lfloor \,\rfloor$. सामान्य स्थिति $b$ के लिए संख्या सिद्धांत पुस्तकालय में पाया गया था। पूर्णांक सन्निकटन दृश्य और मोंटगोमरी गुणन और बैरेट गुणन के बीच पत्राचार की खोज हनो बेकर, विंसेंट ह्वांग, मैथियास जे. कन्नविशर, बो-यिन यांग और शांग-यी यांग द्वारा की गई थी।

एकल-शब्द बैरेट रिडक्शन

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

हम फ़्लोर-फलन केस के विचार का वर्णन करते हैं।

गणना करते समय $a\,{\bmod {\,}}n$ अहस्ताक्षरित पूर्णांकों के लिए स्पष्ट एनालॉग $n$ के लिए विभाजन का उपयोग करना होगा :

func reduce(a uint) uint {
    q:= a / n  // Division implicitly returns the floor of the result.
    return a - q * n
}

चूंकि विभाजन का मूल्य अधिक हो सकता है और क्रिप्टोग्राफ़िक सेटिंग्स में कुछ सीपीयू पर निरंतर-समय निर्देश नहीं हो सकता है। जो ऑपरेशन को समय पर आक्रमण के अधीन करता है। इस प्रकार बैरेट रिडक्शन $1/n$ मूल्य के साथ $m/2^{k}$ अनुमानित है क्योंकि विभाजन द्वारा $2^{k}$ यह केवल राइट-शिफ्ट है और इसलिए यह अधिक मूल्यवान नहीं है।

इस क्रम की गणना में सर्वोत्तम मूल्य $m$ के लिए $2^{k}$ दिया गया है। जिस पर विचार करें:

${\frac {m}{2^{k}}}={\frac {1}{n}}\;\Longleftrightarrow \;m={\frac {2^{k}}{n}}$

$m$ पूर्णांक होने के लिए, हमें किसी प्रकार ${2^{k}}/{n}$ पूर्णांक बनाना होगा। निकटतम पूर्णांक तक पूर्णांकित करने से सर्वोत्तम सन्निकटन प्राप्त होगा। किन्तु इसका परिणाम $m/2^{k}$ से बड़ा होना $1/n$ हो सकता है। जो अंडरफ्लो का कारण बन सकता है। इस प्रकार $m=\lfloor {2^{k}}/{n}\rfloor$ अहस्ताक्षरित अंकगणित के लिए उपयोग किया जाता है।

इस प्रकार हम निम्नलिखित के साथ उपरोक्त फलन का अनुमान लगा सकते हैं:

func reduce(a uint) uint {
    q := (a * m) >> k // ">> k" denotes bitshift by k.
    return a - q * n
}

चूंकि जब से $m/2^{k}\leq 1/n$, का मान q है। उस फलन में अंत में बहुत छोटा हो सकता है और इस प्रकार a केवल अन्दर होने की गारंटी $[0,2n)$ है। इसके अतिरिक्त $[0,n)$ जैसा कि सामान्यतः आवश्यक है। इसे सशर्त घटाव प्रक्रिया ठीक करेगी:

func reduce(a uint) uint {
    q := (a * m) >> k
    a -= q * n
    if a >= n {
        a -= n
    }
    return a
}

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

कल्पना करना $b$ पूर्व से ज्ञात है. यह हमें पूर्व-गणना करने की अनुमति देता है $\left\lfloor {\frac {bR}{n}}\right\rfloor$ तक पहुँचने से पहले $a$. बैरेट गुणन गणना $ab$, के उच्च भाग का अनुमान लगाता है $ab$ साथ

$\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n$,

और सन्निकटन को घटा देता है। तब से

$\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n$ का गुणज है $n$,

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

$ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n$

का प्रतिनिधि है $ab\,{\bmod {\,}}n$.

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

याद रखें कि अहस्ताक्षरित मोंटगोमरी गुणन एक प्रतिनिधि की गणना करता है $ab\,{\bmod {\,}}n$ जैसा

${\frac {a\left(bR\,{\bmod {\,}}n\right)+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)n}{R}}$.

वास्तव में, यह मान बराबर है $ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n$.

हम दावे को इस प्रकार साबित करते हैं।

$\left[\,\right]_{0},\left[\,\right]_{1}$