System resztowy

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

Niech $B=(m_{1},m_{2},\dots ,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_{1},x_{2},\dots ,x_{n})$ gdzie $x_{i}=X{\text{ mod }}m_{i}$ dla każdego $1\leqslant i\leqslant 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\leqslant i\leqslant 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)\cdot (1,2,3)=(0\cdot 1{\bmod {2}},\;2\cdot 2{\bmod {3}},\;2\cdot 3{\bmod {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}\neq 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{\text{ 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_{1},x_{2},\dots ,x_{n})$ będzie reprezentacją liczby $X$ w systemie resztowym o bazie $(m_{1},m_{2},\dots ,m_{n}),$ oraz niech

M=m_{1}\cdot m_{2}\cdot \ldots \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 {1}}05=263\ {\bmod {1}}05=53.

Zobacz też

Linki zewnętrzne

Markus A.M.A. Hitz Markus A.M.A., ErichE. Kaltofen ErichE., Integer Division in Residue Number Systems [online], cs.rpi.edu [zarchiwizowane z adresu 2005-02-17] .