System numeracji pozostałości

Rezydualny system liczbowy ( RNS ) to system liczbowy reprezentujący liczby całkowite za pomocą ich wartości modulo kilku par liczb całkowitych względnie pierwszych, zwanych modułami. Taka reprezentacja jest dozwolona przez chińskie twierdzenie o resztach , które stwierdza, że jeśli $M$ jest iloczynem modułów, to w przedziale o długości $M istnieje$ dokładnie jedna liczba całkowita mająca dowolny zestaw wartości modułowych. Arytmetyka resztowego systemu liczbowego jest również nazywana arytmetyka wielomodułowa .

Arytmetyka wielomodułowa jest szeroko stosowana do obliczeń z dużymi liczbami całkowitymi, zwykle w algebrze liniowej , ponieważ zapewnia szybsze obliczenia niż w przypadku zwykłych systemów liczbowych, nawet jeśli bierze się pod uwagę czas konwersji między systemami liczbowymi. Inne zastosowania arytmetyki wielomodułowej obejmują największy wspólny dzielnik wielomianu , obliczenia bazowe Gröbnera i kryptografię .

Definicja

System liczbowy reszt jest zdefiniowany przez zbiór $k$ liczb całkowitych

{\ Displaystyle \ {m_ {1}, m_ {2}, m_ {3}, \ ldots, m_ {k} \},}

nazywane modułami , które generalnie zakłada się, że są parami względnie pierwsze (to znaczy, że dowolne dwa z nich mają największy wspólny dzielnik równy jeden). Systemy liczb resztowych zostały zdefiniowane dla modułów innych niż względnie pierwsze, ale nie są powszechnie stosowane ze względu na gorsze właściwości. Dlatego nie będą one rozpatrywane w dalszej części artykułu.

Liczba całkowita $x$ jest reprezentowana w systemie liczbowym reszt przez zbiór jej reszt

{\ Displaystyle \ {x_ {1}, x_ {2}, x_ {3}, \ ldots, x_ {k} \}}

w ramach podziału euklidesowego przez moduły. To jest

{\ Displaystyle x_ {i} = x \ operatorname {mod} m_ {i},}

I

{\ Displaystyle 0 \ równoważnik x_ {i}<m_ {i}}

dla każdego $I$

Niech $M$ będzie iloczynem wszystkich ${\ displaystyle m_ {i}}$ . Dwie liczby całkowite, których różnica jest wielokrotnością $M$ , mają tę samą reprezentację w rezydualnym systemie liczbowym określonym przez $m i$ s. Dokładniej, chińskie twierdzenie o resztach stwierdza, że każdy z $M$ różnych zestawów możliwych reszt reprezentuje dokładnie jedną klasę reszt modulo $M$ . Oznacza to, że każdy zestaw reszt reprezentuje dokładnie jedną liczbę całkowitą ${\ displaystyle X}$ w przedziale ${\ Displaystyle 0, \ kropki, M-1}$ . Dla liczb ze znakiem zakres dynamiczny wynosi ${\ textstyle {-\ lfloor M/2 \ rfloor} \ leq X \ leq \ lfloor (M-1 ) / 2 \ rfloor }$ (gdy $jest parzysta$ generalnie reprezentowana jest dodatkowa wartość ujemna).

Działania arytmetyczne

Do dodawania, odejmowania i mnożenia liczb reprezentowanych w systemie liczb reszt wystarczy wykonać tę samą operację modułową na każdej parze reszt. Dokładniej, jeśli

{\ Displaystyle [m_ {1}, \ ldots, m_ {k}]}

$całkowitych$ listą ${\ Displaystyle [y_ {1}, \ ldots, y_ {k}],}$ liczb $x$ i $y$ reszty jest liczbą całkowitą $z$ reprezentowaną przez $\ Displaystyle [z_ {1}, \ ldots, z_ {k}]}$ takie, że

{\ Displaystyle z_ {i} = (x_ {i} + y_ {i}) \ operatorname {mod} m_ {i},}

dla $i = 1, ..., k$ (jak zwykle mod oznacza operację modulo polegającą na wzięciu reszty z dzielenia euklidesowego przez prawy operand). Odejmowanie i mnożenie są zdefiniowane podobnie.

W przypadku kolejnych operacji nie jest konieczne stosowanie operacji modulo na każdym kroku. Może być zastosowany na końcu obliczeń lub podczas obliczeń, aby uniknąć przepełnienia operacji sprzętowych.

Jednak operacje takie jak porównywanie wielkości, obliczanie znaku, wykrywanie przepełnienia, skalowanie i dzielenie są trudne do wykonania w systemie liczb resztowych.

Porównanie

Jeśli dwie liczby całkowite są równe, to wszystkie ich reszty są równe. I odwrotnie, jeśli wszystkie reszty są równe, to dwie liczby całkowite są równe lub ich różnice są wielokrotnością $M$ . Wynika z tego, że testowanie równości jest łatwe.

Z drugiej strony, testowanie nierówności ( $x < y$ ) jest trudne i zwykle wymaga przekształcenia liczb całkowitych w reprezentację standardową. W konsekwencji ta reprezentacja liczb nie jest odpowiednia dla algorytmów wykorzystujących testy nierówności, takich jak dzielenie euklidesowe i algorytm euklidesowy .

Dział

Podział w systemach liczbowych reszt jest problematyczny. Z drugiej strony, jeśli ${\ Displaystyle$ z (czyli ${\ displaystyle b_ {i} \ not = 0}$ $b_ { i$ ), to b ja ≠

{\ Displaystyle C = A \ cdot B ^ {- 1} \ mod M}

można łatwo obliczyć wg

\ Displaystyle c_ {i} = a_ {i} \ cdot b_ {i} ^ {- 1} \ mod m_ {i},}

gdzie ${\ Displaystyle B ^ {- 1}}$ jest multiplikatywną odwrotnością modulo M $\$ $Displaystyle M}$ b $\ Displaystyle b_ {i} ^ {- 1}}$ jest multiplikatywną odwrotnością ${\ displaystyle b_ {i}}$ modulo ${\ displaystyle m_ {i}}$ .

Aplikacje

RNS mają zastosowania w dziedzinie cyfrowej arytmetyki komputerowej . Rozkładając w ten sposób dużą liczbę całkowitą na zbiór mniejszych liczb całkowitych, duże obliczenie można wykonać jako serię mniejszych obliczeń, które można wykonać niezależnie i równolegle.

Zobacz też

Dalsza lektura

Szabo, Mikołaj S.; Tanaka, Ryszard I. (1967). Resztkowa arytmetyka i jej zastosowania w technologii komputerowej (1 wyd.). Nowy Jork, USA: McGraw-Hill .
Sonderstrand, Michael A.; Jenkins, W. Kenneth; Jullien, Graham A.; Taylor, Fred J., wyd. (1986). Arytmetyka systemu liczb resztowych: nowoczesne zastosowania w cyfrowym przetwarzaniu sygnałów . IEEE Press Seria przedruków (1 wyd.). Nowy Jork, USA: IEEE Circuits and Systems Society , IEEE Press . ISBN 0-87942-205-X . LCCN 86-10516 . Kod zamówienia IEEE PC01982. (VIII+418+6 stron)
Czerwiakow, NI; Molahosseini, AS; Lachow, Pensylwania (2017). Konwersja reszty na binarną dla ogólnych zbiorów modułów na podstawie przybliżonego chińskiego twierdzenia o resztach . International Journal of Computer Mathematics , 94:9, 1833-1849, doi: 10.1080/00207160.2016.1247439.
Fin'ko [Финько], Oleg Anatolevich [Олег Анатольевич] (czerwiec 2004). „Duże systemy funkcji boolowskich: realizacja za pomocą modułowych metod arytmetycznych” . Automatyka i zdalne sterowanie . 65 (6): 871–892. doi : 10.1023/B:AURC.0000030901.74901.44 . ISSN 0005-1179 . LCCN 56038628 . S2CID 123623780 . CODEN AURCAT . Mi o 1588 .
Czerwiakow, NI; Lachow, Pensylwania; Deryabin, MA (2020). Rozwiązanie systemowe oparte na liczbach resztkowych w celu zmniejszenia kosztów sprzętu konwolucyjnej sieci neuronowej . Neurocomputing , 407, 439-453, doi: 10.1016/j.neucom.2020.04.018.
Bajard, Jean-Claude; Méloni, Nicolas; Plantard, Thomas (2006-10-06) [lipiec 2005]. „Wydajne podstawy RNS dla kryptografii” (PDF) . IMACS'05: Światowy Kongres: Obliczenia Naukowe Stosowana Matematyka i Symulacja . Paryż, Francja. Identyfikator HAL: lirmm-00106470. Zarchiwizowane (PDF) od oryginału w dniu 2021-01-23 . Źródło 2021-01-23 . (1+7 stron)
Omondi, Amos; Premkumar, Benjamin (2007). Systemy liczb resztkowych: teoria i implementacja . Londyn, Wielka Brytania: Imperial College Press . ISBN 978-1-86094-866-4 . (296 stron)
Mohan, PV Ananda (2016). Systemy liczb resztowych: teoria i zastosowania (1 wyd.). Birkhäuser / Springer International Publishing Szwajcaria . doi : 10.1007/978-3-319-41385-3 . ISBN 978-3-319-41383-9 . LCCN 2016947081 . (351 stron)
Amir Sabbagh, Molahosseini; de Sousa, Leonel Seabra; Chip-Hong Chang, wyd. (2017-03-21). Projektowanie systemów wbudowanych ze specjalnymi systemami arytmetycznymi i liczbowymi (1 wyd.). Springer International Publishing AG . doi : 10.1007/978-3-319-49742-6 . ISBN 978-3-319-49741-9 . LCCN 2017934074 . (389 stron)
https://web.archive.org/web/20050217165652/http://www.cs.rpi.edu/research/ps/93-9.ps . Zarchiwizowane od oryginału w dniu 17.02.2005 . Źródło 2021-01-23 . {{ cite web }} : Brakujące lub puste |title= ( pomoc ) Algorytmy dzielenia
Knutha, Donalda Ervina . Sztuka programowania komputerowego . Addisona Wesleya .
Harvey, David (2010). „Wielomodułowy algorytm obliczania liczb Bernoulliego” . Matematyka obliczeń . 79 (272): 2361–2370. doi : 10.1090/S0025-5718-2010-02367-1 . S2CID 11329343 .
Lecerf, Grégoire; Schost, Éric (2003). „Szybkie mnożenie wielowymiarowych szeregów potęgowych w charakterystycznym zera”. SADIO Dziennik elektroniczny poświęcony informatyce i badaniom operacyjnym . 5 (1): 1–10.
Pomarańczowy, Sebastien; Renault, Guénaël; Yokoyama, Kazuhiro (2012). „Wydajna arytmetyka w kolejnych polach rozszerzeń algebraicznych z wykorzystaniem symetrii”. Matematyka w informatyce . 6 (3): 217–233. doi : 10.1007/s11786-012-0112-y . S2CID 14360845 .
Yokoyama, Kazuhiro (wrzesień 2012). „Wykorzystanie technik modułowych do wydajnego obliczania operacji idealnych”. Międzynarodowe warsztaty na temat algebry komputerowej w obliczeniach naukowych . Berlin / Heidelberg, Niemcy: Springer. s. 361–362.
Hladík, Jakub; Šimeček, Ivan (styczeń 2012). „Arytmetyka modułowa do rozwiązywania równań liniowych na GPU” . Seminarium z analizy numerycznej . s. 68–70.
Pernet, Clément (czerwiec 2015). „Algorytmiczna algebra liniowa dokładna: teoria i praktyka”. Materiały z ACM 2015 na Międzynarodowym Sympozjum na temat Obliczeń Symbolicznych i Algebraicznych . Stowarzyszenie Maszyn Komputerowych . s. 17–18.
Lecerf, Grégoire (2018). „O złożoności algorytmu podwypadkowego Lickteiga-Roya”. Dziennik obliczeń symbolicznych .
Yokoyama, Kazuhiro; Noro, Masayuki; Takeshima, Taku (1994). „Wielomodułowe podejście do faktoryzacji wielomianów w czasie dwuwymiarowych wielomianów całkowych” . Dziennik obliczeń symbolicznych . 17 (6): 545–563. doi : 10.1006/jsco.1994.1034 .
Isupow, Konstantin (2021). „Wysokowydajne obliczenia w systemie liczb resztowych przy użyciu arytmetyki zmiennoprzecinkowej”. Obliczenia . 9 (2): 9. doi:10.3390/obliczenia9020009 . ISSN 2079-3197.