■MOD算術(その28)

[Q]79^37 mod 107,すなわち,79^37を107で割ったときの余りを求めよ.

===================================

 反復2倍乗法を応用した反復平方による累乗法を用いると,

  37=1+2^2+2^5

  79^37=79^(1+2^2+2^5)=79^1・79^(2^2)・79^(2^5)

  79^(2^2)=(79^2)^2

  79^(2^5)=((((79^2)^2)^2)^2)^2

こうして37乗を求めるのに37回よりもはるかに少ない7回のかけ算を行えば十分であることがわかるだろう.

===================================