Systém čísel zbytků - Residue number system

A soustava zbytkových číslic (RNS) je číselná soustava zastupující celá čísla podle jejich hodnot modulo několik dvojice coprime celá čísla zvaná moduly. Toto znázornění je povoleno Čínská věta o zbytku, který tvrdí, že pokud $N$ je součin modulů, je v intervalu délky $N$ , přesně jedno celé číslo, které má danou sadu modulárních hodnot. The aritmetický soustavy číslic zbytku se také nazývá multimodulární aritmetika.

Multimodulární aritmetika je široce používána pro výpočet s velkými celými čísly, obvykle v lineární algebra, protože poskytuje rychlejší výpočet než u obvyklých číselných systémů, i když je zohledněn čas pro převod mezi číslovými systémy. Mezi další aplikace multimodulární aritmetiky patří polynomiální největší společný dělitel, Gröbnerův základ výpočet a kryptografie.

Definice

Systém číslic zbytků je definován sadou $k$ celá čísla

{ displaystyle {m_ {1}, m_ {2}, m_ {3}, ldots, m_ {k} },}

volal moduly, které by obecně měly být dvojice coprime (to znamená, že dva z nich mají největší společný dělitel rovná jedné). Systémy zbytkových čísel byly definovány pro non-coprime moduly, ale nejsou běžně používány kvůli horším vlastnostem. Ve zbývající části tohoto článku proto nebudou brány v úvahu.^[1]

Celé číslo $X$ je v soustavě číslic zbytků představována množinou jejích zbytků

{ displaystyle {x_ {1}, x_ {2}, x_ {3}, ldots, x_ {k} }}

pod Euklidovské dělení podle modulů. To je

{ displaystyle x_ {i} = x operatorname {mod} m_ {i},}

a

{ displaystyle 0 leq x_ {i}

pro každého $i$

Nechat $M$ být produktem všeho ${ displaystyle m_ {i}}$ . Dvě celá čísla, jejichž rozdíl je násobkem $M$ mají stejné zastoupení v soustavě číslic zbytků definované v $m i$ s. Přesněji řečeno Čínská věta o zbytku tvrdí, že každý z $M$ různé sady možných zbytků představuje právě jeden třída zbytků modulo $M$ . To znamená, že každá sada zbytků představuje přesně jedno celé číslo v intervalu $0, ..., M$ .

V aplikacích, kde je zájem také o záporná celá čísla, je často pohodlnější představovat celá čísla patřící k intervalu se středem na 0. V tomto případě, pokud $M$ je liché, každá sada zbytků představuje přesně jedno celé číslo absolutní hodnota nejvíce ${ displaystyle { frac {M} {2}}}$ .

Aritmetické operace

Pro sčítání, odčítání a násobení čísel představovaných v systému čísel zbytků stačí provést totéž modulární provoz na každém páru zbytků. Přesněji řečeno, pokud

{ displaystyle [m_ {1}, ldots, m_ {k}]}

je seznam modulů, součet celých čísel $X$ a $y$ , respektive představované zbytky ${ displaystyle [x_ {1}, ldots, x_ {k}]}$ a ${ displaystyle [y_ {1}, ldots, y_ {k}],}$ je celé číslo $z$ reprezentováno ${ displaystyle [z_ {1}, ldots, z_ {k}],}$ takhle

{ displaystyle z_ {i} = (x_ {i} + y_ {i}) operatorname {mod} m_ {i},}

pro $i = 1, ..., k$ (jako obvykle mod označuje modulo provoz spočívající v převzetí zbývající části Euklidovské dělení správným operandem). Odečtení a násobení jsou definovány podobně.

Pro postupnost operací není nutné v každém kroku použít modulo operaci. Může být použito na konci výpočtu nebo během výpočtu k zamezení přetékat hardwarových operací.

Operace, jako je srovnání velikosti, výpočet znaménka, detekce přetečení, změna měřítka a dělení, je však obtížné provést v systému čísel zbytků.^[2]

Srovnání

Pokud jsou dvě celá čísla stejná, pak jsou všechny jejich zbytky stejné. Naopak, pokud jsou všechny zbytky stejné, pak jsou obě celá čísla stejná nebo je jejich rozdíl násobkem $M$ . Z toho vyplývá, že testování rovnosti je snadné.

Naopak, testování nerovností ( $X < y$ ) je obtížné a obvykle vyžaduje převod celých čísel na standardní reprezentaci. V důsledku toho není toto znázornění čísel vhodné pro algoritmy využívající testy nerovnosti Euklidovské dělení a Euklidovský algoritmus.

Divize

Rozdělení v soustavách zbytkových číslic je problematické. Články popisující některé možné algoritmy jsou k dispozici na [1][2]. Na druhou stranu, pokud ${ displaystyle B}$ je coprime s ${ displaystyle M}$ (to je ${ displaystyle b_ {i} not = 0}$ ) pak

{ displaystyle C = A cdot B ^ {- 1} mod M}

lze snadno vypočítat pomocí

{ displaystyle c_ {i} = a_ {i} cdot b_ {i} ^ {- 1} mod m_ {i},}

kde ${ displaystyle B ^ {- 1}}$ je multiplikativní inverzní z ${ displaystyle B}$ modulo ${ displaystyle M}$ , a ${ displaystyle b_ {i} ^ {- 1}}$ je multiplikativní inverzní funkce k ${ displaystyle b_ {i}}$ modulo ${ displaystyle m_ {i}}$ .

Aplikace

RNS mají aplikace v oblasti digitální počítačová aritmetika. Rozložením tohoto velkého celého čísla na sadu menších celých čísel lze provést velký výpočet jako řadu menších výpočtů, které lze provést nezávisle a paralelně.

Viz také

Reference

^ Behrooz Parhami, Počítačová aritmetika: Algoritmy a návrh hardwaru. 2. vydání, Oxford University Press, New York, 2010. 641 + xxv str. ISBN 978-0-19-532848-6.
^ Isupov, K. (2020). „Používání intervalů s plovoucí desetinnou čárkou pro nemodulární výpočty v systému čísel reziduí“. Přístup IEEE. 8: 58603–58619. doi:10.1109 / ACCESS.2020.2982365. ISSN 2169-3536.

Další čtení

Jean-Claude Bajard, Nicolas Meloni a Thomas Plantard, Efektivní základy RNS pro kryptografii, IMACS'05: World Congress: Scientific Computation Applied Mathematics and Simulation. 2005.
O. A. Fin'ko, Velké systémy booleovských funkcí: Realizace modulárními aritmetickými metodami, Automation and Remote Control, 65 (2004), č. 6, 871–892.
Amos Omondi, Benjamin Premkumar. Systémy reziduálních čísel: teorie a implementace. Imperial College Press. Londýn. 2007. 296 s. ISBN 978-1-86094-866-4.
Ananda Mohan, P.V. Systémy zbytkových čísel, Springer International Publishing. 2016. 351 s. ISBN 978-3-319-41385-3.
Amir Sabbagh, Molahosseini, Leonel Seabra de Sousa a Chip-Hong Chang (redaktoři), Návrh vestavěných systémů se speciálními aritmetickými a číselnými systémy, Springer International Publishing. 21. března 2017. 389 s. ISBN 978-3-319-49742-6.

[1] Behrooz Parhami, Počítačová aritmetika: Algoritmy a návrh hardwaru. 2. vydání, Oxford University Press, New York, 2010. 641 + xxv str. ISBN 978-0-19-532848-6.

[2] Isupov, K. (2020). „Používání intervalů s plovoucí desetinnou čárkou pro nemodulární výpočty v systému čísel reziduí“. Přístup IEEE. 8: 58603–58619. doi:10.1109 / ACCESS.2020.2982365. ISSN 2169-3536.

[1]

[2]