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.}$