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

Niech ${\displaystyle B=(m_{1},m_{2},\dots ,m_{n}),}$ będzie bazą względnie pierwszych modułów, a ${\displaystyle M}$ ich iloczynem. Wtedy reprezentacją liczby ${\displaystyle X}$ w systemie resztowym o bazie ${\displaystyle B}$ jest ${\displaystyle (x_{1},x_{2},\dots ,x_{n})}$ gdzie ${\displaystyle x_{i}=X{\text{ mod }}m_{i}}$ dla każdego ${\displaystyle 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, ${\displaystyle A}$ i ${\displaystyle B,}$ reprezentowane przez ${\displaystyle a_{i}}$ i ${\displaystyle b_{i}}$ w systemie resztowym zdefiniowanym przez bazę ${\displaystyle m_{i}}$ (dla ${\displaystyle i}$ z przedziału ${\displaystyle 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:

${\displaystyle C=A\pm B\mod M}$

może być policzone w systemie resztowym jako:

${\displaystyle 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ć:

${\displaystyle C=A\cdot B\mod M,}$

liczymy:

${\displaystyle c_{i}=a_{i}\cdot b_{i}\mod m_{i}.}$

Przykład

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

${\displaystyle M=m_{1}\cdot m_{2}\cdot m_{3}=2\cdot 3\cdot 5=30,}$

${\displaystyle X\cdot Y=46,}$

${\displaystyle X\cdot Y\mod M=46\mod 30=16.}$

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

${\displaystyle (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 ${\displaystyle B}$ jest liczbą pierwszą dla ${\displaystyle M}$ (tzn. ${\displaystyle b_{i}\neq 0}$ dla wszystkich ${\displaystyle i}$), wtedy

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

może być prosto policzone przez

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

gdzie ${\displaystyle B^{-1}}$ jest liczbą odwrotną do ${\displaystyle B{\text{ modulo }}M,}$ i ${\displaystyle b_{i}^{-1}}$ jest liczbą odwrotną z ${\displaystyle b_{i}}$ modulo ${\displaystyle m_{i}}$ (współczynniki ${\displaystyle 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 ${\displaystyle (x_{1},x_{2},\dots ,x_{n})}$ będzie reprezentacją liczby ${\displaystyle X}$ w systemie resztowym o bazie ${\displaystyle (m_{1},m_{2},\dots ,m_{n}),}$ oraz niech

${\displaystyle M=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n}}$

oraz

${\displaystyle {\tilde {m_{i}}}=M\cdot m_{i}^{-1},}$

gdzie:

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

wtedy

${\displaystyle 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ą ${\displaystyle X}$ jest (2, 3, 4), wtedy

${\displaystyle M=105,{\tilde {m_{1}}}=35,{\tilde {m_{2}}}=21,{\tilde {m_{3}}}=15}$

oraz

${\displaystyle {\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

${\displaystyle 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ż

• silniowy system pozycyjny
• system pozycyjny

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] .