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

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

例として２つの 9 bit の正の整数 A, B の自乗和を剰余系を使用し

X = A² + B²

を求めてみる。

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

2¹⁹ = 524,288 ≦ d₁ d₂ … d_t

となる互いに素な任意の整数のセットを選ぶ。
例として {5, 7, 9, 11, 13, 16} を選ぶと、各要素の積 n は

2¹⁹ = 524,288 ＜ n = 5 * 7 * 9 * 11 * 13 * 16 = 720,720

であるから上の条件を満たすのでこれを使用することにする。
与えられる２つの数をＡ、Ｂとし、Ａ＝357、Ｂ＝412　の時を例にとって説明する。
Ａ、Ｂをそれぞれ {5, 7, 9, 11, 13, 16} で割った余りを求めると、

A₅ = 2 (mod  5),
A₇ = 0 (mod  7),
A₉ = 6 (mod  9),
A₁₁ = 5 (mod 11),
A₁₃ = 6 (mod 13),
A₁₆ = 5 (mod 16)

B₅ =  2 (mod  5),
B₇ =  6 (mod  7),
B₉ =  7 (mod  9),
B₁₁ =  5 (mod 11),
B₁₃ =  9 (mod 13),
B₁₆ = 12 (mod 16)

となる。それぞれの自乗の剰余を求め

SA₅ =  4 (mod  5),
SA₇ =  0 (mod  7),
SA₉ =  0 (mod  9),
SA₁₁ =  3 (mod 11),
SA₁₃ = 10 (mod 13),
SA₁₆ =  9 (mod 16)

SB₅ = 4 (mod  5),
SB₇ = 1 (mod  7),
SB₉ = 2 (mod  9),
SB₁₁ = 3 (mod 11),
SB₁₃ = 3 (mod 13),
SB₁₆ = 0 (mod 16)

それぞれの和の剰余を求めると

S₅ = 3 (mod  5),
S₇ = 1 (mod  7),
S₉ = 4 (mod  9),
S₁₁ = 6 (mod 11),
S₁₃ = 0 (mod 13),
S₁₆ = 9 (mod 16)

となり、剰余系において答えが求められた。
この剰余系のまま他の計算を進めることも出来るが、この剰余系の数を普通の数に戻すには、

(n / d_j ) x_j ≡ 1 (mod d_j )

なる x_j 、つまり n / d の d_j における乗法的逆元を拡張ユークリッドの互除法 (extended Euclid's algorithm)により求め、

n₅ = 576576 (mod m /  5),
n₇ = 205920 (mod m /  7),
n₉ = 320320 (mod m /  9),
n₁₁ = 196560 (mod m / 11),
n₁₃ = 277200 (mod m / 13),
n₁₆ = 585585 (mod m / 16)

各剰余類と逆元の積和として、得ることが出来る。

X = ( (S₅ n₅ ) (mod n)
    + (S₇ n₇ ) (mod n)
    + (S₉ n₉ ) (mod n)
    + (S₁₁ n₁₁ ) (mod n)
    + (S₁₃ n₁₃ ) (mod n)
    + (S₁₆ n₁₆ ) (mod n) ) (mod n)


  = 297193 (mod n)

*Note1 ＦＦＴによる方法も中国人剰余定理による方法も考え方の本質的には同じである。つまり、ある大きな数を直交するｎ次元の小さな数に細分できれば、ｎ個の小さな数の計算で済むということである。単位ベクトルを e^jωnt にとればフーリエ変換であるし、互いに素な数にとれば中国人剰余定理である。

Get the test program source written in C (mod_calc-1.6.tar.gz)
MD5 (mod_calc-1.6.tar.gz) = 1bac199de2f3dcb0ef55d9b29dbe56f9