暗号の数学

計算法 (演算の高速化)

Karatsuba乗算

2n 桁の数 uvの乗算を行うことを考える.uv を基数 b の冪 x = bn を用いて

u = u1x + u0, v = v1x + v0

のように上半分と下半分に分ければ,x を基数とした乗算と考えることができる.

このとき単純に w = u v を求めると,

w = u1v1x2 + (u0v1 + u1v0)x + u0v0

のように n 桁 × n 桁の乗算が 4回必要である.しかし

u0v1 + u1v0 = (u1 + u0)(v1 + v0) - (u1v1 + u0v0)

または

u0v1 + u1v0 = u1v1 + u0v0 - (u1 - u0)(v1 - v0)

という関係を使えば n 桁×n 桁の乗算は 3回で済むことが分かる.ここで,さらに u1,u0,v1,v0 の上位の桁を 0 で埋めて桁数を偶数にするか,あるいは始めから uv の桁数を 2の冪にしておけば,3回の乗算に同じアルゴリズムを再帰的に適用することができる.この乗算アルゴリズムを Karatsuba乗算(Karatsuba Multiplication)という. すなわち, b 進法で表現したとき 2桁になる整数同士の乗算は,b 進法で 1桁の整数同士の乗算を 3回と,それよりもコストの十分に小さい加減算を用いて行うことができる.

n = 2kと仮定したとき,b 進法で n 桁の整数同士の乗算をKaratsuba乗算で行うと,b 進法で1桁の整数同士の乗算が 3k 回必要となる.k = log2 n より,この方法での b 進法で n 桁の整数同士の乗算のコストは,3k = 3log2 n = nlog2 3n1.585 程度で済むことになる.実際には n が 2k で表現できるとは限らないので, 2k で表現できないときは n1.585 よりも少し余計にかかる.

多項式の積 (Karatsuba - Offman乗算)

多項式の変数 x の係数を計算するときに,x0x2 の係数を再利用することにより,加減算より遅い乗算の回数を削減でき高速化が図れる(aibi が多項式である場合には効果がある).

(a0 + a1 x)(b0 + b1 x) = a0b0 + (a0b1 + a1b0) x + a1b1 x2
 = a0b0 + {(a0 + a1)(b0 + b1) - a0b0 - a1b1} x + a1b1 x2

(a0 + a1 x + a2 x2)(b0 + b1 x + b2 x2)
 = a0b0 + [{(a0 + a1)(b0 + b1) - a1b1} - a0b0] x + [(a0 + a1 + a2)(b0 + b1 + b2)
  - {(a0 + a1)(b0 + b1) - a1b1} - {(a1 + a2)(b1 + b2) - a1b1}] x2
  + [{(a1 + a2)(b1 + b2) - a1b1} - a2b2] x3 + a2b2 x4

中国人の剰余定理

剰余演算

逆元

Montgomery 算法


inserted by FC2 system