System resztowy

Szablon:Inne znaczenia Szablon:Systemy liczbowe 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⩽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 BmodM$

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 BmodM,$

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 YmodM=46mod30=16.$

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

$(0,2,2)\cdot (1,2,3)=(0\cdot 1mod2,2\cdot 2mod3,2\cdot 3mod5)=(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\ne 0$ dla wszystkich $i$), wtedy

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

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 \dots \cdot m_n$

oraz

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

gdzie:

$x=z^{-1}moda⟺(x\cdot z)moda=1;$

wtedy

$X=(\sum _{i=1}^n\widetilde{m_i}\cdot ({\widetilde{m_i}}^{-1}{modm}_i)\cdot x_i)modM.$

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

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

oraz

${\widetilde{m_1}}^{-1}{modm}_1=2,{\widetilde{m_2}}^{-1}{modm}_2=1,{\widetilde{m_3}}^{-1}{modm}_3=1,$

więc

$X=(35\cdot 2\cdot 2+21\cdot 1\cdot 3+15\cdot 1\cdot 4)mod105=263mod105=53.$

Zobacz też

• silniowy system pozycyjny
• system pozycyjny

Linki zewnętrzne

• Szablon:Cytuj