Mnożenie modułowe Montgomery'ego

W modułowych obliczeniach arytmetycznych modułowe mnożenie Montgomery'ego , częściej określane jako mnożenie Montgomery'ego , jest metodą wykonywania szybkiego mnożenia modułowego. Został wprowadzony w 1985 roku przez amerykańskiego matematyka Petera L. Montgomery'ego .

Modułowe mnożenie Montgomery'ego opiera się na specjalnej reprezentacji liczb zwanej formą Montgomery'ego. Algorytm $ab wykorzystuje N$ formy Montgomery'ego $aib$ do efektywnego obliczenia postaci Montgomery'ego $mod$ . Wydajność wynika z unikania kosztownych operacji dzielenia. Klasyczne mnożenie modułowe zmniejsza iloczyn podwójnej szerokości $ab,$ stosując dzielenie przez $N$ i zachowując tylko resztę. Podział ten wymaga estymacji cyfr ilorazowych i korekty. Z kolei forma Montgomery'ego zależy od stałej $R > N$ co jest względnie pierwsze z $N$ , a jedynym koniecznym dzieleniem w mnożeniu Montgomery'ego jest dzielenie przez $R$ . Stałą $R$ można wybrać tak, aby dzielenie przez $R$ było łatwe, co znacznie poprawia szybkość algorytmu. W praktyce $R$ jest zawsze potęgą dwójki, ponieważ dzielenie przez potęgi dwójki można zrealizować poprzez przesunięcie bitów .

Konieczność przekształcenia $aib$ w postać Montgomery'ego i ich iloczynu z postaci Montgomery'ego oznacza, że obliczenie pojedynczego iloczynu przez mnożenie Montgomery'ego jest wolniejsze niż algorytmy konwencjonalne lub $redukujące$ Barretta . Jednak podczas wykonywania wielu mnożeń z rzędu, jak w przypadku potęgowania modułowego , wyniki pośrednie można pozostawić w postaci Montgomery'ego. Wtedy początkowa i końcowa konwersja staje się znikomym ułamkiem ogólnych obliczeń. Wiele ważnych systemów kryptograficznych, takich jak RSA i Diffie-Hellman są oparte na operacjach arytmetycznych modulo dużej liczby nieparzystej, a dla tych kryptosystemów obliczenia wykorzystujące mnożenie Montgomery'ego z $R$ potęgą dwójki są szybsze niż dostępne alternatywy.

Arytmetyka modułowa

Niech $N$ oznacza dodatni moduł całkowity. Pierścień ilorazowy $Z / N Z$ składa się z klas reszt modulo $N$ , czyli jego elementami są zbiory postaci

{\ Displaystyle \ {a + kN \ dwukropek k \ w \ mathbf {Z} \},}

gdzie $a$ mieści się w zakresie liczb całkowitych. Każda klasa reszt jest zbiorem liczb całkowitych takich, że różnica dowolnych dwóch liczb całkowitych w zbiorze jest podzielna przez $N$ (i klasa reszt jest maksymalna w odniesieniu do tej właściwości; liczby całkowite nie są pomijane w klasie reszt, chyba że naruszałyby warunek podzielności). Klasa reszt odpowiadająca $a$ jest oznaczona $jako$ . Równość klas reszt nazywana jest kongruencją i jest oznaczana

{\ Displaystyle {\ bar {a}} \ równoważnik {\ bar {b}} {\ pmod {N}}.}

Przechowywanie całej klasy reszt na komputerze jest niemożliwe, ponieważ klasa reszt ma nieskończenie wiele elementów. Zamiast tego klasy pozostałości są przechowywane jako reprezentatywne. Konwencjonalnie przedstawicielami tymi są liczby całkowite $a$ dla których $0 \leq a \leq N - 1$ . Jeśli $a$ jest liczbą całkowitą, wówczas reprezentant $a$ jest zapisywany $jako mod N$ . Podczas zapisywania kongruencji często identyfikuje się liczbę całkowitą z klasą reszt, którą reprezentuje. W tej konwencji powyższa równość jest zapisywana $a \equiv b mod N$ .

Arytmetyka na klasach reszt jest wykonywana najpierw przez wykonanie arytmetyki liczb całkowitych na ich przedstawicielach. Wynik operacji na liczbach całkowitych określa klasę reszt, a wynik operacji modułowej jest określany przez obliczenie przedstawiciela klasy reszt. Na przykład, jeśli $N = 17$ , to suma klas reszt $7$ i $15$ jest obliczana przez znalezienie sumy całkowitej $7 + 15 = 22$ , a następnie określenie $22 mod 17$ , liczby całkowitej między 0 a 16, której różnica z 22 jest wielokrotnością 17. W tym przypadku ta liczba całkowita to 5, więc $7 + 15 \equiv 5 mod 17$ .

Forma Montgomery'ego

Jeżeli $aib$ są liczbami całkowitymi z zakresu $[0, N - 1]$ , to ich suma mieści się w przedziale $[0, 2 N 2] ,$ $-$ a ich różnica mieści się w przedziale $[- N + 1, N - 1]$ , więc określenie przedstawiciela w $[0, N - 1]$ wymaga co najwyżej jednego odjęcia lub dodania (odpowiednio) $N$ . Jednak iloczyn $ab$ mieści się w przedziale $[0, N 2 - 2 N + 1]$ . Przechowywanie pośredniego iloczynu całkowitego $ab$ wymaga dwa razy więcej bitów niż $a$ lub $b$ , a efektywne określenie przedstawiciela w $[0, N - 1]$ wymaga dzielenia. Z matematycznego punktu widzenia liczbę całkowitą między 0 a $N - 1$ , która jest przystająca do $ab$ , można wyrazić, stosując twierdzenie o dzieleniu euklidesowym :

{\ Displaystyle ab = qN + r,}

gdzie $q$ $,$ ilorazem a $r reszta$ w przedziale [ $0, -]$ Reszta $r$ to $ab mod N$ . Określenie $r$ można wykonać, obliczając $q$ , a następnie odejmując $qN$ od $ab$ . Na przykład ponownie z ${\ displaystyle N = 17}$ , iloczyn $7 \cdot 15$ $, podzielenie ,$ określany przez obliczenie odjęcie ⌊ $\ Displaystyle \ lfloor 105/17 \ rfloor =$ ${\ Displaystyle 105-6 \ cdot 17 = 105-102 = 3}$ .

Ponieważ obliczenie $q$ wymaga dzielenia, jest niepożądanie drogie na większości sprzętu komputerowego. Forma Montgomery'ego to inny sposób wyrażania elementów pierścienia, w którym produkty modułowe można obliczyć bez kosztownych podziałów. Chociaż podziały są nadal konieczne, można je wykonać w odniesieniu do innego dzielnika $R$ . Dzielnik ten można wybrać jako potęgę dwójki, dla której dzielenie można zastąpić przesunięciem, lub jako całkowitą liczbę słów maszynowych, dla których dzielenie można zastąpić pominięciem słów. Podziały te są szybkie, więc większość kosztów obliczania produktów modułowych przy użyciu formularza Montgomery'ego to koszt obliczania zwykłych produktów.

Moduł pomocniczy $R$ musi być dodatnią liczbą całkowitą taką, że $gcd(R, N) = 1$ . Dla celów obliczeniowych konieczne jest również, aby dzielenie i redukcja modulo $R$ były niedrogie, a moduł nie jest przydatny do mnożenia modułowego, chyba że $R > N$ . Forma Montgomery'ego klasy reszt $a$ w odniesieniu do $R$ to $aR mod N$ , to znaczy jest reprezentatywna dla klasy reszt $aR$ . Załóżmy na przykład, że $N = 17$ i że $R = 100$ . Formy Montgomery 3, 5, 7 i 15 to $300 mod 17 = 11$ , $500 mod 17 = 7$ , $700 mod 17 = 3$ i $1500 mod 17 = 4$ .

Dodawanie i odejmowanie w postaci Montgomery'ego jest tym samym, co zwykłe modułowe dodawanie i odejmowanie ze względu na prawo dystrybucji:

{\ Displaystyle aR + bR = (a + b) R}

{\ Displaystyle aR-bR = (ab) R.}

Wynika to z faktu, że ponieważ $gcd(R, N) = 1$ , mnożenie przez $R$ jest izomorfizmem grupy addytywnej $Z / N Z$ . Na przykład $(7 + 15) mod 17 = 5$ , co w postaci Montgomery'ego staje się $(3 + 4) mod 17 = 7$ .

Mnożenie w postaci Montgomery'ego jest jednak pozornie bardziej skomplikowane. Zwykły iloczyn $aR$ i $bR$ nie reprezentuje iloczynu $aib$ , ponieważ ma dodatkowy współczynnik $R$ $:$

{\ Displaystyle (aR {\ bmod {N}}} (bR {\ bmod {N}}) {\ bmod {N}} = (abR) R {\ bmod {N}}.}

Obliczanie produktów w postaci Montgomery'ego wymaga usunięcia dodatkowego czynnika $R$ . Podczas gdy dzielenie przez $R$ jest tanie, produkt pośredni $(aR mod N) (bR mod N)$ nie jest podzielny przez $R$ , ponieważ operacja modulo zniszczyła tę właściwość. Na przykład iloczyn form Montgomery'ego 7 i 15 modulo 17 jest iloczynem 3 i 4, czyli 12. Ponieważ 12 nie jest podzielne przez 100, usunięcie dodatkowego czynnika R wymaga dodatkowego $wysiłku$ .

Usunięcie dodatkowego czynnika $R$ można wykonać mnożąc przez liczbę całkowitą $R'$ taką, że $RR' \equiv 1 (mod N)$ , to znaczy przez $R'$ , którego klasa reszt jest modularną odwrotnością $R$ mod $N$ . Następnie, pracując modulo $N$ ,

{\ Displaystyle (aR {\ bmod {N}}) (bR {\ bmod {N}}) R '\ równoważnik (aR) (bR) R ^ {-1} \ równoważnik (ab) R {\ pmod {N }}.}

Liczba całkowita $R'$ istnieje z powodu założenia, że $R$ i $N$ są względnie pierwsze. Można go skonstruować za pomocą rozszerzonego algorytmu euklidesowego . Rozszerzony algorytm Euklidesa skutecznie wyznacza liczby całkowite $R'$ i $N'$ , które spełniają tożsamość Bézouta : $0 < R' < N$ , $0 < N' < R$ , oraz:

{\ Displaystyle RR'-NN' = 1.}

To pokazuje, że możliwe jest wykonanie mnożenia w postaci Montgomery'ego. Prostym algorytmem mnożenia liczb w postaci Montgomery'ego jest zatem pomnożenie $aR mod N$ , $bR mod N$ i $R'$ jako liczb całkowitych i zredukowanie modulo $N$ .

Na przykład, aby pomnożyć 7 i 15 modulo 17 w postaci Montgomery'ego, ponownie z $R = 100$ , oblicz iloczyn 3 i 4, aby uzyskać 12 jak powyżej. Z rozszerzonego algorytmu euklidesowego wynika, że $8\cdot100 - 47\cdot17 = 1$ , więc $R' = 8$ . Pomnóż 12 przez 8, aby uzyskać 96 i zmniejsz modulo 17, aby uzyskać 11. Zgodnie z oczekiwaniami jest to forma Montgomery'ego 3.

Algorytm REDC

Chociaż powyższy algorytm jest poprawny, jest wolniejszy niż mnożenie w reprezentacji standardowej ze względu na konieczność mnożenia przez $R'$ i dzielenia przez $N$ . Redukcja Montgomery'ego , znana również jako REDC, jest algorytmem, który jednocześnie oblicza iloczyn przez $R'$ i redukuje modulo $N$ szybciej niż metoda naiwna. W przeciwieństwie do konwencjonalnej redukcji modułowej, która koncentruje się na zmniejszeniu liczby do $N$ , redukcja Montgomery'ego koncentruje się na uczynieniu liczby bardziej podzielną przez $R$ . Robi to, dodając małą wielokrotność $N$ , która jest wybrana, aby anulować resztę modulo $R$ . Dzielenie wyniku przez $R$ daje znacznie mniejszą liczbę. Ta liczba jest o tyle mniejsza, że jest bliska redukcji modulo $N$ , a obliczenie redukcji modulo $N$ wymaga jedynie końcowego odejmowania warunkowego. Ponieważ wszystkie obliczenia są wykonywane tylko przy użyciu redukcji i dzielenia w odniesieniu do $R$ , a nie $N$ , algorytm działa szybciej niż prosta modułowa redukcja przez dzielenie.

     funkcja  REDC  jest  wprowadzana:  Liczby całkowite  R  i  N  z  gcd(  R  ,  N  ) = 1  , Liczba całkowita  N  ′ w  [0,  R  − 1]  takie, że  NN  ′ ≡ −1 mod  R  , Liczba całkowita  T  w zakresie  [0,  RN  − 1]  .  wyjście:  Liczba całkowita  S  z zakresu  [0,  N  − 1]  taka, że 

    
    
      
         
    
         
    
 S  ≡  TR ⁻¹ mod  N  m  ← ((  T  mod  R  )  N  ′) mod  R  t  ← (  T  +  mN  ) /  R  jeśli  t  ≥  N  to  zwróć  t  −  N  inaczej  zwróć  t  koniec jeśli  koniec funkcji

Aby przekonać się, że ten algorytm jest poprawny, najpierw zauważ, że $m$ jest wybrane dokładnie tak, że $T + mN$ jest podzielne przez $R$ . Liczba jest podzielna przez $R$ wtedy i tylko wtedy, gdy jest przystająca do zera mod $R$ i mamy:

{\ Displaystyle T + mN \ równoważnik T + (((T {\ bmod {R}}) N') {\ bmod {R}}) N \ równoważnik T + TN'N \ równoważnik TT \ równoważnik 0 {\ pmod { R}}.}

Dlatego $t$ jest liczbą całkowitą. Po drugie, wyjściem jest albo $t$ albo $t - N$ , z których oba są przystające do $t mod N$ , więc aby udowodnić, że wyjście jest przystające do $TR -1 mod N$ , wystarczy udowodnić, że $t$ jest. Modulo $N$ , $t$ spełnia:

{\ Displaystyle t \ równoważnik (T + mN) R ^ {- 1} \ równoważnik TR ^ {-1} + (mR ^ {-1}) N \ równoważny TR ^ {- 1} {\ pmod {N}} .}

Dlatego wyjście ma prawidłową klasę pozostałości. Po trzecie, $m$ jest w $[0, R - 1]$ , a zatem $T + mN$ jest między 0 a $(RN - 1) + (R - 1) N < 2 RN$ . Stąd $t$ jest mniejsze niż $2 N$ , a ponieważ jest to liczba całkowita, to umieszcza $t$ w zakresie $[0, 2 N - 1]$ . Dlatego zmniejszenie $t$ do pożądanego zakresu wymaga co najwyżej jednego odjęcia, więc wynik algorytmu mieści się we właściwym zakresie.

Aby użyć REDC do obliczenia iloczynu 7 i 15 modulo 17, najpierw przekonwertuj do postaci Montgomery'ego i pomnóż jako liczby całkowite, aby uzyskać 12 jak powyżej. Następnie zastosuj REDC z $R = 100$ , $N = 17$ , $N' = 47$ i $T = 12$ . Pierwszy krok ustawia $m$ na $12 \cdot 47 mod 100 = 64$ . Drugi krok ustawia $t$ na $(12 + 64 \cdot 17) / 100$ . Zauważ, że $12 + 64 \cdot 17$ to 1100, czyli zgodnie z oczekiwaniami wielokrotność 100. $T$ jest ustawiona na 11, czyli mniej niż 17, więc końcowy wynik to 11, co zgadza się z obliczeniami z poprzedniej sekcji.

Jako inny przykład rozważmy iloczyn $7 \cdot 15 mod 17$ , ale z $R = 10$ . Używając rozszerzonego algorytmu Euklidesa, oblicz $-5 \cdot 10 + 3 \cdot 17 = 1$ , więc $N'$ będzie wynosić $-3 mod 10 = 7$ . Formy Montgomery 7 i 15 to $70 mod 17 = 2$ i $150 mod 17 = 14$ . Ich iloczyn 28 jest wejściem $T$ do REDC, a ponieważ $28 < RN = 170$ , to założenia REDC są spełnione. Aby uruchomić REDC, ustaw $m$ na $(28 mod 10) \cdot 7 mod 10 = 196 mod 10 = 6$ . Wtedy $28 + 6 \cdot 17 = 130$ , więc $t = 13$ . Ponieważ $30 mod 17 = 13$ , to jest forma Montgomery'ego $3 = 7 \cdot 15 mod 17$ .

Arytmetyka w postaci Montgomery'ego

Wiele interesujących operacji modulo $N$ można równie dobrze wyrazić w postaci Montgomery'ego. Dodawanie, odejmowanie, negacja, porównywanie pod kątem równości, mnożenie przez liczbę całkowitą nie w postaci Montgomery'ego oraz największe wspólne dzielniki z $N$ można wykonać za pomocą standardowych algorytmów. Symbol Jacobiego można obliczyć jako ${\ Displaystyle {\ duży (}{\ tfrac {a} {N}}} {\ duży)} = {\ duży (} {\ tfrac {aR} {N}} {\ duży)} / {\ duży (} {\ tfrac {R} {N}} {\ duży}}}$ $jak długo$ jest przechowywany

Kiedy $R > N$ , większość innych operacji arytmetycznych można wyrazić za pomocą REDC. To założenie implikuje, że iloczyn dwóch przedstawicieli mod $N$ jest mniejszy niż $RN$ , co jest dokładną hipotezą niezbędną do wygenerowania przez REDC poprawnego wyniku. W szczególności iloczyn $aR mod N$ i $bR mod N$ to $REDC((aR mod N)(bR mod N))$ . Połączona operacja mnożenia i REDC jest często nazywana mnożeniem Montgomery'ego .

Konwersja do postaci Montgomery'ego odbywa się poprzez obliczenie $REDC((a mod N)(R 2 mod N))$ . Konwersja z postaci Montgomery'ego odbywa się poprzez obliczenie $REDC(aR mod N)$ . Modularna odwrotność $aR mod N$ to $REDC((aR mod N) -1 (R 3 mod N))$ . Modułowe potęgowanie można wykonać za pomocą potęgowanie przez podniesienie do kwadratu przez zainicjowanie początkowego iloczynu do reprezentacji Montgomery'ego 1, to znaczy do $R mod N$ , oraz przez zastąpienie kroków mnożenia i kwadratu przez mnożenia Montgomery'ego.

Wykonanie tych operacji wymaga znajomości co najmniej $N'$ i $R 2 mod N$ . Gdy $R$ jest potęgą małej dodatniej liczby całkowitej $b$ , $N'$ można obliczyć za pomocą lematu Hensela : odwrotność $N$ modulo $b$ jest obliczana za pomocą naiwnego algorytmu (na przykład, jeśli $b = 2$ , to odwrotność wynosi 1), a lemat jest używany wielokrotnie, aby znaleźć odwrotność modulo do coraz wyższych potęg $b$ znana jest odwrotność modulo $R ;$ $N'$ jest negacją tej odwrotności. Stałe $R mod N$ i $R 3 mod N$ można wygenerować jako $REDC(R 2 mod N)$ i jako $REDC((R 2 mod N)(R 2 mod N))$ . Podstawową operacją jest obliczenie REDC produktu. Gdy potrzebny jest samodzielny REDC, można go obliczyć jako REDC produktu z $1 mod N$ . Jedynym miejscem, gdzie konieczna jest bezpośrednia redukcja modulo $N R2 mod N.$ $,$ jest wstępne obliczenie

Arytmetyka Montgomery'ego na liczbach całkowitych wieloprecyzyjnych

Większość aplikacji kryptograficznych wymaga liczb o długości setek, a nawet tysięcy bitów. Takie liczby są zbyt duże, aby można je było przechowywać w jednym słowie maszynowym. Zazwyczaj sprzęt wykonuje mod mnożenia o jakiejś podstawie $B$ , więc wykonywanie większych mnożeń wymaga połączenia kilku małych mnożeń. Baza $B$ to zazwyczaj 2 dla aplikacji mikroelektronicznych, 2 ⁸ dla 8-bitowego oprogramowania układowego lub 2 ³² lub 2 ⁶⁴ dla aplikacji programowych.

Algorytm REDC wymaga iloczynów modulo $R$ i zwykle $R > N$ , aby REDC mógł być użyty do obliczenia iloczynów. Jednakże, gdy $R$ jest potęgą $B$ , istnieje wariant REDC, który wymaga iloczynów tylko liczb całkowitych wielkości słowa maszynowego. Załóżmy, że zapisane są dodatnie liczby całkowite o wielu precyzjach little endian , to znaczy $x$ jest przechowywane jako tablica $x [0], ..., x [ℓ - 1]$ taka, że $0 \leq x [i] < b$ dla wszystkich $ja$ i $x = \sum x [ja] b ja$ . Algorytm zaczyna się od wieloprecyzyjnej liczby całkowitej $T$ i zmniejsza ją o jedno słowo na raz. Najpierw dodaje się odpowiednią wielokrotność $N$ , aby $T było$ podzielne przez $B$ . Następnie dodaje się wielokrotność $N$ $B2,$ aby $T było$ podzielne przez i tak dalej. Ostatecznie $T$ jest podzielne przez $R$ , a po podzieleniu przez $R$ znajduje się w tym samym miejscu, w którym znajdował się REDC po obliczeniu $t$ .

      funkcja  MultiPrecisionREDC  jest  wprowadzana:  liczba całkowita  N  z  gcd(  B  ,  N  ) = 1  , przechowywana jako tablica  p  słów, liczba całkowita  R  =  B ^r , --tak,  r  =  log _B R  liczba całkowita  N  ′ w  [0,  B  − 1 ]  takie, że  NN  ′ ≡ −1 (mod  B  )  , liczba całkowita  T   
      w zakresie  0 ≤  T  <  RN  , przechowywana jako tablica  r  +  p  słów.  Wyjście:  Liczba całkowita  S  w  [0,  N  − 1]  taka, że  TR ⁻¹ ≡  S  (mod  N  )  , zapisana jako tablica  p  słów. Ustaw   T  [  r  +  p  ] = 0  (dodatkowe słowo przeniesienia)  dla  0 ≤  i  <  r  
        

        
          
            

            
             do  --loop1- Spraw, aby T było podzielne przez  B ⁱ⁺¹ c  ← 0  m  ←  T  [  i  ] ⋅  N  ′ mod  B  dla  0 ≤  j  <  p  do  --loop2- Dodaj dolne słowo  m ⋅ N[j]  i przeniesienie z wcześniejszego i znajdź nowe przeniesienie  x  ←  T  [  i  +  j  ] +  m  ⋅  N  [  j  ] +  c  T  [ 
            
        
          
            

            
            
             i  +  j  ] ←  x  mod  B  c  ←  ⌊  x  /  B  ⌋  koniec dla  for  p  ≤  j  ≤  r  +  p  −  i  do  --loop3- Kontynuuj przenoszenie  x  ←  T  [  i  +  j  ] +  c  T  [  i  +  j  ] ←  x  mod  Bc  ←  _ 
        
    

      
        

      
         
    
         
    
 ⌊  x  /  B  ⌋  koniec dla  koniec dla  dla  0 ≤  i  <  p  do  S  [  i  ] ←  T  [  i  +  r  ]  koniec dla  jeśli  S  ≥  N  to  powrót  S  −  N  inaczej  powrót  S  koniec jeśli  koniec funkcja

Ostateczne porównanie i odejmowanie odbywa się za pomocą standardowych algorytmów.

Powyższy algorytm jest poprawny zasadniczo z tych samych powodów, dla których REDC jest poprawny. Za każdym razem w pętli $i$ wybiera się $m tak, że$ $T [i] + mN [0]$ jest podzielne przez $B$ . Następnie $mNB i$ jest dodawane do $T.$ Ponieważ ta wielkość wynosi zero mod $N$ , dodanie jej nie wpływa na wartość $T mod N$ . Jeśli $m i$ oznacza wartość $m$ obliczoną w $i$ iteracji pętli, to algorytm ustawia $S$ na $T + (\sum m i B i) N$ . Ponieważ MultiPrecisionREDC i REDC dają ten sam wynik, ta suma jest taka sama jak wybór $m$ , którego dokonałby algorytm REDC.

Ostatnie słowo $T$ , $T [r + p]$ (i w konsekwencji $S [p]$ ), jest używane tylko do utrzymania przeniesienia, ponieważ początkowy wynik redukcji jest związany z wynikiem z zakresu $0 \leq S < 2N$ . Wynika z tego, że tego dodatkowego słowa przenoszenia można całkowicie uniknąć, jeśli z góry wiadomo, że $R \geq 2N$ . W typowej implementacji binarnej jest to równoznaczne z powiedzeniem, że tego słowa przeniesienia można uniknąć, jeśli liczba bitów $N$ jest mniejsza niż liczba bitów $R$ . W przeciwnym razie przeniesienie będzie równe zero lub jeden. W zależności od procesora może być możliwe przechowywanie tego słowa jako flagi przeniesienia zamiast pełnowymiarowego słowa.

Możliwe jest połączenie mnożenia wieloprecyzyjnego i REDC w jeden algorytm. Ten połączony algorytm jest zwykle nazywany mnożeniem Montgomery'ego. Koç, Acar i Kaliski opisali kilka różnych implementacji. Algorytm może wykorzystywać zaledwie $p + 2$ słowa pamięci (plus bit przeniesienia).

Jako przykład niech $B = 10$ , $N = 997$ i $R = 1000$ . Załóżmy, że $a = 314$ i $b = 271$ . Reprezentacje $aib$ w Montgomery to $314000 mod 997 = 942$ $i$ 271000 $mod 997 = 813$ . Oblicz $942 \cdot 813 = 765846$ . Początkowe wejście $T$ do MultiPrecisionREDC będzie [6, 4, 8, 5, 6, 7]. Numer $N$ będzie reprezentowany jako [7, 9, 9]. Rozszerzony algorytm euklidesowy mówi, że $-299 \cdot 10 + 3 \cdot 997 = 1$ , więc $N'$ będzie równe 7.

 i ← 0 m ←  6 ⋅ 7 mod 10 = 2  j T c - ------- - 0 0485670 2  (Po pierwszej iteracji pierwszej pętli)  1 0485670 2 2 0485670 2 3 0487670 0  (Po pierwszej iteracji drugiej pętli pętli)  4 0487670 0 5 0487670 0 6 0487670 0 i ← 1 m ←  4 ⋅ 7 mod 10 = 8  j T c - ------- - 0 0087670 6  (Po pierwszej iteracji pierwszej pętli)  1 0067670 8 2 0067670 8 3 0067470 1  (Po pierwszej iteracji drugiej pętli)  4 0067480 0 5 0067480 0 i ← 2 m ←  6 ⋅ 7 mod 10 = 2  j T c - ------- - 0 0007480 2  (Po pierwszej iteracji pierwszej pętli)  1 0007480 2 2 0007480 2 3 0007400 1  (Po pierwszej iteracji drugiej pętli)  4 0007401 0

Dlatego przed końcowym porównaniem i odejmowaniem $S = 1047$ . Końcowe odejmowanie daje liczbę 50. Ponieważ reprezentacja Montgomery'ego $314 \cdot 271 mod 997 = 349$ to $349000 mod 997 = 50$ , jest to oczekiwany wynik.

Podczas pracy w bazie 2 określenie prawidłowego $m$ na każdym etapie jest szczególnie łatwe: jeśli bieżący bit roboczy jest parzysty, to $m$ wynosi zero, a jeśli jest nieparzysty, to $m$ wynosi jeden. Ponadto, ponieważ każdy krok MultiPrecisionREDC wymaga znajomości tylko najniższego bitu, mnożenie Montgomery'ego można łatwo połączyć z sumatorem oszczędzającym przenoszenie .

Ataki kanałami bocznymi

Ponieważ redukcja Montgomery'ego pozwala uniknąć kroków korekcyjnych wymaganych w dzieleniu konwencjonalnym, gdy oszacowania cyfr ilorazu są niedokładne, jest w większości wolna od gałęzi warunkowych, które są głównymi celami ataków bocznym kanałem czasowym i mocy ; kolejność wykonywanych instrukcji jest niezależna od wartości operandów wejściowych. Jedynym wyjątkiem jest końcowe odejmowanie warunkowe modułu, ale można je łatwo zmodyfikować (aby zawsze odjąć coś, moduł lub zero), aby uczynić go odpornym. Oczywiście konieczne jest upewnienie się, że algorytm potęgowania zbudowany wokół prymitywu mnożenia jest również odporny.

Zobacz też

redukcja Barretta

Linki zewnętrzne

Henry S. Warren, Jr. (lipiec 2012). „Teoria i praktyka mnożenia Montgomery'ego”. CiteSeerX 10.1.1.450.6124 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )