バイナリ法による冪剰余の計算
ここにコード書くのはどうやればいいんだ？と思ったらpreタグでいいらしい。
■冪剰余 - Wikipedia
http://ja.wikipedia.org/wiki/%E5%86%AA%E5%89%B0%E4%BD%99#.E9.80.94.E4.B8.AD.E3.81.A7.E5.89.B0.E4.BD.99.E3.82.92.E3.81.A8.E3.82.8B
Bignum modpow( Bignum b, Bignum e, Bignum m){
Bignum result = 1;
while ( e > 0 ){
if (( e & 1 ) == 1
result = (result * b ) % m;
e >>= 1;
b = ( b * b ) % m;
}
return result;
}
「アルゴリズムを学ぼう」に書いてあるk=2^tならn^k = n^t * n^tってのが何なのかようやく判ってきたのでメモっとく。
ちなみにそっちのコードはこんな↓で、これはこれで理解するのに一週間くらい掛かった。
long powmod( int a, int k, int m){
if ( k == 0 )
return 1;
long t = powmod( a, k / 2, m);
t = (t * t) % m;
if (k % 2 == 1)
t = (t * a) % m;
return (int) t;
}
どっちも要するに２で割って、
２で割り切れないなら ( t * a ) % m
２で割り切れるなら(t * t) % m
ってとこがポイントかなと。
ところでバイナリ法はモンゴメリ乗算の一つ、っていう理解で良いのだろうか。判らんことが多い。。
