Jäännösluokkajärjestelmä

Jäännösluokkajärjestelmä (SOC) ( englanniksi jäännösnumerojärjestelmä ) on modulaariseen aritmetiikkaan perustuva numerojärjestelmä .

Lukujen esitys jäännösluokkajärjestelmässä perustuu jäännöksen käsitteeseen ja kiinalaiseen jäännöslauseeseen . RNS määritetään joukolla parittaisia koprime - moduuleja , eli siten, että , kutsutaan kantaksi, ja tulo siten, että segmentin jokainen kokonaisluku liittyy jäännösjoukkoon , jossa $(m_{1},\,m_{2},\,\dots ,\,m_{n})$ $\gcd(m_{i},\,m_{j})=1$ ${\näyttötyyli (i,\,j=0,\,1,\,\pisteet ,\,n;\ i\neq j)}$ $M=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n},$ $x$ ${\näyttötyyli [0,\M-1]}$ $(x_{1},\,x_{2},\,\dots ,\,x_{n})$

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

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

{\näyttötyyli \pisteet \pisteet \pisteet \pisteet \pisteet \pisteet \pisteet }

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

Samalla kiinalainen jäännöslause takaa ei-negatiivisten kokonaislukujen esityksen ainutlaatuisuuden (yksilöllisyyden) väliltä . ${\näyttötyyli [0,\M-1]}$

Jäännösluokkajärjestelmän edut

RNS:ssä aritmeettiset operaatiot (yhteen-, vähennys-, kerto- ja jakolasku) suoritetaan komponentti kerrallaan, jos tuloksen tiedetään olevan kokonaisluku ja se on myös . $[0,M-1]$

Lisäyskaava: missä $(x_{1},x_{2},\dots ,x_{n})+(y_{1},y_{2},\dots ,y_{n})=(z_{1},z_ {2},\pisteet ,z_{n})$

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

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

{\näyttötyyli \pisteet \pisteet \pisteet \pisteet \pisteet \pisteet \pisteet \pisteet \pisteet}

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

Vähentäminen, kertominen ja jako suoritetaan samalla tavalla. Huomautus : Jaossa on lisärajoituksia. Jaon tulee olla kokonaisluku, eli jakajan on jaettava osinko kokonaisluvulla. Jakajan tulee olla koprime kaikkien kantan moduulien kanssa.

Jäännösluokkajärjestelmän haitat

tehokkaiden lukujen vertailualgoritmien puute; Yleensä vertailu suoritetaan kääntämällä argumentit RNS:stä numerojärjestelmään (polyadic) sekapohjaisilla: ; ${\displaystyle m_{1},m_{1}m_{2},\dots ,m_{1}m_{2}\dots m_{n-1))$
hitaat algoritmit lukujen esityksen keskinäiseen muuntamiseen paikkalukujärjestelmästä RNS:ään ja päinvastoin;
monimutkaiset jakoalgoritmit (kun tulos ei ole kokonaisluku);
vaikeuksia havaita ylivuoto.

Jäännösluokkajärjestelmän soveltaminen

SOC:ta käytetään laajasti mikroelektroniikassa erikoistuneissa DSP -laitteissa , joissa sitä tarvitaan:

virheenhallinta ottamalla käyttöön ylimääräisiä redundantteja moduuleja;
suuri nopeus, joka saadaan aikaan aritmeettisten perusoperaatioiden rinnakkaisella toteutuksella;
tietoturva .

Käytännön sovellus: Tšekkoslovakian tyhjiöputkitietokone "EPOS" , Neuvostoliiton armeijan moniprosessorinen supertietokone 5E53 , suunniteltu ratkaisemaan ohjuspuolustusongelmia .

Erikoismoduulijärjestelmät

Modulaarisessa aritmetiikassa on erityisiä moduulisarjoja, joiden avulla voit osittain tasoittaa puutteet ja joihin on olemassa tehokkaita algoritmeja lukujen vertailuun ja modulaaristen lukujen suora- ja käänteismuuntamiseen paikkalukujärjestelmäksi. Yksi suosituimmista moduulijärjestelmistä on kolmen parittaisen koprime-luvun joukko , jotka ovat muotoa {2 n −1, 2 n , 2 n +1} .

Esimerkki

Harkitse RNS:ää, jonka perusta on . Tällä perusteella on mahdollista esittää numeroita väliltä yksi yhteen , koska . Paikkalukujärjestelmän ja jäännösluokkien järjestelmän numeroiden vastaavuustaulukko: $(2;3;5)$ $0$ $29$ $M=2\kertaa 3\kertaa 5=30$

$0=(0;0;0)$	${\näyttötyyli 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)$

Lisäysesimerkki

Lisätään perusteeseen kaksi lukua 9 ja 14 . Niiden edustus annetulla pohjalla ja (katso taulukko yllä). Käytämme kaavaa summaukseen: $(2;3;5)$ $9=(1;0;4)$ $14=(0;2;4)$ ${\näyttötyyli (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;

${\näyttötyyli (z_{1},z_{2},z_{3})=(1,2,3)}$ - taulukon mukaan varmistamme, että tulos on 23.

Kertoesimerkki

Kerro kaksi lukua 4 ja 5 perusteella . Niiden edustus annetulla pohjalla ja (katso yllä olevaa levyä). Käytämme kertomiseen kaavaa: $(2;3;5)$ $4=(0;1;4)$ $5=(1;2;0)$ ${\näyttötyyli (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;

${\näyttötyyli (z_{1},z_{2},z_{3})=(0,2,0)}$ - taulukon mukaan varmistamme, että tulos on 20.

Huomaa: jos kerrottaisiin tai laskettaisiin yhteen luvut, jotka kertomisen tuloksena antoivat luvun, joka on suurempi tai yhtä suuri kuin, niin saatu tulos, jossa on paikannuslukujärjestelmän operaation tulos. $M=30$ $RES\equiv REAL{\pmod {M}}$ $REAL$

Esimerkki jaosta, olettaen että kokonaislukujako on mahdollista

Jako voidaan suorittaa samalla tavalla kuin kertolasku, mutta vain, jos jakaja jakaa osingon tasaisesti, ilman jäännöstä.
Moduulien kohdalla jaa luku 1872 9 :llä. Jaa luvulla . $(29;31;32)$
$1872=(16;12;16)$ $9=(9;9;9)$

Käytetään kaavaa
$z_{i}\equiv (x_{i}*y_{i}^{-1}){\pmod {m_{i}}}.$

Tässä on sanottava, että , mikä ei ole sama asia kuin yksinkertaisesti jakaminen . Kaavan mukaan saamme: ${\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.$

Tämä on oikea tulos - numero 208. Tällainen tulos voidaan kuitenkin saada vain, jos tiedetään, että jako suoritetaan ilman jäännöstä.

Katso myös

Kirjallisuus

Akushsky I.Ya. , Yuditsky D.I. Koneen aritmetiikka jäännösluokissa . - Pöllöt. radio , 1968. - 439 s.
Torgašev, Valeri Antonovich. Jäännösluokkien järjestelmä ja tietokoneiden luotettavuus . - M . : Sov. radio , 1973. - 118 s.
Amerbaev V.M. Konearitmeettisen teoreettiset perusteet . - Kazakstanin SSR:n tiedeakatemia, matematiikan ja mekaniikan instituutti. Alma-Ata: Tiede , 1976. - 324 s.
Finko O. A. Rinnakkaisten loogisten laskutoimitusten modulaarinen aritmetiikka : Monografia - M .: IPU RAS , 2003. - 214 s.
Vuosipäivä Kansainvälinen tieteellinen ja tekninen konferenssi "50 vuotta modulaarista aritmetiikkaa" . - OJSC "Angstrem" , MIET . - 23.–25. marraskuuta 2005; Moskova, Zelenograd: FIZMATLIT , 2006. - 775 s. — ISBN ISBN 5-7256-0409-8 .
Amos Omondi, Benjamin Premkumar. Jäännösnumerojärjestelmät: teoria ja toteutus . - 57 Shelton Street Covent Garden London: Imperial College Press , 2007. - 296 s. - ISBN 978-1-86094-866-4 .
Chervyakov N. I., Evdokimov A. A., Galushkin A. I. , Lavrinenko IN et al. Keinotekoisten hermoverkkojen ja jäännösluokkajärjestelmän soveltaminen kryptografiassa . — M .: FIZMATLIT , 2012. — 280 s. - ISBN 978-5-9221-1386-1 .
Ananda Mohan, PV Residue Number Systems. - Cham: Springer International Publishing , 2016. - 351 s. - ISBN 978-3-319-41385-3 .
Amir Sabbagh, Molahosseini, Leonel Seabra de Sousa ja Chip-Hong Chang (toimittajat). Sulautetut järjestelmät erityisillä aritmeettisilla ja numerojärjestelmillä. - Cham: Springer International Publishing , 21. maaliskuuta 2017. - 389 s. — ISBN 978-3-319-49742-6 .

Linkit

Artikkeli "Modulaarinen aritmetiikka" suuressa venäläisessä tietosanakirjassa