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

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