2013-09-16 MOD指数演算 指数演算は容易にオーバーフローしてしまうので、MODをとる場合でも工夫が必要である。 指数演算の場合の工夫は、MOD乗算の場合と非常に似ている。 指数をの足し算で表す。 ここで、は2進数表記でのnビット目を示す。ただし、0ビットから始まるとする。 このように、表現することでaの2のべき乗の総和で答えを表現できる。2のべき乗の数字を作るのは、自身の二乗をとればよい。からを作るのは、とすればよい。