指数演算は容易にオーバーフローしてしまうので、MODをとる場合でも工夫が必要である。 指数演算の場合の工夫は、MOD乗算の場合と非常に似ている。 指数をの足し算で表す。 ここで、は2進数表記でのnビット目を示す。ただし、0ビットから始まるとする。 この…

MODをとる場合でも大きい数字の掛け算はオーバーフローしてしまうので、工夫をしなければならない。 片方の数字をの足し算で表す。 ここで、は2進数表記でのnビット目を示す。ただし、0ビットから始まるとする。 aを括弧内に入れる。 は1か0しか値を取らない…