Systém zbytkových tříd

Systém zbytkových tříd (SOC) ( anglicky zbytek číselný systém ) je číselný systém založený na modulární aritmetice .

Reprezentace čísla v systému třídy zbytku je založena na konceptu zbytku a čínské větě o zbytku . RNS je určena sadou párových coprime modulů , to znamená tak, že se nazývá báze a součin , takže každé celé číslo ze segmentu je spojeno se sadou zbytků , kde $(m_{1},\,m_{2},\,\tečky ,\,m_{n})$ $\gcd(m_{i},\,m_{j})=1$ $(i,\,j=0,\,1,\,\tečky ,\,n;\ i\neq j)$ $M=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n},$ $X$ $[0,\M-1]$ $(x_{1},\,x_{2},\,\tečky ,\,x_{n})$

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

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

\tečky \tečky \tečky \tečky \tečky \tečky \tečky

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

Čínská věta o zbytku zároveň zaručuje jednoznačnost (jedinečnost) reprezentace nezáporných celých čísel z intervalu . $[0,\M-1]$

Výhody systému zbytkových tříd

V RNS se aritmetické operace (sčítání, odčítání, násobení, dělení) provádějí po komponentech, pokud je výsledek znám jako celé číslo a také leží v . $[0,M-1]$

Sčítací vzorec: kde $(x_{1},x_{2},\tečky ,x_{n})+(y_{1},y_{2},\tečky ,y_{n})=(z_{1},z_ {2},\tečky ,z_{n})$

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

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

\tečky \tečky \tečky \tečky \tečky \tečky \tečky \tečky \tečky

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

Odčítání, násobení a dělení se provádí podobně. Poznámka : Existují další omezení dělení. Dělení musí být celé číslo, to znamená, že dělitel musí dělit dividendu celým číslem. Dělitel musí být coprime se všemi moduly báze.

Nevýhody systému zbytkových tříd

nedostatek účinných algoritmů pro porovnávání čísel; Obvykle se srovnání provádí převodem argumentů z RNS do číselné soustavy (polyadické) se smíšenými základy: ; ${\displaystyle m_{1},m_{1}m_{2},\tečky ,m_{1}m_{2}\tečky m_{n-1))$
pomalé algoritmy pro vzájemnou transformaci reprezentace čísel z poziční číselné soustavy do RNS a naopak;
komplexní algoritmy dělení (když výsledek není celé číslo);
potíže s detekcí přetečení.

Aplikace systému zbytkových tříd

SOC je široce používán v mikroelektronice ve specializovaných DSP zařízeních , kde je požadováno:

kontrola chyb zavedením dalších redundantních modulů;
vysoká rychlost, která je zajištěna paralelní implementací základních aritmetických operací;
informační bezpečnost .

Praktické využití: Československý elektronkový počítač "EPOS" , sovětský vojenský víceprocesorový superpočítač 5E53 , určený k řešení problémů protiraketové obrany .

Speciální modulové systémy

V modulární aritmetice existují speciální sady modulů, které umožňují částečně vyrovnat nedostatky a pro které existují účinné algoritmy pro porovnávání čísel a pro přímý a zpětný převod modulárních čísel do pozičního číselného systému. Jedním z nejpopulárnějších moduli systémů je množina tří párových prvočísel ve tvaru {2 n −1, 2 n , 2 n +1} .

Příklad

Zvažte RNS se základem . V tomto základě je možné reprezentovat čísla z intervalu od do jedna ku jedné , protože . Korespondenční tabulka čísel z poziční číselné soustavy a soustavy zbytkových tříd: $(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)$

Příklad přidání

Sečteme dvě čísla 9 a 14 v základu . Jejich zastoupení v daném základu a (viz tabulka výše). Pro sčítání použijeme vzorec: $(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)$ - podle tabulky dbáme na to, aby výsledek byl 23.

Příklad násobení

Vynásobte dvě čísla 4 a 5 v základu . Jejich zastoupení v daném základu a (viz štítek výše). Pro násobení použijeme vzorec: $(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)$ - podle tabulky dbáme na to, aby výsledek byl 20.

Poznámka: Pokud bychom měli násobit nebo sčítat čísla, která v důsledku násobení dala číslo větší nebo rovné, pak získaný výsledek, kde je výsledek operace v poziční číselné soustavě. $M=30$ $RES\equiv REAL{\pmod {M}}$ $REAL$

Příklad dělení za předpokladu, že je možné dělení celým číslem

Dělení lze provést stejným způsobem jako násobení, ale pouze v případě, že dělitel dělí dělenec rovnoměrně, beze zbytku.
U modulů vydělte číslo 1872 9. Vydělte . $(29;31;32)$
$1872=(16;12;16)$ $9=(9;9;9)$

Použijme vzorec
$z_{i}\equiv (x_{i}*y_{i}^{-1}){\pmod {m_{i}}}.$

Zde je třeba říci, že , což není totéž jako prosté dělení podle . Podle vzorce dostaneme: ${\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.$

Toto je správný výsledek - číslo 208. Takový výsledek však lze získat pouze tehdy, je-li známo, že dělení je provedeno beze zbytku.

Viz také

Literatura

Akushsky I.Ya. , Yuditsky D.I. Strojová aritmetika ve zbytkových třídách . - Sovy. rozhlas , 1968. - 439 s.
Torgashev, Valerij Antonovič. Systém zbytkových tříd a spolehlivost počítačů . - M . : Sov. rozhlas , 1973. - 118 s.
Amerbaev V.M. Teoretické základy strojové aritmetiky . - Akademie věd Kazašské SSR, Ústav matematiky a mechaniky. Alma-Ata: Science , 1976. - 324 s.
Finko O. A. Modulární aritmetika paralelních logických výpočtů : Monografie - M .: IPU RAS , 2003. - 214 s.
výročí Mezinárodní vědecká a technická konference "50 let modulární aritmetiky" . - OJSC "Angstrem" , MIET . - 23.-25. listopadu 2005; Moskva, Zelenograd: FIZMATLIT , 2006. - 775 s. — ISBN ISBN 5-7256-0409-8 .
Amos Omondi, Benjamin Premkumar. Systémy čísel reziduí: Teorie a realizace . - 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 aj. Aplikace umělých neuronových sítí a systému reziduálních tříd v kryptografii . — M .: FIZMATLIT , 2012. — 280 s. - ISBN 978-5-9221-1386-1 .
Ananda Mohan, PV systémy reziduí čísel. - Cham: Springer International Publishing , 2016. - 351 s. - ISBN 978-3-319-41385-3 .
Amir Sabbagh, Molahosseini, Leonel Seabra de Sousa a Chip-Hong Chang (editoři). Návrh vestavěných systémů se speciálními aritmetickými a číselnými soustavami. - Cham: Springer International Publishing , 21. března 2017. - 389 s. — ISBN 978-3-319-49742-6 .

Odkazy

Článek "Modulární aritmetika" ve Velké ruské encyklopedii