c - 累乗剰余

Question

C/C++ では、64 ビットに収まらない(a^b)%m場所を計算するにはどうすればよいですか? bつまり、b%m代わりに を使用して上記の値を計算する方法はありbますか?

O(log(b))上記の結果を時間または時間で計算できるアルゴリズムはありますO(log(b%m))か?

Answer 1

オイラーの定理によると、aとmが互いに素である場合:

ab mod m = ab mod phi(m) mod m

が大きい場合は、代わりにb値を使用できます。はオイラーのトーティエント関数であり、 の素因数分解がわかっていれば簡単に計算できます。b % phi(m)bphi(m)m

bこの方法での値を減らしたら、2 乗によるべき乗を使用して、 の剰余べき乗を計算しO(log (b % phi(m)))ます。