System resztowy

System resztowy (skr. 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 [0, M), gdzie M jest iloczynem wszystkich modułów.

Niech B = (m₁, m₂, ..., m_n), będzie bazą względnie pierwszych modułów, a M ich iloczynem. Wtedy reprezentacją liczby X w systemie resztowym o bazie B jest (x₁, x₂, ..., x_n) gdzie x_i = X mod m_i dla każdego 1 ≤ i ≤ n.

Operacje

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, A i B, reprezentowane przez a_i i b_i w systemie resztowym zdefiniowanym przez bazę m_i (dla i z przedziału 0 ≤ i ≤ n).

Dodawanie i odejmowanie

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

$C=A\pm B \mod M$

może być policzone w systemie resztowym jako:

$c_i=a_i\pm b_i \mod m_i$

Mnożenie

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

$C = A \cdot B \mod M,$

liczymy:

$c_i = a_i\cdot b_i \mod m_i$

Przykład

Przyjmijmy bazę (2,3,5). Rozpatrzmy dwie liczby, X=2 i Y=23. W przyjętym systemie resztowym liczby te reprezentujemy jako X = (0,2,2), Y= (1,2,3). :

$M=m_1 \cdot m_2 \cdot m_3 = 2 \cdot 3 \cdot 5 = 30$

$X \cdot Y=46$

$X \cdot Y \mod M = 46 \mod 30 = 16$

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

(0, 2, 2) * (1, 2, 3) = (0*1 mod 2, 2*2 mod 3, 2*3 mod 5) = (0, 1, 1)

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

Dzielenie

Dzielenie w systemie resztowym jest bardziej skomplikowanie.

Z drugiej strony jeśli B jest liczbą pierwszą dla M (tzn. $b_i\not =0$ dla wszystkich i) wtedy

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

może być prosto policzone przez

$c_i=a_i \cdot b_i^{-1} \mod m_i$

gdzie $B^{-1}$ jest liczbą odwrotną do B modulo M, i $b_i^{-1}$ jest liczbą odwrotną z $b_i$ modulo $m_i$ (współczynniki $b_i^{-1}$ mogą zostać wyliczone raz dla danego systemu resztowego).

Konwersja odwrotna

Konwersją odwrotną można przeprowadzić w następujący sposób. Niech (x₁, x₂, ..., x_n) będzie reprezentacją liczby X w systemie resztowym o bazie (m₁, m₂, ..., m_n), oraz niech

$M = m_1\cdot m_2\cdot ...\cdot m_n$

oraz

$\tilde{m_i} = M\cdot m_i^{-1},$

gdzie

$x = z^{-1} \bmod a \iff (x\cdot z) \bmod a = 1$;

wtedy

$X = \bigg(\sum_{i=1}^n \tilde{m_i} \cdot (\tilde{m_i}^{-1} \bmod m_i) \cdot x_i\bigg) \bmod M$

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

$M = 105, \tilde{m_1} = 35, \tilde{m_2} = 21, \tilde{m_3} = 15$

oraz

$\tilde{m_1}^{-1} \bmod m_1 = 2, \tilde{m_2}^{-1} \bmod m_2 = 1, \tilde{m_3}^{-1} \bmod m_3 = 1,$

więc $X = (35\cdot 2\cdot 2 + 21\cdot 1\cdot 3 + 15\cdot 1\cdot 4)\ \bmod 105 = 263\ \bmod 105 = 53.$

Zobacz też

• system pozycyjny
• silniowy system pozycyjny

Linki zewnętrzne

• [1] – artykuł opisujący jeden z możliwych algorytmów dzielenia