バイナリ法による冪剰余の計算
ここにコード書くのはどうやればいいんだ?と思ったら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;
}
どっちも要するに2で割って、
2で割り切れないなら ( t * a ) % m
2で割り切れるなら(t * t) % m
ってとこがポイントかなと。
ところでバイナリ法はモンゴメリ乗算の一つ、っていう理解で良いのだろうか。判らんことが多い。。