Barrett reduction
मॉड्यूलर अंकगणित में, बैरेट रिडक्शन एक रिडक्शन एल्गोरिथ्म है जिसे 1986 में पी. डी. बैरेट। कम्प्युटिंग का एक सरल तरीका एक तेज़ विभाजन एल्गोरिथ्म का उपयोग करना होगा। बैरेट रिडक्शन एक एल्गोरिथ्म है जिसे इस ऑपरेशन को अनुकूलित करने के लिए डिज़ाइन किया गया है, यह मानते हुए कि यह स्थिर है, और गुणा द्वारा विभाजन को प्रतिस्थापित करता है। ऐतिहासिक रूप से, मूल्यों के लिए, पूर्ण उत्पाद पर बैरेट रिडक्शन लागू करके गणना की जाती है। हाल ही में, यह दिखाया गया था कि यदि हम ऑपरेंड में से किसी एक पर पूर्व संगणना कर सकते हैं तो पूरा उत्पाद अनावश्यक है। सामान्य विचार हम एक फलन को एक पूर्णांक सन्निकटन कहते हैं। एक मापांक और एक पूर्णांक सन्निकटन के लिए, हम के रूप में परिभाषित करते हैं। आम विकल्प फर्श, छत और गोल कार्य हैं। आम तौर पर, बैरेट गुणन दो पूर्णांक सन्निकटनों को निर्दिष्ट करके शुरू होता है और एक उचित रूप से निकट सन्निकटन की गणना करता है, जहां एक निश्चित स्थिरांक है, आमतौर पर 2 की एक शक्ति है, जिसे चुना जाता है ताकि गुणा और विभाजन को कुशलता से किया जा सके। यह मामला पी. डी. द्वारा पेश किया गया था। फ्लोर-फंक्शन केस के लिए बैरेट। इसका सामान्य मामला एन. टी. एल. में पाया जा सकता है। पूर्णांक सन्निकटन दृश्य और मोंटगोमेरी गुणन और बैरेट गुणन के बीच पत्राचार की खोज हैनो बेकर, विंसेंट ह्वांग, मथायस जे. कन्नविशर, बो-यिन यांग और शांग-यी यांग ने की थी। एकल-शब्द बैरेट रिडक्शन बैरेट को शुरू में उपरोक्त एल्गोरिथ्म का एक पूर्णांक संस्करण माना जाता है जब मान मशीन शब्दों में फिट होते हैं। हम और के साथ फर्श-कार्य मामले के विचार को स्पष्ट करते हैं। अहस्ताक्षरित पूर्णांकों के लिए गणना करते समय, स्पष्ट अनुरूप विभाजन का उपयोग करना होगाः फंक रिड्यूस (एक उइनट) उइनट {q: = a/n// विभाजन निहित रूप से परिणाम का आधार देता है। हालांकि, विभाजन महंगा हो सकता है और, क्रिप्टोग्राफिक सेटिंग्स में, कुछ सीपीयू पर एक निरंतर-समय निर्देश नहीं हो सकता है, जो ऑपरेशन को समय के हमले के अधीन करता है। इस प्रकार बैरेट की कमी एक मूल्य के साथ अनुमानित है क्योंकि विभाजन केवल एक सही-बदलाव है, और इसलिए यह सस्ता है। दिए गए विचार के लिए सर्वोत्तम मूल्य की गणना करने के लिएः एक पूर्णांक होने के लिए, हमें किसी तरह गोल करने की आवश्यकता है। निकटतम पूर्णांक को गोल करने से सबसे अच्छा अनुमान मिलेगा, लेकिन इसके परिणामस्वरूप यह उससे बड़ा हो सकता है, जो अधोप्रवाह का कारण बन सकता है। इस प्रकार अहस्ताक्षरित अंकगणित के लिए उपयोग किया जाता है। इस प्रकार हम उपरोक्त फलन को निम्नलिखित के साथ अनुमानित कर सकते हैंः फ़ंक्स रिड्यूस (ए यून्ट) यून्ट {क्यूः = (ए * एम)> के// "> के" बिटशिफ्ट को के द्वारा दर्शाता है. ए-क्यू * एन लौटाता है हालांकि, क्योंकि उस फलन में क्यू का मान बहुत छोटा हो सकता है, और इस प्रकार केवल ए के भीतर होने की गारंटी है न कि आम तौर पर आवश्यक है। एक सशर्त घटाव इसे ठीक करेगाः यदि a> = n {a-= n} लौटाता है a} एक शब्द बैरेट गुणन मान लीजिए कि ज्ञात है तो (a * m) uint {q: = (a * m)> k a-= q * n को कम करें। यह हमें प्राप्त करने से पहले पूर्व-गणना करने की अनुमति देता है। बैरेट गुणन गणना करता है, साथ के उच्च भाग को अनुमानित करता है, और सन्निकटन को घटाता है। चूंकि एक गुणक है, परिणामी मान का प्रतिनिधि है। बैरेट और मोंटगोमेरी गुणन के बीच पत्राचार याद रखें कि अहस्ताक्षरित मोंटगोमेरी गुणन के रूप में एक प्रतिनिधि की गणना करता है। वास्तव में, यह मान इसके बराबर है। हम इस दावे को निम्नानुसार साबित करते हैं। आम तौर पर, पूर्णांक सन्निकटन के लिए, हमारे पास है। बैरेट गुणन की सीमा हम आउटपुट को इसके साथ बांधते हैं। इसी तरह की सीमाएँ अन्य प्रकार के पूर्णांक सन्निकटन कार्यों के लिए होती हैं। उदाहरण के लिए, यदि हम राउंडिंग हाफ अप फ़ंक्शन चुनते हैं, तो हमारे पास मल्टी-वर्ड बैरेट रिडक्शन बैरेट की प्राथमिक प्रेरणा कमी पर विचार करने के लिए आरएसए का कार्यान्वयन था, जहां विचाराधीन मान लगभग निश्चित रूप से एक मशीन शब्द के आकार से अधिक होंगे। इस स्थिति में, बैरेट ने एक एल्गोरिथ्म प्रदान किया जो उपरोक्त एकल-शब्द संस्करण का अनुमान लगाता है लेकिन बहु-शब्द मूल्यों के लिए। अधिक जानकारी के लिए हैंडबुक ऑफ एप्लाइड क्रिप्टोग्राफी का खंड 14.3.3 देखें। बहुपदों के लिए बैरेट एल्गोरिथ्म बहुपदों को उलटकर और एक्स-एडिक अंकगणित का उपयोग करके बहुपद विभाजन के लिए बैरेट एल्गोरिथ्म का उपयोग करना भी संभव है। यह भी देखें कि मोंटगोमेरी रिडक्शन एक और समान एल्गोरिथ्म है। संदर्भ स्रोत कंप्यूटर अंकगणितीय मॉड्यूलर अंकगणितीय