剰余の法が大きい場合のアルゴリズム

質問

プログラミング等でよく"x^n(mod m)を解け"といった問題がよく挙がりますが、法"m"が
大きい場合については触れているものが少ないので質問させていただきます。

例えば単純に除法で求める場合、"x^n"については展開できるので、何でもよい数として
簡単に"x"とおくと、"x/m"をニュートン法で求め"x-round(x/m)*m"で余を求める、という
ような感じになります。ここで"m"は"1024bit"程度の大きい数を想定しています。よい
アルゴリズムがあれば教えてください。

回答No.2

rinkun

まあアルゴリズムに関する情報は多倍長演算で探せばありますね。
なお、乗算剰余演算や冪剰余演算はそのまま計算すると桁数が増えすぎて無駄に時間が掛かるので、工夫されたアルゴリズムがあります。具体的には乗算剰余演算に使うモンゴメリ乗算があります。冪剰余演算もこれを応用して行います。

モンゴメリ乗算：http://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%B3%E3%82%B4%E3%83%A1%E3%83%AA%E4%B9%97%E7%AE%97

回答No.1

Tacosan

「任意精度計算」とか「多倍長演算」とかで適当に調べれば出てきそうな気がするんだけど....

ただ, 「剰余計算そのもの」に興味があるならいいんだけど, そうじゃなくてそれを道具として使いたいというだけならライブラリに丸投げした方が安心できると思うよ.