きままにものづくり

日々の気付いたことなんかを書いてます。

MOD指数演算

指数演算は容易にオーバーフローしてしまうので、MODをとる場合でも工夫が必要である。
指数演算の場合の工夫は、MOD乗算の場合と非常に似ている。
指数を2^nの足し算で表す。
a^b = a^{(b_02^0 + b_12^1 + b_22^2+...+b_N2^N)}
ここで、b_nは2進数表記でのnビット目を示す。ただし、0ビットから始まるとする。
このように、表現することでaの2のべき乗の総和で答えを表現できる。2のべき乗の数字を作るのは、自身の二乗をとればよい。2^4から2^8を作るのは、2^4\times2^4とすればよい。