🌐English

剰余系による数値計算の例

modular arithmetic based calculation (including CRT)

2026-01-04
Takayuki HOSODA

概要

多桁の数を直接計算するにはハードウェア規模が Ο (n2) で増大し非現実的なサイズになってしまう。 もし、多桁の数をくつかの小さな数のセットに分解して演算ができると、ハードウェアで 数値演算回路を構成する場合にハードウェアの規模を小さくする事が出来る場合がある。 多桁の乗算には FFT を用いた方法などがあるが、 ここでは、中国人剰余定理 (Chinese remainder theorem) を利用した 剰余系 による数値計算を紹介する。

※ 但し、数千桁未満の場合や剰余系のまま計算を進められない場合、あるいはハードウェアでの剰余計算が利用できない場合には Karatsuba 法 などに対してメリットは薄い。
なぜなら、定数での剰余の計算もそれなりに計算コストが高いし、また通常の数に戻すときに逆元との積和で大きな数を扱わなければならないからである。

中国人剰余定理を利用した剰余系による数値計算法の例

例として２つの 9 bit の正の整数 A, B の自乗和を剰余系を使用し
X = A2 + B2
を求めてみる。

まず、２つの 9 bit の自乗和は、高々 19 bit であるから

219 = 524,288 ≤ d1 d2 … dt
となる互いに素な任意の整数のセットを選ぶ。
例として {5, 7, 9, 11, 13, 16} を選ぶと、各要素の積 n は
219 = 524,288 < n = 5 × 7 × 9 × 11 × 13 × 16 = 720,720
であるから上の条件を満たすのでこれを使用することにする。
与えられる２つの数を A, B とし、A = 357, B = 412 の場合を例にとって説明する。
A, B をそれぞれ {5, 7, 9, 11, 13, 16} で割った余りを求めると、 
A5  = 2 (mod  5),
A7  = 0 (mod  7),
A9  = 6 (mod  9),
A11 = 5 (mod 11),
A13 = 6 (mod 13),
A16 = 5 (mod 16)

B5  =  2 (mod  5),
B7  =  6 (mod  7),
B9  =  7 (mod  9),
B11 =  5 (mod 11),
B13 =  9 (mod 13),
B16 = 12 (mod 16)
となる。それぞれの自乗の剰余 SA, SB を求め 
SA5  =  4 (mod  5),
SA7  =  0 (mod  7),
SA9  =  0 (mod  9),
SA11 =  3 (mod 11),
SA13 = 10 (mod 13),
SA16 =  9 (mod 16)

SB5  = 4 (mod  5),
SB7  = 1 (mod  7),
SB9  = 2 (mod  9),
SB11 = 3 (mod 11),
SB13 = 3 (mod 13),
SB16 = 0 (mod 16)
それぞれの和の剰余 S を求めると 
S5  = 3 (mod  5),
S7  = 1 (mod  7),
S9  = 4 (mod  9),
S11 = 6 (mod 11),
S13 = 0 (mod 13),
S16 = 9 (mod 16)
となり、剰余系において答えが求められた。
この剰余系のまま他の計算を進めることも出来るが、
この剰余系の数を普通の数に戻すには、 n / d の dj における 乗法的逆元 すなわち
n / dj · Ij ≡ 1 (mod dj)
なる Ij を 拡張ユークリッドの互除法 (extended Euclid's algorithm) により求め、 
I5  = 576576,
I7  = 205920,
I9  = 320320,
I11 = 196560,
I13 = 277200,
I16 = 585585
各剰余類と逆元の積和として、得ることが出来る。 

X = ( (S5  × I 5) (mod n)
    + (S7  × I 7) (mod n)
    + (S9  × I 9) (mod n)
    + (S11 × I11) (mod n)
    + (S13 × I13) (mod n)
    + (S16 × I16) (mod n) ) (mod n)
  = 297193 (mod n)

まとめ

このように、中国人剰余定理（CRT）に基づく数値計算は、演算を 小さく独立した計算に分解できる 点に大きな特徴があり、それらを 並列に実行できる、あるいは並列実行を前提として構成できる という点で魅力的である。 さらに、互いに素な剰余の集合を自由に選択できるため、 対象とするアーキテクチャや性能要件に応じて、 並列計算の粒度を調整できる という柔軟性を持つ。 この柔軟性は、FFT を用いた方法とは異なり、 ワード長、パイプライン段数、利用可能な並列資源といった ハードウェア制約に合わせて演算構造を設計できる ことを意味する。

一方で、実装にあたっては次の点を考慮する必要がある。

DSP や FPGA においては、対象とするビット長や演算パターンによって、 Karatsuba 法、FFT による方法、剰余系による方法のいずれが有利になるかは大きく異なる。

多桁演算という観点で見ると、FFT による方法と CRT による方法はいずれも、 大きな数を 直交する成分へ分解する という点で本質的に類似している。
すなわち、ある大きな数を直交する n 個の成分に分解できれば、計算は n 個の小さな演算に帰着される。
単位ベクトルを eiωnt とすれば、フーリエ変換 となり、互いに素な整数の集合を用いれば 中国人剰余定理 となる。

SEE ALSO

www.finetune.co.jp [Mail] © 2000 Takayuki HOSODA.