redukcja Barretta

W arytmetyce modularnej redukcja Barretta to algorytm redukcji wprowadzony w 1986 roku przez PD Barretta. Naiwny sposób obliczania

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

byłoby użyć szybkiego algorytmu dzielenia . Redukcja $i$ to algorytm zaprojektowany do optymalizacji tej operacji, przy założeniu, $przez$ dzielenie mnożenie.

Główny pomysł

Niech ${\ displaystyle s = 1/n}$ będzie odwrotnością ${\ displaystyle n}$ jako liczby zmiennoprzecinkowej . Następnie

${\ Displaystyle a \ {\ bmod {\,}} n = a- \ lfloor as \ rfloor n}$

gdzie ${\ Displaystyle \ lfloor x \ rfloor}$ oznacza funkcję podłogi . Wynik jest dokładny, o ile $obliczany$ z wystarczającą dokładnością.

Redukcja Barretta jednym słowem

Barrett początkowo rozważał całkowitą wersję powyższego algorytmu, gdy wartości pasują do słów maszynowych.

Podczas obliczania ${\ displaystyle a \, {\ bmod {\,}} n}$ przy użyciu powyższej metody, ale z liczbami całkowitymi, oczywistym analogiem byłoby użycie dzielenia przez ${\ displaystyle n$ : n

    
          
         
 func  reduce  (  a  uint  )  uint  {  q  :=  a  /  n  // Dzielenie niejawnie zwraca dolną część wyniku.  zwróć  a  -  q  *  n  } 

Jednak podział może być kosztowny, aw ustawieniach kryptograficznych może nie być instrukcją o stałym czasie na niektórych procesorach. Zatem redukcja Barretta jest zbliżona $jest$$}$$2$ \ ^ słuszne -shift i tak jest tanio.

Aby obliczyć najlepszą wartość dla danego $\$$Displaystyle 2 ^ {k}}$ rozważ: m {\ displaystyle m}

${\ Displaystyle {\ Frac {m} {2 ^ {k}}} = {\ Frac {1} {n}} \; \ Longleftrightarrow \; m = {\ ułamek {2^{k}}{n}}}$

Aby $_ Zaokrąglenie$$liczbą$ , zaokrąglić $niedomiar$$będzie$ całkowitej da najlepsze przybliżenie, ale może spowodować, że co może Zatem ${\ Displaystyle m = \ lfloor {2 ^ {k}}/{n} \ rfloor}$ jest powszechnie używany.

W ten sposób możemy przybliżyć powyższą funkcję za pomocą:

    
           
         
 func  reduce  (  a  uint  )  uint  {  q  :=  (  a  *  m  )  >>  k  // ">> k" oznacza przesunięcie bitowe o k.  zwróć  a  -  q  *  n  } 

Jednakże, ponieważ $za$ w tej funkcji może mała, a a być w zakresie ${\ Displaystyle [0,2n)}$ zamiast ${\ Displaystyle [0, n)},$ jak jest to ogólnie wymagane. Warunkowe odejmowanie poprawi to:

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

Ponieważ jest to tylko przybliżenie, należy wziąć pod uwagę prawidłowy zakres ${\ displaystyle m/2 ^ {k}$$.$ Błąd przybliżenia wynosi: ${\ displaystyle 1/n}$

${\ Displaystyle e = {\ Frac {1} {n}} - {\ Frac {m} {2 ^ {k}}}}$

Zatem błąd w wartości q wynosi ${\ displaystyle ae}$ . Tak długo, jak $displaystyle a <1$$\$ ważna, więc za . Funkcja redukcji może nie dać od $muszą$ błędnej odpowiedzi, ale granice na ${\ displaystyle a}$ poprawną odpowiedź w ogólnym

Wybierając większe wartości $których obowiązuje$ można zwiększyć zakres wartości, $.$$większe wartości$ mogą powodować problemy z przepełnieniem w innych miejscach

Przykład

Rozważ przypadek ${\ displaystyle n = 101}$ podczas pracy z 16-bitowymi liczbami całkowitymi.

Najmniejsza wartość , która ma sens, to $\$$displaystyle k = 7}$ , ponieważ jeśli to redukcja będzie ważna tylko dla wartości $<n}$ które są już minimalne! Dla wartości siedem $\ Displaystyle m = \ lfloor 2 ^ {k}/n \ rfloor = \ lfloor 128/101 \ rfloor = 1$ . Dla wartości ośmiu ${\ Displaystyle m = \ lfloor 256/101 \ rfloor = 2}$ . Zatem ${\ Displaystyle k = 8} nie$${\ Displaystyle 1/128}$$\ Displaystyle 1/101$ przybliżenie w tym przypadku ( $)$ jest dokładnie takie samo jak . k ${\ Displaystyle k = 9}$ , otrzymujemy ${\ Displaystyle m = \ lfloor 512/101 \ rfloor = 5} ,$ jest lepszym przybliżeniem.

Teraz rozważymy prawidłowe zakresy wejściowe dla ${\ displaystyle k = 7}$ i ${\ displaystyle k = 9}$ . W pierwszym przypadku ${\ Displaystyle e = 1/nm/2 ^ {k} = 1/101-1/128 = 27/12928}$ więc ${\ Displaystyle a <1/e}$ implikuje ${\ Displaystyle a <478,81}$ . Ponieważ $całkowitą$ , faktycznie maksymalna wartość to 478. (W praktyce funkcja działa dla wartości do 504).

Jeśli weźmiemy ${\ Displaystyle k = 9}$ , to ${\ Displaystyle e = 1/101-5/512 = 7/51712},$ a więc maksymalna wartość ${\ displaystyle a}$ to 7387. (W praktyce funkcja działa do 7473.)

Następna wartość , która daje lepsze przybliżenie, to 13, co daje $81$$displaystyle 81/8192}$ . Należy jednak zauważyć, że wartość pośrednia $k$ obliczeniach przepełni wartość 16-bitową bez znaku, gdy ${\ Displaystyle 810 \ równoważnik a}$ a zatem $\ Displaystyle k = 7}$ lepiej sprawdza się w tej sytuacji.

Dowód na zakres dla określonego k

Niech ${\ displaystyle k_ {0}}$ będzie najmniejszą liczbą całkowitą taką, że ${\ displaystyle 2 ^ {k_ {0}}> n}$ . Weź ${\ displaystyle k_ {0} + 1}$ jako rozsądną wartość dla $+ 1 {\ displaystyle k}$ w powyższych równaniach. Podobnie jak w powyższych fragmentach kodu, let

• ${\ Displaystyle q = \ lewo \ lfloor {\ Frac {ma} {2 ^ {k}}} \ prawo \ rfloor}$ i
• ${\ displaystyle r = a-qn}$ .

Ze względu na funkcję podłogi jest liczbą całkowitą i $}}$$\ Displaystyle r \ równoważny a$ } . Ponadto, jeśli $a \ równoważnik$ za $}}$ k W takim przypadku zapisanie powyższych fragmentów jako wyrażenia:

${\ Displaystyle a \, {\ bmod {\,}} n = {\ rozpocząć {przypadki} r & {\ tekst {jeśli}} r <n \\ rn & {\text{inaczej}}\end{przypadki}}}$

Dowód na to jest następujący: ${\ displaystyle r <2n}$

Jeśli ${\ Displaystyle a \ równoważnik 2 ^ {k}}$ , to

${\ Displaystyle {\ Frac {a} {2 ^ {k}}} \ cdot (2 ^ {k} \ mod n) <n}$

$Displaystyle n \ cdot {\ Frac {ma \ mod 2 ^ {k}} {2 ^ {k}}} <n} niezależnie od za {\$ za Displaystyle $}$ , wynika, że

${\ Displaystyle {\ Frac {a \ cdot (2 ^ {k} \ mod n)} {2 ^ {k} }}+ n\cdot {\frac {ma\mod 2^{k}}{2^{k}}}<2n}$

${\ Displaystyle a- \ lewo (a - {\ Frac {a \ cdot (2 ^ {k} \ mod n)} {2 ^ {k}}} \ prawej) +{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n}$

${\ Displaystyle a - {\ Frac {a} {2 ^ {k}}} \ cdot \ lewo (2 ^ {k} - (2 ^ {k} \ mod n)\right)+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n}$

${\ Displaystyle a- {\ Frac {na} {2 ^ {k}}} \ cdot \ lewo ({\ Frac {2 ^ { k}-(2^{k}\mod n)}{n}}\right)+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n }$

${\ Displaystyle a- {\ Frac {na} {2 ^ {k}}} \ cdot \ left\lfloor {\frac {2^{k}}{n}}\right\rfloor \ +{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}< 2n}$

${\ Displaystyle a- {\ Frac {nma} {2 ^ {k}}} + {\ Frac {n \ cdot (ma \ mod 2 ^ {k})} {2 ^ {k}}} <2n}$

${\ Displaystyle a- \ left ({\frac {ma- (ma\mod 2^{k})}{2^{k}}}\right)\cdot n<2n}$

${ \ Displaystyle a - \ lewo \ lfloor {\ Frac {ma} {2 ^ {k}}} \ prawo \ rfloor \ cdot n <2n} za - q n <2 n {$

$}$

${\ displaystyle r <2n}$

Wielowyrazowa redukcja Barretta

Główną motywacją Barretta do rozważenia redukcji była implementacja RSA , gdzie omawiane wartości prawie na pewno przekroczą rozmiar słowa maszynowego. W tej sytuacji Barrett dostarczył algorytm, który przybliża powyższą wersję jednowyrazową, ale dla wartości wielowyrazowych. Aby uzyskać szczegółowe informacje, patrz sekcja 14.3.3 Podręcznika Kryptografii Stosowanej .

Algorytm Barretta dla wielomianów

Możliwe jest również użycie algorytmu Barretta do dzielenia wielomianów, poprzez odwrócenie wielomianów i zastosowanie arytmetyki X-adic.

Zobacz też

• Redukcja Montgomery'ego to kolejny podobny algorytm.

Źródła

•    Bosselaers, A.; Govaerts, R.; Vandewalle, J. (1993). „Porównanie trzech modułowych funkcji redukcji” . W Stinson, Douglas R. (red.). Postępy w kryptologii — Crypto'93 . Notatki z wykładów z informatyki. Tom. 773. Zygmunt. s. 175–186. CiteSeerX 10.1.1.40.3779 . ISBN 3540483292 .
•    Hasenplaugh, W.; Gaubatz, G.; Gopal, V. (2007). „Szybka redukcja modułowa” (PDF) . 18. Sympozjum IEEE na temat arytmetyki komputerowej (ARITH'07) . s. 225–9. doi : 10.1109/ARITH.2007.18 . ISBN 978-0-7695-2854-0 . S2CID 14801112 .