Restklasssystem

Residual class system (SOC) ( engelsk restnummersystem ) är ett talsystem baserat på modulär aritmetik .

Representationen av ett tal i restklassens system baseras på begreppet rest och den kinesiska restsatsen . RNS bestäms av en uppsättning parvisa coprime -moduler , det vill säga sådana som kallas en bas, och en produkt så att varje heltal från segmentet är associerat med en uppsättning rester , där $(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))}.

Samtidigt garanterar den kinesiska restsatsen det unika (unika) i representationen av icke-negativa heltal från intervallet . $[0,\M-1]$

Fördelar med restklasssystemet

I RNS utförs aritmetiska operationer (addition, subtraktion, multiplikation, division) komponent för komponent om resultatet är känt för att vara ett heltal och även ligger i . $[0,M-1]$

Tilläggsformel: var $(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))}.

Subtraktion, multiplikation och division utförs på liknande sätt. Obs : Det finns ytterligare restriktioner för division. Divisionen måste vara ett heltal, det vill säga divisorn måste dividera utdelningen med ett heltal. Divisorn måste vara coprime med alla moduler i basen.

Nackdelar med restklasssystemet

brist på effektiva algoritmer för att jämföra siffror; Vanligtvis utförs jämförelsen genom att översätta argumenten från RNS till talsystemet (polyadiskt) med blandade baser: ; ${\displaystyle m_{1},m_{1}m_{2},\dots ,m_{1}m_{2}\dots m_{n-1))$
långsamma algoritmer för ömsesidig transformation av representationen av tal från positionsnummersystemet till RNS och vice versa;
komplexa divisionsalgoritmer (när resultatet inte är ett heltal);
svårigheter att upptäcka översvämning.

Tillämpning av restklasssystemet

SOC används i stor utsträckning inom mikroelektronik i specialiserade DSP- enheter , där det krävs:

felkontroll genom att införa ytterligare redundanta moduler;
hög hastighet, som tillhandahålls av parallell implementering av grundläggande aritmetiska operationer;
informationssäkerhet .

Praktisk tillämpning: Tjeckoslovakisk vakuumrördator "EPOS" , sovjetisk militär multiprocessor superdator 5E53 , designad för att lösa missilförsvarsproblem .

Specialmodulsystem

Inom modulär aritmetik finns det speciella uppsättningar av moduler som gör att du delvis kan utjämna bristerna och för vilka det finns effektiva algoritmer för att jämföra tal och för direkt och omvänd översättning av modulära tal till ett positionsnummersystem. Ett av de mest populära modulsystemen är en uppsättning av tre parvisa samprimtal av formen {2 n −1, 2 n , 2 n +1} .

Exempel

Överväg en RNS med grund . I denna bas är det möjligt att representera tal från intervallet från till en-till-ett , eftersom . Korrespondenstabell med tal från positionsnummersystemet och systemet med restklasser: $(2;3;5)$ $0$ $29$ $M=2\ gånger 3\ gånger 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)$

Exempel på tillägg

Låt oss lägga till två siffror 9 och 14 i basen . Deras representation i den givna grunden och (se tabellen ovan). Låt oss använda formeln för addition: $(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)$ - enligt tabellen ser vi till att resultatet blir 23.

Multiplikationsexempel

Multiplicera två siffror 4 och 5 i grund . Deras representation i den givna grunden och (se plattan ovan). Låt oss använda formeln för multiplikation: $(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)$ – enligt tabellen ser vi till att resultatet blir 20.

Notera: om vi skulle multiplicera eller lägga till tal som gav ett tal större än eller lika med som ett resultat av multiplikation, då är det erhållna resultatet, där är resultatet av operationen i positionsnummersystemet. $M=30$ $RES\equiv REAL{\pmod {M}}$ $REAL$

Ett exempel på division, förutsatt att heltalsdivision är möjlig

Division kan utföras på samma sätt som multiplikation, men bara om divisorn delar utdelningen jämnt, utan rest.
För moduler , dividera talet 1872 med 9. Dividera med . $(29;31;32)$
$1872=(16;12;16)$ $9=(9;9;9)$

Låt oss använda formeln
$z_{i}\equiv (x_{i}*y_{i}^{-1}){\pmod {m_{i}}}.$

Här måste det sägas att , vilket inte är detsamma som att bara dividera med . Enligt formeln får vi: ${\displaystyle y_{i}^{-1}*y_{i}=1{\pmod {m_{i))))$ $x$ $y$
${\displaystyle 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.$

Detta är det korrekta resultatet - siffran 208. Ett sådant resultat kan dock endast erhållas om det är känt att divisionen utförs utan en rest.

Se även

Litteratur

Akushsky I.Ya. , Yuditsky D.I. Maskinaritmetik i restklasser . - Ugglor. radio , 1968. - 439 sid.
Torgashev, Valery Antonovich. System av restklasser och datorers tillförlitlighet . - M . : Sov. radio , 1973. - 118 sid.
Amerbaev V.M. Teoretiska grunder för maskinaritmetik . - Vetenskapsakademin i den kazakiska SSR, Institutet för matematik och mekanik. Alma-Ata: Science , 1976. - 324 sid.
Finko O. A. Modulär aritmetik för parallella logiska beräkningar : Monografi - M .: IPU RAS , 2003. - 214 sid.
Jubileum Internationell vetenskaplig och teknisk konferens "50 år av modulär aritmetik" . - OJSC "Angstrem" , MIET . - 23-25 november 2005; Moskva, Zelenograd: FIZMATLIT , 2006. - 775 s. — ISBN ISBN 5-7256-0409-8 .
Amos Omondi, Benjamin Premkumar. Restnummersystem: teori och implementering . - 57 Shelton Street Covent Garden London: Imperial College Press , 2007. - 296 sid. - ISBN 978-1-86094-866-4 .
Chervyakov N. I., Evdokimov A. A., Galushkin A. I. , Lavrinenko IN et al. Tillämpning av artificiella neurala nätverk och system av kvarvarande klasser i kryptografi . — M .: FIZMATLIT , 2012. — 280 sid. - ISBN 978-5-9221-1386-1 .
Ananda Mohan, PV Residue Number Systems. - Cham: Springer International Publishing , 2016. - 351 sid. - ISBN 978-3-319-41385-3 .
Amir Sabbagh, Molahosseini, Leonel Seabra de Sousa och Chip-Hong Chang (redaktörer). Design av inbyggda system med speciella aritmetiska och talsystem. - Cham: Springer International Publishing , 21 mars 2017. - 389 sid. — ISBN 978-3-319-49742-6 .

Länkar

Artikel "Modulär aritmetik" i Great Russian Encyclopedia