- 912 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 20:20:31 ]
- >>888 で述べた a^((p - 1)/2) (mod p) を効率よく計算する
アルゴリズムを紹介する。
Cohen の A course in computational algebraic number theory に
述べられている方法である。
問題を一般にして、G を群とし、G の元 g と n ＞ 0 に対して
g^n を計算する方法を考える。
n を２進数で表示して n = Σ(ε_i)2^i とする。
ε_i は 0 または 1 である。
g^n = Π g^(2^i) である。ここで i は ε_i = 1 となる i を動く。
各 g^(2^i) は、最初に z = g として z = z・z を繰り返せばよい。
ここで = は右辺を左辺に代入することを表す。
各 g^(2^i) を計算したら順次、前に計算した結果に掛けていく。
これで終わりである。
このアルゴリズムを擬似コードで書くと次のようになる。
