System resztowy


System resztowy w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania Systemy liczboweKultura

Cyfry indyjsko-arabskie


Systemy wschodnioazjatyckie


Systemy alfabetyczne


Inne

Systemy pozycyjne (podstawa)

Dziesiętny (10)

Inne

więcej...


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

Niech B = ( m 1 , m 2 , , m n ) , {\displaystyle B=(m_{1},m_{2},\dots ,m_{n}),} będzie bazą względnie pierwszych modułów, a M {\displaystyle M} ich iloczynem. Wtedy reprezentacją liczby X {\displaystyle X} w systemie resztowym o bazie B {\displaystyle B} jest ( x 1 , x 2 , , x n ) {\displaystyle (x_{1},x_{2},\dots ,x_{n})} gdzie x i = X  mod  m i {\displaystyle x_{i}=X{\text{ mod }}m_{i}} dla każdego 1 i n . {\displaystyle 1\leqslant i\leqslant n.}

Spis treści

Operacje | edytuj kod

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 {\displaystyle A} i B , {\displaystyle B,} reprezentowane przez a i {\displaystyle a_{i}} i b i {\displaystyle b_{i}} w systemie resztowym zdefiniowanym przez bazę m i {\displaystyle m_{i}} (dla i {\displaystyle i} z przedziału 0 i n {\displaystyle 0\leqslant i\leqslant n} ).

Dodawanie i odejmowanie | edytuj kod

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

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

może być policzone w systemie resztowym jako:

c i = a i ± b i mod m i . {\displaystyle c_{i}=a_{i}\pm b_{i}\mod m_{i}.}

Mnożenie | edytuj kod

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

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

liczymy:

c i = a i b i mod m i . {\displaystyle c_{i}=a_{i}\cdot b_{i}\mod m_{i}.}

Przykład | edytuj kod

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

M = m 1 m 2 m 3 = 2 3 5 = 30 , {\displaystyle M=m_{1}\cdot m_{2}\cdot m_{3}=2\cdot 3\cdot 5=30,} X Y = 46 , {\displaystyle X\cdot Y=46,} X Y mod M = 46 mod 30 = 16. {\displaystyle 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 ) . {\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 | edytuj kod

Dzielenie w systemie resztowym jest bardziej skomplikowanie.

Z drugiej strony jeśli B {\displaystyle B} jest liczbą pierwszą dla M {\displaystyle M} (tzn. b i 0 {\displaystyle b_{i}\neq 0} dla wszystkich i {\displaystyle i} ), wtedy

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

może być prosto policzone przez

c i = a i b i 1 mod m i , {\displaystyle c_{i}=a_{i}\cdot b_{i}^{-1}\mod m_{i},}

gdzie B 1 {\displaystyle B^{-1}} jest liczbą odwrotną do B  modulo  M , {\displaystyle B{\text{ modulo }}M,} i b i 1 {\displaystyle b_{i}^{-1}} jest liczbą odwrotną z b i {\displaystyle b_{i}} modulo m i {\displaystyle m_{i}} (współczynniki b i 1 {\displaystyle b_{i}^{-1}} mogą zostać wyliczone raz dla danego systemu resztowego).

Konwersja odwrotna | edytuj kod

Konwersję odwrotną można przeprowadzić w następujący sposób. Niech ( x 1 , x 2 , , x n ) {\displaystyle (x_{1},x_{2},\dots ,x_{n})} będzie reprezentacją liczby X {\displaystyle X} w systemie resztowym o bazie ( m 1 , m 2 , , m n ) , {\displaystyle (m_{1},m_{2},\dots ,m_{n}),} oraz niech

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

oraz

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

gdzie:

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

wtedy

X = ( i = 1 n m i ~ ( m i ~ 1 mod m i ) x i ) mod M . {\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ą X {\displaystyle X} jest (2, 3, 4), wtedy

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

oraz

m 1 ~ 1 mod m 1 = 2 , m 2 ~ 1 mod m 2 = 1 , m 3 ~ 1 mod m 3 = 1 , {\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

X = ( 35 2 2 + 21 1 3 + 15 1 4 )   mod 1 05 = 263   mod 1 05 = 53. {\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ż | edytuj kod

Linki zewnętrzne | edytuj kod

Na podstawie artykułu: "System resztowy" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy