高速乗算法の設計と実装(4)
梅谷 武
作成：2001-09-20 更新：2005-04-20
高速乗算法(3)において係数を分解しない方法の実験を行なったが、剰余演算の語長が6語であったため、2語と4語に分解した高速乗算法Ⅱよりかなり計算量が多くなった。高速乗算法Ⅳは係数を分解しないで剰余演算の語長を3語にする。
IMS:20010920002; NDC:412.1; keywords:高速乗算法;
係数の評価式
から
なる素数
pであって、
Fpの演算、すなわち法
pの剰余演算が高速に計算できるものを探す。
とおくと
が成り立つ。
U(n),n=0,1,2,3,4,5,6を素数判定してみる。
| | |
| | |
| | |
| | |
| | | 216(232-1)+1 | = | 281474976645121:合成数 |
|
| | |
| | |
、すなわち
K=25=32の場合に素数になっているが、
と表現するとき、
となり除算を使わずに3語の剰余演算ができる。
p = U(5) = 232(264-1)+1とする。これは素数であり、
という係数の評価式が成り立つ。さらに
Fp上に長さ
Nの離散フーリエ変換が存在するための必要十分条件は、
であるが、
はこの条件を満たし、さらにこのとき
pの最小原始根
11を使って
Fp上の
1の原始
N乗根を
| 11t, | t | = | 232-n(264-1), | 0＜n≦32 |
と表現することができる。
Step 1. 数のP進表現
基数を
P=232とし、長さを
とする。正の整数
a,bが次のように
P進表現されるものとする。
この積について
0≦ab＜PNが成り立つと仮定する。
Step 2. 多項式としての積の計算
PK≡1(mod PN-1)より、
となる。この係数
cr=∑s+t≡r(mod N)asbtの大きさを評価すると、
| 0 | ≦ | cr | ≦ | N(232-1)2 | ＜ | U(5) | = | 232(264-1)+1 |
となる。
Step 3. 離散フーリエ変換による係数の計算
crは、
(N, FU(5), ζ), ζ=11t, t=232-n(264-1)型の離散Fourier変換を利用して次のように計算する。
| | |
| | |
| | | N-1 | N-1
Σ
k=0 | F(a)kF(b)kζ-kr | | (mod U(5)) |
|
Step 4. 桁上げ処理
最後にcr, r=0,…,K-1に桁上げ処理を施すことで、c=abのP進表現が得られる。
高速乗算法