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.}
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
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 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}.}
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 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
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.}
Linki zewnętrzne
edytuj