System resztowy

Ten artykuł dotyczy systemu liczbowego. Zobacz też: arytmetyka resztowa liczb całkowitych.

System resztowy (RNS od ang. residue number system) – system liczbowy służący do reprezentacji liczb całkowitych wektorem reszt z dzielenia względem ustalonego wektora wzajemnie względnie pierwszych modułów. Chińskie twierdzenie o resztach orzeka, że taka reprezentacja jest jednoznaczna dla liczb całkowitych ze zbioru gdzie jest iloczynem wszystkich modułów.

Niech będzie bazą względnie pierwszych modułów, a ich iloczynem. Wtedy reprezentacją liczby w systemie resztowym o bazie jest gdzie dla każdego

OperacjeEdytuj

Na liczbach reprezentowanych w systemie resztowym może być efektywnie przeprowadzonych wiele operacji arytmetycznych. Wykonuje się je, przeprowadzając niezależnie na odpowiednich resztach „zwykłe” operacje, a następnie operację modulo odpowiedniego modułu. Dla następujących operacji rozważmy dwie liczby całkowite,   i   reprezentowane przez   i   w systemie resztowym zdefiniowanym przez bazę   (dla   z przedziału  ).

Dodawanie i odejmowanieEdytuj

Dodawanie (lub odejmowanie) może być wykonane przez proste dodawanie (lub odejmowanie) małych liczb całkowitych i policzenie odpowiedniego modułu:

 

może być policzone w systemie resztowym jako:

 

MnożenieEdytuj

Mnożenie można wykonać w podobny sposób do dodawania i odejmowania. Aby obliczyć:

 

liczymy:

 

PrzykładEdytuj

Przyjmijmy bazę   Rozpatrzmy dwie liczby,   i   W przyjętym systemie resztowym liczby te reprezentujemy jako    

 
 
 

Obliczamy wartość iloczynu przy użyciu systemu resztowego:

 

Liczba (0, 1, 1) po zamianie na liczbę całkowitą w reprezentacji dziesiętnej wynosi 16.

DzielenieEdytuj

Dzielenie w systemie resztowym jest bardziej skomplikowanie.

Z drugiej strony jeśli   jest liczbą pierwszą dla   (tzn.   dla wszystkich  ), wtedy

 

może być prosto policzone przez

 

gdzie   jest liczbą odwrotną do   i   jest liczbą odwrotną z   modulo   (współczynniki   mogą zostać wyliczone raz dla danego systemu resztowego).

Konwersja odwrotnaEdytuj

Konwersję odwrotną można przeprowadzić w następujący sposób. Niech   będzie reprezentacją liczby   w systemie resztowym o bazie   oraz niech

 

oraz

 

gdzie:

 

wtedy

 

Np. w systemie o bazie (3, 5, 7) reprezentacją   jest (2, 3, 4), wtedy

 

oraz

 

więc

 

Zobacz teżEdytuj

Linki zewnętrzneEdytuj