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

मॉड्यूलर अंकगणित में, बैरेट रिडक्शन 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}$