Residual class system

The system of residual classes (SOC) ( born residue number system ) is a number system based on modular arithmetic .

The representation of a number in the system of residual classes is based on the concept of deduction and the Chinese remainder theorem . RMS is determined by a set of pairs of mutually simple modules. $(m_{1},\,m_{2},\,\dots ,\,m_{n})$ ${\ displaystyle (m_ {1}, \, m_ {2}, \, \ dots, \, m_ {n})}$ ${\ displaystyle (m_ {1}, \, m_ {2}, \, \ dots, \, m_ {n})}$ that is, such that $\gcd(m_{i},\,m_{j})=1$ ${\ displaystyle \ gcd (m_ {i}, \, m_ {j}) = 1}$ ${\ displaystyle \ gcd (m_ {i}, \, m_ {j}) = 1}$ $(i,\,j=0,\,1,\,\dots ,\,n;\ i\neq j)$ ${\ displaystyle (i, \, j = 0, \, 1, \, \ dots, \, n; \ i \ neq j)}$ ${\ displaystyle (i, \, j = 0, \, 1, \, \ dots, \, n; \ i \ neq j)}$ called basis and product $M=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n},$ ${\ displaystyle M = m_ {1} \ cdot m_ {2} \ cdot \ ldots \ cdot m_ {n},}$ ${\ displaystyle M = m_ {1} \ cdot m_ {2} \ cdot \ ldots \ cdot m_ {n},}$ so that every integer $x$ ${\ displaystyle x}$ $x$ from the segment $[0,\ M-1]$ ${\ displaystyle [0, \ M-1]}$ ${\ displaystyle [0, \ M-1]}$ set of deductions matched $(x_{1},\,x_{2},\,\dots ,\,x_{n})$ ${\ displaystyle (x_ {1}, \, x_ {2}, \, \ dots, \, x_ {n})}$ ${\ displaystyle (x_ {1}, \, x_ {2}, \, \ dots, \, x_ {n})}$ where

x_{1}\equiv x{\pmod {m_{1}}};

{\ displaystyle x_ {1} \ equiv x {\ pmod {m_ {1}}};}

{\ displaystyle x_ {1} \ equiv x {\ pmod {m_ {1}}};}

x_{2}\equiv x{\pmod {m_{2}}};

{\ displaystyle x_ {2} \ equiv x {\ pmod {m_ {2}}};}

{\ displaystyle x_ {2} \ equiv x {\ pmod {m_ {2}}};}

\dots \dots \dots \dots \dots \dots \dots

{\ displaystyle \ dots \ dots \ dots \ dots \ dots \ dots \ dots}

{\ displaystyle \ dots \ dots \ dots \ dots \ dots \ dots \ dots}

x_{n}\equiv x{\pmod {m_{n}}}.

{\ displaystyle x_ {n} \ equiv x {\ pmod {m_ {n}}}.}

{\ displaystyle x_ {n} \ equiv x {\ pmod {m_ {n}}}.}

Moreover, the Chinese theorem on residuals guarantees the uniqueness (uniqueness) of the representation of non-negative integers from the segment $[0,\ M-1]$ ${\ displaystyle [0, \ M-1]}$ ${\ displaystyle [0, \ M-1]}$ .

Content

Benefits of the residual class system

In the SOC the arithmetic operations (addition, subtraction, multiplication, division) are performed componentwise, if the result is known that it is integer and also lies in $[0,M-1]$ ${\ displaystyle [0, M-1]}$ .

Formula for addition: $(x_{1},x_{2},\dots ,x_{n})+(y_{1},y_{2},\dots ,y_{n})=(z_{1},z_{2},\dots ,z_{n})$ ${\ displaystyle (x_ {1}, x_ {2}, \ dots, x_ {n}) + (y_ {1}, y_ {2}, \ dots, y_ {n}) = (z_ {1}, z_ {2}, \ dots, z_ {n})}$ where

z_{1}\equiv (x_{1}+y_{1}){\pmod {m_{1}}};

{\ displaystyle z_ {1} \ equiv (x_ {1} + y_ {1}) {\ pmod {m_ {1}}};}

z_{2}\equiv (x_{2}+y_{2}){\pmod {m_{2}}};

{\ displaystyle z_ {2} \ equiv (x_ {2} + y_ {2}) {\ pmod {m_ {2}}}}

\dots \dots \dots \dots \dots \dots \dots \dots \dots

{\ displaystyle \ dots \ dots \ dots \ dots \ dots \ dots \ dots \ dots \ dots}

z_{n}\equiv (x_{n}+y_{n}){\pmod {m_{n}}}.

{\ displaystyle z_ {n} \ equiv (x_ {n} + y_ {n}) {\ pmod {m_ {n}}}.}

Similarly, subtraction, multiplication and division are performed. Note : the division imposes additional restrictions. The division must be integer, that is, the divisor must completely divide the dividend. The divider must be mutually simple with all modules of the basis.

Disadvantages of the residual class system

lack of efficient algorithms for comparing numbers; Usually, the comparison is carried out by transferring the arguments from the RNS to the number system (polyadic) with mixed bases: $m_{1},m_{1}m_{2},\dots ,m_{1}m_{2}\dots m_{n-1}$ ${\ displaystyle m_ {1}, m_ {1} m_ {2}, \ dots, m_ {1} m_ {2} \ dots m_ {n-1}}$ ;
slow algorithms for the mutual conversion of the representation of numbers from the positional number system to the SOC and vice versa;
complex division algorithms (when the result is not integer);
difficulty in detecting overflow.

Application of residual class system

JUICE is widely used in microelectronics in specialized DSP devices where it is required:

error control due to the introduction of additional redundant modules;
high speed of work, which provides a parallel implementation of the basic arithmetic operations;
information security .

Practical application: Czechoslovak tube EPOS computer , Soviet military multiprocessor supercomputer 5E53 , designed to solve the missile defense tasks.

Special module systems

In modular arithmetic, there are special sets of modules that allow you to partially level the flaws and for which there are effective algorithms for comparing numbers and for the direct and reverse translation of modular numbers into a positional number system. One of the most popular module systems is a set of three pairwise mutually simple numbers of the form {2 ⁿ −1, 2 ⁿ , 2 ⁿ +1} .

Example

Consider a SOC with basis $(2;3;5)$ ${\ displaystyle (2; 3; 5)}$ . In this basis, one can represent numbers from the interval from $0$ ${\ displaystyle 0}$ before $29$ ${\ displaystyle 29}$ , because $M=2\times 3\times 5=30$ ${\ displaystyle M = 2 \ times 3 \ times 5 = 30}$ . Table of correspondence of numbers from the positional number system and the residual class system

$0=(0;0;0)$ ${\ displaystyle 0 = (0; 0; 0)}$	$1=(1;1;1)$ ${\ displaystyle 1 = (1; 1; 1)}$	$2=(0;2;2)$ ${\ displaystyle 2 = (0; 2; 2)}$	$3=(1;0;3)$ ${\ displaystyle 3 = (1; 0; 3)}$	$4=(0;1;4)$ ${\ displaystyle 4 = (0; 1; 4)}$
$5=(1;2;0)$ ${\ displaystyle 5 = (1; 2; 0)}$	$6=(0;0;1)$ ${\ displaystyle 6 = (0; 0; 1)}$	$7=(1;1;2)$ ${\ displaystyle 7 = (1; 1; 2)}$	$8=(0;2;3)$ ${\ displaystyle 8 = (0; 2; 3)}$	$9=(1;0;4)$ ${\ displaystyle 9 = (1; 0; 4)}$
$10=(0;1;0)$ ${\ displaystyle 10 = (0; 1; 0)}$	$11=(1;2;1)$ ${\ displaystyle 11 = (1; 2; 1)}$	$12=(0;0;2)$ ${\ displaystyle 12 = (0; 0; 2)}$	$13=(1;1;3)$ ${\ displaystyle 13 = (1; 1; 3)}$	$14=(0;2;4)$ ${\ displaystyle 14 = (0; 2; 4)}$
$15=(1;0;0)$ ${\ displaystyle 15 = (1; 0; 0)}$	$16=(0;1;1)$ ${\ displaystyle 16 = (0; 1; 1)}$	$17=(1;2;2)$ ${\ displaystyle 17 = (1; 2; 2)}$	$18=(0;0;3)$ ${\ displaystyle 18 = (0; 0; 3)}$	$19=(1;1;4)$ ${\ displaystyle 19 = (1; 1; 4)}$
$20=(0;2;0)$ ${\ displaystyle 20 = (0; 2; 0)}$	$21=(1;0;1)$ ${\ displaystyle 21 = (1; 0; 1)}$	$22=(0;1;2)$ ${\ displaystyle 22 = (0; 1; 2)}$	$23=(1;2;3)$ ${\ displaystyle 23 = (1; 2; 3)}$	$24=(0;0;4)$ ${\ displaystyle 24 = (0; 0; 4)}$
$25=(1;1;0)$ ${\ displaystyle 25 = (1; 1; 0)}$	$26=(0;2;1)$ ${\ displaystyle 26 = (0; 2; 1)}$	$27=(1;0;2)$ ${\ displaystyle 27 = (1; 0; 2)}$	$28=(0;1;3)$ ${\ displaystyle 28 = (0; 1; 3)}$	$29=(1;2;4)$ ${\ displaystyle 29 = (1; 2; 4)}$

Addition Example

Add two numbers 9 and 14 in basis $(2;3;5)$ ${\ displaystyle (2; 3; 5)}$ . Their representation in a given basis $9=(1;0;4)$ ${\ displaystyle 9 = (1; 0; 4)}$ and $14=(0;2;4)$ ${\ displaystyle 14 = (0; 2; 4)}$ (see plate above). We use the formula for addition: $(z_{1},z_{2},z_{3})=(1,0,4)+(0,2,4)$ ${\ displaystyle (z_ {1}, z_ {2}, z_ {3}) = (1,0,4) + (0,2,4)}$

z_{1}\equiv (x_{1}+y_{1}){\pmod {m_{1}}}\equiv (1+0){\pmod {2}}=1;

{\ displaystyle z_ {1} \ equiv (x_ {1} + y_ {1}) {\ pmod {m_ {1}}} \ equiv (1 + 0) {\ pmod {2}} = 1;}

z_{2}\equiv (x_{2}+y_{2}){\pmod {m_{2}}}\equiv (0+2){\pmod {3}}=2;

{\ displaystyle z_ {2} \ equiv (x_ {2} + y_ {2}) {\ pmod {m_ {2}}} \ equiv (0 + 2) {\ pmod {3}} = 2;}

z_{3}\equiv (x_{3}+y_{3}){\pmod {m_{3}}}\equiv (4+4){\pmod {5}}=3;

{\ displaystyle z_ {3} \ equiv (x_ {3} + y_ {3}) {\ pmod {m_ {3}}} \ equiv (4 + 4) {\ pmod {5}} = 3;}

$(z_{1},z_{2},z_{3})=(1,2,3)$ ${\ displaystyle (z_ {1}, z_ {2}, z_ {3}) = (1,2,3)}$ - according to the table we are convinced that the result is equal to 23.

Multiplication Example

Multiply two numbers 4 and 5 in the basis $(2;3;5)$ ${\ displaystyle (2; 3; 5)}$ . Their representation in a given basis $4=(0;1;4)$ ${\ displaystyle 4 = (0; 1; 4)}$ and $5=(1;2;0)$ ${\ displaystyle 5 = (1; 2; 0)}$ (see plate above). We use the formula for multiplication: $(z_{1},z_{2},z_{3})=(0,1,4)*(1,2,0)$ ${\ displaystyle (z_ {1}, z_ {2}, z_ {3}) = (0,1,4) * (1,2,0)}$

z_{1}\equiv (x_{1}*y_{1}){\pmod {m_{1}}}\equiv (0*1){\pmod {2}}=0;

{\ displaystyle z_ {1} \ equiv (x_ {1} * y_ {1}) {\ pmod {m_ {1}}} \ equiv (0 * 1) {\ pmod {2}} = 0;}

z_{2}\equiv (x_{2}*y_{2}){\pmod {m_{2}}}\equiv (1*2){\pmod {3}}=2;

{\ displaystyle z_ {2} \ equiv (x_ {2} * y_ {2}) {\ pmod {m_ {2}}} \ equiv (1 * 2) {\ pmod {3}} = 2;}

z_{3}\equiv (x_{3}*y_{3}){\pmod {m_{3}}}\equiv (4*0){\pmod {5}}=0;

{\ displaystyle z_ {3} \ equiv (x_ {3} * y_ {3}) {\ pmod {m_ {3}}} \ equiv (4 * 0) {\ pmod {5}} = 0;}

$(z_{1},z_{2},z_{3})=(0,2,0)$ ${\ displaystyle (z_ {1}, z_ {2}, z_ {3}) = (0,2,0)}$ - according to the table we are convinced that the result is equal to 20.

Note: if we multiplied or added the numbers that gave a multiplication number greater than or equal $M=30$ ${\ displaystyle M = 30}$ then the result $RES\equiv REAL{\pmod {M}}$ ${\ displaystyle RES \ equiv REAL {\ pmod {M}}}$ where $R E A L$ ${\ displaystyle REAL}$ - the result of the operation in the positional number system.

Example of division, provided that the division is entirely

The division can be performed in the same way as multiplication, but only if the divisor divides the dividend completely, without a remainder.
For modules $(29;31;32)$ ${\ displaystyle (29; 31; 32)}$ divide the number 1872 by 9.
Divide $1872=(16;12;16)$ ${\ displaystyle 1872 = (16; 12; 16)}$ on $9=(9;9;9)$ ${\ displaystyle 9 = (9; 9; 9)}$ .

We use the formula
$z_{i}\equiv (x_{i}*y_{i}^{-1}){\pmod {m_{i}}}.$ ${\ displaystyle z_ {i} \ equiv (x_ {i} * y_ {i} ^ {- 1}) {\ pmod {m_ {i}}}.}$

Here I must say that $y_{i}^{-1}*y_{i}=1{\pmod {m_{i}}}$ ${\ displaystyle y_ {i} ^ {- 1} * y_ {i} = 1 {\ pmod {m_ {i}}}}$ that is not the same thing as simply sharing $x$ ${\ displaystyle x}$ on $y$ ${\ displaystyle y}$ .
According to the formula $y_{i}^{m_{i}-1}=1{\pmod {m_{i}}}$ ${\ displaystyle y_ {i} ^ {m_ {i} -1} = 1 {\ pmod {m_ {i}}}}$ we get:
$9^{29-2}{\pmod {29}}=13,$ ${\ displaystyle 9 ^ {29-2} {\ pmod {29}} = 13,}$
$9^{31-2}{\pmod {31}}=7.$ ${\ displaystyle 9 ^ {31-2} {\ pmod {31}} = 7.}$
$9^{32-2}{\pmod {32}}=17;$ ${\ displaystyle 9 ^ {32-2} {\ pmod {32}} = 17;}$

$z_{1}\equiv (16*13){\pmod {29}}=5,$ ${\ displaystyle z_ {1} \ equiv (16 * 13) {\ pmod {29}} = 5,}$
$z_{2}\equiv (12*7){\pmod {31}}=22,$ ${\ displaystyle z_ {2} \ equiv (12 * 7) {\ pmod {31}} = 22,}$
$z_{3}\equiv (16*17){\pmod {32}}=16.$ ${\ displaystyle z_ {3} \ equiv (16 * 17) {\ pmod {32} = 16.}$

This is the correct result - the number 208. However, this result can be obtained only if it is known that the division is made without a remainder.

Literature

Akushsky I.Ya. , Yuditsky D.I. Machine arithmetic in residual classes . - Owls. Radio , 1968. - 439 p.
Torgashev, Valery Antonovich. System of residual classes and reliability of digital computers . - M .: Owls. Radio , 1973. - 118 p.
Amerbayev V.M. Theoretical foundations of machine arithmetic . - Academy of Sciences of the Kazakh SSR, Institute of Mathematics and Mechanics. Alma-Ata: Science , 1976. - 324 p.
O. Finko. Modular arithmetic of parallel logical calculations : monograph - Moscow : Institute of Control Sciences , Russian Academy of Sciences , 2003. - 214 p.
<a href=" https://wikidata.org/wiki/Track:Q28500761 "> </a> <a href=" https://wikidata.org/wiki/Track:Q53341250 "> </a> <a href = " https://wikidata.org/wiki/Track:Q16690205 "> </a>
Jubilee International Scientific and Technical Conference "50 years of modular arithmetic . " - JSC Angstrem , MIET . - November 23-25, 2005; Moscow, Zelenograd: FIZMATLIT , 2006. - 775 p. - ISBN ISBN 5-7256-0409-8 .
Amos Omondi, Benjamin Premkumar. Residue Number Systems: Theory and Implementation . - 57 Shelton Street Covent Garden London: Imperial College Press , 2007. - 296 p. - ISBN 978-1-86094-866-4 .
Chervyakov N. I., Evdokimov A. A., Galushkin A. I. , Lavrinenko I.N. and others. The use of artificial neural networks and the system of residual classes in cryptography . - M .: FIZMATLIT , 2012. - 280 p. - ISBN 978-5-9221-1386-1 .
Ananda Mohan, PV Residue Number Systems. - Cham: Springer International Publishing , 2016. - 351 p. - ISBN 978-3-319-41385-3 .
Amir Sabbagh, Molahosseini, Leonel Seabra de Sousa, and Chip-Hong Chang (editors). Embedded Systems Design with Special Arithmetic and Number Systems. - Cham: Springer International Publishing , 21 March 2017. - 389 p. - ISBN 978-3-319-49742-6 .

Links

The article "Modular arithmetic" in the Great Russian Encyclopedia