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

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

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

　　４２＝２＋２^3＋２^5

　　４２^42＝４２^（２＋２^3＋２^5）＝４２^2・４２^（２^3）・４２^（２^5）

　　４２^2＝１７６４＝２５

　　４２^（２^2）＝（４２^2）^2＝６２５＝１４

　　４２^（２^3）＝（（４２^2）^2）^2）＝１９６＝８

　　４２^（２^4）＝（（（４２^2）^2）^2）^2）＝６４＝１７

　　４２^（２^5）＝（（（（４２^2）^2）^2）^2）^2)＝２８９＝７

　　４２^42＝４２^（２＋２^3＋２^5）＝４２^2・４２^（２^3）・４２^（２^5）＝２５・８・７＝１４００＝３７＝-１０

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