Sistemul de clase reziduale

Sistemul de clasă reziduală (SOC) ( în engleză sistem de numere reziduale ) este un sistem de numere bazat pe aritmetică modulară .

Reprezentarea unui număr în sistemul de clase de rest se bazează pe conceptul de reziduu și teorema chineză a restului . RNS este determinat de un set de module coprime în perechi , adică astfel încât , numită bază și un produs, astfel încât fiecare număr întreg din segment să fie asociat cu un set de reziduuri , unde $(m_{1},\,m_{2},\,\dots,\,m_{n})$ $\gcd(m_{i},\,m_{j})=1$ $(i,\,j=0,\,1,\,\dots ,\,n;\i\neq j)$ $M=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n},$ $X$ $[0,\M-1]$ $(x_{1},\,x_{2},\,\dots ,\,x_{n})$

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

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

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

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

În același timp, teorema chineză a restului garantează unicitatea (unicitatea) reprezentării numerelor întregi nenegative din intervalul . $[0,\M-1]$

Beneficiile sistemului de clase reziduale

În RNS, operațiile aritmetice (adunare, scădere, înmulțire, împărțire) sunt efectuate component cu component dacă se știe că rezultatul este un număr întreg și se află și în . $[0,M-1]$

Formula de adunare: unde $(x_{1},x_{2},\dots,x_{n})+(y_{1},y_{2},\dots,y_{n})=(z_{1},z_ {2},\dots ,z_{n})$

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

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

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

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

Scăderea, înmulțirea și împărțirea se efectuează în mod similar. Notă : Există restricții suplimentare privind împărțirea. Împărțirea trebuie să fie un număr întreg, adică divizorul trebuie să împartă dividendul la un număr întreg. Divizorul trebuie să fie coprim cu toate modulele bazei.

Dezavantajele sistemului de clase reziduale

lipsa algoritmilor eficienți pentru compararea numerelor; De obicei, comparația se realizează prin traducerea argumentelor din RNS în sistemul numeric (poliadic) cu baze mixte: ; ${\displaystyle m_{1},m_{1}m_{2},\dots ,m_{1}m_{2}\dots m_{n-1))$
algoritmi lenți pentru transformarea reciprocă a reprezentării numerelor din sistemul numeric pozițional în RNS și invers;
algoritmi de divizare complecși (când rezultatul nu este un număr întreg);
dificultate în detectarea preaplinului.

Aplicarea sistemului de clase reziduale

SOC este utilizat pe scară largă în microelectronică în dispozitive DSP specializate , unde este necesar:

controlul erorilor prin introducerea de module suplimentare redundante;
viteză mare, care este asigurată de implementarea în paralel a operațiilor aritmetice de bază;
securitatea informatiei .

Aplicație practică: computer cehoslovac cu tub vid „EPOS” , supercomputer multiprocesor militar sovietic 5E53 , conceput pentru a rezolva problemele de apărare antirachetă .

Sisteme de module speciale

În aritmetica modulară, există seturi speciale de module care vă permit să nivelați parțial deficiențele și pentru care există algoritmi eficienți pentru compararea numerelor și pentru traducerea directă și inversă a numerelor modulare într-un sistem numeric pozițional. Unul dintre cele mai populare sisteme de module este un set de trei numere coprime în perechi de forma {2 n −1, 2 n , 2 n +1} .

Exemplu

Luați în considerare un RNS cu bază . În această bază, este posibil să se reprezinte numere din intervalul de la unu-la-unu , deoarece . Tabelul de corespondență al numerelor din sistemul numeric pozițional și sistemul claselor reziduale: $(2;3;5)$ $0$ $29$ $M=2\times 3\times 5=30$

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

Exemplu de adăugare

Să adăugăm două numere 9 și 14 în bază . Reprezentarea lor în baza dată și (vezi tabelul de mai sus). Să folosim formula pentru adunare: $(2;3;5)$ $9=(1;0;4)$ $14=(0;2;4)$ $(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;

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;

$(z_{1},z_{2},z_{3})=(1,2,3)$ - conform tabelului, ne asigurăm că rezultatul este 23.

Exemplu de multiplicare

Înmulțiți două numere 4 și 5 în bază . Reprezentarea lor în baza dată și (vezi placa de mai sus). Să folosim formula de înmulțire: $(2;3;5)$ $4=(0;1;4)$ $5=(1;2;0)$ $(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;

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;

$(z_{1},z_{2},z_{3})=(0,2,0)$ - conform tabelului, ne asigurăm că rezultatul este 20.

Notă: dacă ar fi să înmulțim sau să adunăm numere care au dat un număr mai mare sau egal cu ca rezultat al înmulțirii, atunci rezultatul obținut, unde este rezultatul operației în sistemul numeric pozițional. $M=30$ $RES\equiv REAL{\pmod {M}}$ $REAL$

Un exemplu de împărțire, presupunând că este posibilă împărțirea întregului

Împărțirea poate fi efectuată în același mod ca și înmulțirea, dar numai dacă împărțitorul împarte dividendul în mod egal, fără rest.
Pentru module , împărțiți numărul 1872 la 9. Împărțiți cu . $(29;31;32)$
$1872=(16;12;16)$ $9=(9;9;9)$

Să folosim formula
$z_{i}\equiv (x_{i}*y_{i}^{-1}) {\pmod {m_{i}}}.$

Aici trebuie spus că , ceea ce nu este același lucru cu simpla împărțire la . După formula obținem: $y_{i}^{-1}*y_{i}=1{\pmod {m_{i)))$ $X$ $y$
$y_{i}^{m_{i}-1}=1{\pmod {m_{i)))$
$9^{29-2}{\pmod {29}}=13,$
$9^{31-2}{\pmod {31}}=7.$
$9^{32-2}{\pmod {32}}=17;$

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

Acesta este rezultatul corect - numărul 208. Cu toate acestea, un astfel de rezultat poate fi obținut numai dacă se știe că împărțirea se efectuează fără rest.

Vezi și

Literatură

Akushsky I.Ya. , Yuditsky D.I. Aritmetica mașinii în clase reziduale . - Bufniţe. radio , 1968. - 439 p.
Torgashev, Valery Antonovici. Sistemul claselor reziduale și fiabilitatea calculatoarelor . - M . : Sov. radio , 1973. - 118 p.
Amerbaev V.M. Fundamentele teoretice ale aritmeticii mașinilor . - Academia de Științe a RSS Kazahului, Institutul de Matematică și Mecanică. Alma-Ata: Știință , 1976. - 324 p.
Finko O. A. Aritmetica modulară a calculelor logice paralele : Monografie - M .: IPU RAS , 2003. - 214 p.
Aniversare Conferința științifică și tehnică internațională „50 de ani de aritmetică modulară” . - OJSC „Angstrem” , MIET . - 23-25 noiembrie 2005; Moscova, Zelenograd: FIZMATLIT , 2006. - 775 p. — ISBN ISBN 5-7256-0409-8 .
Amos Omondi, Benjamin Premkumar. Sisteme de numărare a reziduurilor: teorie și implementare . - 57 Shelton Street Covent Garden Londra: Imperial College Press , 2007. - 296 p. - ISBN 978-1-86094-866-4 .
Chervyakov N. I., Evdokimov A. A., Galushkin A. I. , Lavrinenko IN et al. Aplicarea rețelelor neuronale artificiale și a sistemului de clase reziduale în criptografie . — M .: FIZMATLIT , 2012. — 280 p. - ISBN 978-5-9221-1386-1 .
Ananda Mohan, Sisteme de numărare a reziduurilor fotovoltaice. - Cham: Springer International Publishing , 2016. - 351 p. - ISBN 978-3-319-41385-3 .
Amir Sabbagh, Molahosseini, Leonel Seabra de Sousa și Chip-Hong Chang (editori). Proiectare de sisteme încorporate cu sisteme speciale de aritmetică și numere. - Cham: Springer International Publishing , 21 martie 2017. - 389 p. — ISBN 978-3-319-49742-6 .

Link -uri

Articolul „Aritmetică modulară” în Marea Enciclopedie Rusă