［Ｑ］３０^30　ｍｏｄ　４７，すなわち，３０^30を４７で割ったときの余りを求めよ．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

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

　　３０＝２＋２^2＋２^3＋２^4

　　３０^30＝３０^（２＋２^2＋２^3＋２^4）＝３０~2・３０^（２^2）・３０^（２^3）・３０^（２^4）

　　３０^2＝９００＝７

　　３０^（２^2）＝（３０^2）^2＝４９＝２

　　３０^（２^3）＝（（３０^2）^2）^2）＝４

　　３０^（２^4）＝（（（３０^2）^2）^2）^2）＝１６

　　３０^30＝３０^（２＋２^2＋２^3＋２^4）＝３０~2・３０^（２^2）・３０^（２^3）・３０^（２^4）＝８９６＝３

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝