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

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

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

　　４３＝１＋２＋２^3＋２^5

　　４３^43＝４２^（１＋２＋２^3＋２^5）＝４３・４３^2・４３^（２^3）・４３^（２^5）

　　４３^2＝１８４９＝１６

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

　　４３^（２^3）＝（（４３^2）^2）^2）＝４４１＝１８

　　４３^（２^4）＝（（（４３^2）^2）^2）^2）＝３２４＝４２

　　４３^（２^5）＝（（（（４３^2）^2）^2）^2）^2)＝１７６４＝２５

　　４３^43＝４２^（１＋２＋２^3＋２^5）＝４３・４３^2・４３^（２^3）・４３^（２^5）

＝４３・１６・１８・２５＝３０９６００＝１１

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