残基数システム

剰余記数法( RNS ) は、整数を、モジュラスと呼ばれる互いに素な整数の組を法としてその値を表す記数法です。この表現は、中国剰余定理によって許可されています。中国剰余定理は、M がモジュラスの積である場合、長さMの区間には、任意のモジュラー値のセットを持つ整数が 1 つだけ存在すると主張しています。算術演算に剰余記数法を使用することは、マルチモジュラー算術とも呼ばれます。

マルチモジュラ演算は、数値システム間の変換時間を考慮しても、通常の数値システムよりも高速な計算が可能であるため、典型的には線型代数における大きな整数の計算に広く使用されています。マルチモジュラ演算の他の用途には、多項式の最大公約数、グレブナー基底計算、暗号化などがあります。

剰余数体系はk個の整数 の集合によって定義される。

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

モジュライと呼ばれるものは、一般に互いに素である（つまり、任意の2つの最大公約数が1に等しい）と考えられています。非素数モジュライに対しても留数システムが定義されていますが、特性が悪いため一般的には使用されていません。したがって、この記事の残りの部分では考慮しません。^[1]

整数xは剰余数体系ではその剰余の集合で表される。

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

ユークリッドの法による 除算で、

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

そして

${\displaystyle 0\leq x_{i} <m_{i}}$

すべてのi

M をすべての の積とします。差がMの倍数である 2 つの整数は、m _i sで定義される剰余数記数法で同じ表現を持ちます。より正確には、中国剰余定理は、 M 個の異なる剰余集合のそれぞれが、M を法とする剰余類クラスを1 つだけ表すと主張します。つまり、剰余集合のそれぞれは、区間 内の1 つの整数を正確に表します。符号付き数の場合、動的範囲は です (が偶数のときは、一般に余分な負の値が表されます)。^[2]${\displaystyle m_{i}}$${\displaystyle X}$${\displaystyle 0,\dots ,M-1}$${\textstyle {-\lfloor M/2\rfloor }\leq X\leq \lfloor (M-1)/2\rfloor }$${\displaystyle M}$

剰余数体系で表された数の加算、減算、乗算には、剰余の各ペアに対して 同じモジュラー演算を実行すれば十分である。より正確には、

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

は剰余で表される整数xとyの合計であるモジュライのリストであり、は剰余 で表される整数zであり、${\displaystyle [x_{1},\ldots,x_{k}]}$${\displaystyle [y_{1},\ldots ,y_{k}],}$${\displaystyle [z_{1},\ldots ,z_{k}],}$

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

i = 1, ..., kの場合(通常どおり、mod はユークリッド除算の余りを右オペランドで 割るモジュロ演算を表します)。減算と乗算も同様に定義されます。

一連の演算では、各ステップでモジュロ演算を適用する必要はありません。ハードウェア演算のオーバーフローを回避するために、計算の最後にモジュロ演算を適用したり、計算中にモジュロ演算を適用したりすることができます。

しかし、剰余数システムでは、大きさの比較、符号の計算、オーバーフローの検出、スケーリング、除算などの演算を実行することは困難です。^[3]

2 つの整数が等しい場合、その剰余はすべて等しいです。逆に、すべての剰余が等しい場合、 2 つの整数は等しいか、またはその差がMの倍数です。したがって、等価性のテストは簡単です。

逆に、不等式 ( x < y ) のテストは難しく、通常は整数を標準表現に変換する必要があります。結果として、この数値表現は、ユークリッド除算やユークリッドの互除法などの不等式テストを使用するアルゴリズムには適していません。

剰余数体系における除算は問題である。一方、が と互いに素である（つまり）場合、 ${\displaystyle B}$${\displaystyle M}$${\displaystyle b_{i}\not =0}$

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

簡単に計算できる

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

ここで、はを法とする逆数であり、 はを法とする逆数です。 ${\displaystyle B^{-1}}$${\displaystyle B}$${\displaystyle M}$${\displaystyle b_{i}^{-1}}$${\displaystyle b_{i}}$${\displaystyle m_{i}}$

RNS は、デジタル コンピュータ演算の分野で応用されています。この分野では、大きな整数を小さな整数のセットに分解することで、大規模な計算を、独立して並列に実行できる一連の小さな計算として実行できます。

• カバーシステム
• 残留物低減システム

• Szabo, Nicholas S.; Tanaka, Richard I. (1967).剰余演算とコンピュータ技術への応用(第 1 版). ニューヨーク、米国: McGraw-Hill .
• Sonderstrand, Michael A.; Jenkins, W. Kenneth; Jullien, Graham A.; Taylor, Fred J. 編 (1986)。剰余数システム演算: デジタル信号処理における最新のアプリケーション。IEEE プレス再版シリーズ (第 1 版)。米国ニューヨーク: IEEE 回路およびシステム協会、IEEEプレス。ISBN 0-87942-205-XLCCN  86-10516。IEEE 注文コード PC01982 。（viii+418+6ページ）
• Chervyakov, NI; Molahosseini, AS; Lyakhov, PA (2017). 近似中国剰余定理に基づく一般モジュライ集合の剰余からバイナリへの変換。International Journal of Computer Mathematics、94:9、1833-1849、doi: 10.1080/00207160.2016.1247439。
• フィンコ [Финько]、オレグ・アナトレヴィチ [Олег Анатольевич] (2004 年 6 月)。 「ブール関数の大規模システム: モジュラー算術手法による実現」。オートメーションとリモートコントロール。65 (6): 871–892。土井:10.1023/B:AURC.0000030901.74901.44。ISSN  0005-1179。LCCN  56038628。S2CID 123623780。CODEN AURCAT  。 ​ミ 1588。
• Chervyakov, NI; Lyakhov, PA; Deryabin , MA (2020). 畳み込みニューラルネットワークのハードウェアコストを削減するための剰余数システムベースのソリューション。Neurocomputing 、407、439-453、doi: 10.1016/j.neucom.2020.04.018。
• Bajard, Jean-Claude; Méloni, Nicolas; Plantard, Thomas (2006-10-06) [2005 年 7 月]。「暗号化のための効率的な RNS 基数」(PDF)。IMACS'05 : 世界会議: 科学計算、応用数学、シミュレーション。パリ、フランス。HAL Id: lirmm-00106470。2021-01-23にオリジナルからアーカイブ(PDF) 。2021-01-23に取得。（1+7ページ）
• オモンディ、アモス、プレムクマール、ベンジャミン (2007)。剰余数システム:理論と実装。ロンドン、イギリス:インペリアル・カレッジ・プレス。ISBN 978-1-86094-866-4。（296ページ）
• Mohan, PV Ananda (2016). 残基数システム: 理論と応用 (第1版). Birkhäuser / Springer International Publishing Switzerland . doi :10.1007/978-3-319-41385-3. ISBN 978-3-319-41383-9. LCCN  2016947081.（351ページ）
• Amir Sabbagh、Molahosseini、de Sousa、Leonel Seabra、Chip-Hong Chang 編 (2017-03-21)。特殊な算術および数値システムによる組み込みシステム設計 (第 1 版)。Springer International Publishing AG。doi : 10.1007 / 978-3-319-49742-6。ISBN 978-3-319-49741-9. LCCN  2017934074.（389ページ）
• 「除算アルゴリズム」。2005年2月17日にオリジナルからアーカイブ。2023年8月24日に閲覧。
• ドナルド・アービン・クヌース著『コンピュータプログラミングの芸術』アディソン・ウェスリー著。
• Harvey, David (2010). 「ベルヌーイ数を計算するためのマルチモジュラーアルゴリズム」.計算数学. 79 (272): 2361– 2370. arXiv : 0807.1347 . doi : 10.1090/S0025-5718-2010-02367-1 . S2CID  11329343.
• Lecerf, Grégoire; Schost, Éric ( 2003). 「特性ゼロにおける高速多変量べき級数乗算」SADIO 電子ジャーナル、情報科学およびオペレーションズ・リサーチ。5 (1): 1– 10。
• Orange, Sébastien; Renault, Guénaël; Yokoyama, Kazuhiro (2012). 「対称性を用いた連続代数拡大体における効率的な算術」.コンピュータサイエンスにおける数学. 6 (3): 217– 233. doi :10.1007/s11786-012-0112-y. S2CID  14360845.
• 横山 和弘 (2012 年 9 月)。「理想演算の効率的な計算のためのモジュラー手法の使用」。科学計算におけるコンピュータ代数に関する国際ワークショップ。ベルリン / ハイデルベルク、ドイツ: Springer。pp.  361– 362。
• Hladík, Jakub; Šimeček, Ivan (2012 年 1 月)。「GPU で線形方程式を解くためのモジュラー演算」。数値解析セミナー。pp.  68– 70。
• Pernet, Clément (2015 年 6 月)。「正確な線形代数アルゴリズム: 理論と実践」。2015 ACM 国際記号および代数計算シンポジウムの議事録。Association for Computing Machinery。pp .  17– 18。
• Lecerf, Grégoire (2018)。「Lickteig-Roy 部分終結アルゴリズムの複雑さについて」。Journal of Symbolic Computation。
• 横山 和弘; 野呂 正之; 竹島 拓 (1994). 「二変量積分多項式の多項式時間分解に対するマルチモジュラーアプローチ」.シンボリック計算ジャーナル. 17 (6): 545– 563. doi : 10.1006/jsco.1994.1034 .
• Isupov, Konstantin (2021). 「浮動小数点演算を使用した剰余数システムにおける高性能計算」。計算。9 (2): 9. doi:10.3390/computation9020009. ISSN 2079-3197 。