Barrett reduction
મોડ્યુલર અંકગણિતમાં, બેરેટ રિડક્શન એ 1986માં પી. ડી. દ્વારા રજૂ કરાયેલ રિડક્શન અલ્ગોરિધમ છે. બેરેટ. ઝડપી વિભાજન અલ્ગોરિધમનો ઉપયોગ કરવો એ ગણતરીની નિષ્કપટ રીત હશે. બેરેટ રિડક્શન એ એક અલ્ગોરિધમ છે જે આ કામગીરીને અનુકૂળ બનાવવા માટે રચાયેલ છે, એમ ધારીને કે તે સતત છે, અને ગુણાકાર દ્વારા વિભાગોને બદલે છે. ઐતિહાસિક રીતે, મૂલ્યો માટે, સંપૂર્ણ ઉત્પાદનમાં બેરેટ ઘટાડાને લાગુ કરીને ગણતરી કરવામાં આવે છે. તાજેતરમાં, એવું દર્શાવવામાં આવ્યું હતું કે જો આપણે ઓપરેન્ડ્સમાંથી કોઈ એક પર પૂર્વગણતરી કરી શકીએ તો સંપૂર્ણ ઉત્પાદન બિનજરૂરી છે. સામાન્ય વિચાર આપણે કાર્યને પૂર્ણાંક અંદાજ કહીએ છીએ. મોડ્યુલસ અને પૂર્ણાંક અંદાજ માટે, આપણે આ રીતે વ્યાખ્યાયિત કરીએ છીએ. સામાન્ય પસંદગીઓ ફ્લોર, છત અને ગોળાકાર કાર્યો છે. સામાન્ય રીતે, બેરેટ ગુણાકાર બે પૂર્ણાંક અંદાજોને સ્પષ્ટ કરીને શરૂ થાય છે અને જ્યાં એક નિશ્ચિત અચળાંક હોય છે, સામાન્ય રીતે 2 ની ઘાત હોય છે, તેના વ્યાજબી રીતે નજીકના અંદાજની ગણતરી કરે છે, જેથી ગુણાકાર અને ભાગાકાર અસરકારક રીતે કરી શકાય. આ કેસ પી. ડી. એ રજૂ કર્યો હતો. ફ્લોર-ફંક્શન કેસ માટે બેરેટ. સામાન્ય કેસ એન. ટી. એલ. માં મળી શકે છે. પૂર્ણાંક અંદાજ દૃશ્ય અને મોન્ટગોમેરી ગુણાકાર અને બેરેટ ગુણાકાર વચ્ચેના પત્રવ્યવહારની શોધ હન્નો બેકર, વિન્સેન્ટ હ્વાંગ, મેથિયસ જે. કન્નવિશર, બો-યીન યાંગ અને શાંગ-યી યાંગ દ્વારા કરવામાં આવી હતી. જ્યારે મૂલ્યો મશીન શબ્દોમાં બંધબેસે છે ત્યારે સિંગલ-વર્ડ બેરેટ રિડક્શન બેરેટને શરૂઆતમાં ઉપરોક્ત અલ્ગોરિધમનો પૂર્ણાંક સંસ્કરણ માનવામાં આવે છે. અમે અને સાથે ફ્લોર-ફંક્શન કેસ માટેના વિચારને સમજાવીએ છીએ. સહી વગરના પૂર્ણાંકોની ગણતરી કરતી વખતે, સ્પષ્ટ એનાલોગ આ પ્રમાણે વિભાજનનો ઉપયોગ કરવાનો હશેઃ ફંક ઘટાડે છે (એક યુન્ટ) યુન્ટ {q: = a/n// ડિવિઝન ગર્ભિત રીતે પરિણામની સપાટી પરત કરે છે. જો કે, વિભાજન ખર્ચાળ હોઈ શકે છે અને, ક્રિપ્ટોગ્રાફિક સેટિંગ્સમાં, કેટલાક CPU પર સતત-સમયની સૂચના ન પણ હોઈ શકે, જે કામગીરીને સમયના હુમલાને આધિન કરે છે. આમ બેરેટ ઘટાડો મૂલ્ય સાથે અંદાજિત થાય છે કારણ કે વિભાજન દ્વારા માત્ર એક જમણી પાળી છે, અને તેથી તે સસ્તી છે. આપેલ વિચારણા માટે શ્રેષ્ઠ મૂલ્યની ગણતરી કરવા માટેઃ પૂર્ણાંક બનવા માટે, આપણે કોઈક રીતે ગોળાકાર કરવાની જરૂર છે. નજીકના પૂર્ણાંકને ગોળાકાર કરવાથી શ્રેષ્ઠ અંદાજ મળશે પરંતુ તે તેના કરતા મોટો થઈ શકે છે, જે અંડરફ્લોનું કારણ બની શકે છે. આમ સહી વગરના અંકગણિત માટે વપરાય છે. આમ આપણે ઉપરના વિધેયને નીચેની બાબતો સાથે અંદાજિત કરી શકીએ છીએઃ func ઘટાડે છે (a uint) uint {q: = (a * m)> k// "> k" એ k દ્વારા બિટ્શિફ્ટ સૂચવે છે. a-q * n પરત કરો} જો કે, કારણ કે, તે વિધેયમાં q નું મૂલ્ય ખૂબ નાનું હોઈ શકે છે, અને આમ a સામાન્ય રીતે જરૂરી હોય તેના બદલે અંદર હોવાની ખાતરી આપે છે. શરતી બાદબાકી આને સુધારશેઃ જો a> = n {a-= n} પાછો a} એક શબ્દ બેરેટ ગુણાકાર જાણીતો હોય તો (a * m) q: = (a * m)> k a-= q * n ઘટાડે છે. આ આપણને પ્રાપ્ત થાય તે પહેલાં પૂર્વ ગણતરી કરવાની મંજૂરી આપે છે. બેરેટ ગુણાકાર ગણતરી કરે છે, સાથે ઉચ્ચ ભાગનો અંદાજ કાઢે છે અને અંદાજને બાદ કરે છે. કારણ કે તે ગુણાંક છે, પરિણામી મૂલ્ય તેનું પ્રતિનિધિ છે. બેરેટ અને મોન્ટગોમેરી ગુણાકાર વચ્ચેનો પત્રવ્યવહાર યાદ કરો કે હસ્તાક્ષર વિનાનું મોન્ટગોમેરી ગુણાકાર એ. એસ. ના પ્રતિનિધિની ગણતરી કરે છે. હકીકતમાં, આ મૂલ્ય બરાબર છે. અમે દાવો નીચે પ્રમાણે સાબિત કરીએ છીએ. સામાન્ય રીતે, પૂર્ણાંક અંદાજો માટે, આપણી પાસે છે. બેરેટ ગુણાકારની શ્રેણી આપણે આઉટપુટને તેની સાથે બાંધીએ છીએ. સમાન સીમાઓ અન્ય પ્રકારના પૂર્ણાંક અંદાજ કાર્યો માટે હોય છે. ઉદાહરણ તરીકે, જો આપણે રાઉન્ડિંગ હાફ અપ ફંક્શન પસંદ કરીએ, તો આપણી પાસે મલ્ટી-વર્ડ બેરેટ રિડક્શન બેરેટની પ્રાથમિક પ્રેરણા ઘટાડો ધ્યાનમાં લેવા માટે આરએસએનું અમલીકરણ હતું, જ્યાં પ્રશ્નમાંના મૂલ્યો લગભગ ચોક્કસપણે મશીન વર્ડના કદ કરતાં વધી જશે. આ પરિસ્થિતિમાં, બેરેટ એક અલ્ગોરિધમ પ્રદાન કરે છે જે ઉપરના એક-શબ્દ સંસ્કરણને અંદાજિત કરે છે પરંતુ બહુ-શબ્દ મૂલ્યો માટે. વધુ વિગતો માટે હેન્ડબુક ઓફ એપ્લાઇડ ક્રિપ્ટોગ્રાફીનો વિભાગ 14.3.3 જુઓ. બહુપદીઓ માટે બેરેટ અલ્ગોરિધમ બહુપદીઓને ઉલટાવીને અને X-adic અંકગણિતનો ઉપયોગ કરીને બહુપદી વિભાજન માટે બેરેટ અલ્ગોરિધમનો ઉપયોગ કરવો પણ શક્ય છે. આ પણ જુઓ મોન્ટગોમેરી ઘટાડો એ અન્ય સમાન અલ્ગોરિધમ છે. સંદર્ભો સ્ત્રોતો કોમ્પ્યુટર અંકગણિત મોડ્યુલર અંકગણિત