［Ｑ］２^561　ｍｏｄ　５６１，すなわち，２^561を５６１で割ったときの余りを求めよ．

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

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

　　５６１＝１＋２^4＋２^5＋２^9

　　２^561＝２^（１＋２^4＋２^5＋２^9）＝２・２^（２^4）・２^（２^5）・２^（２^9）

　　２＝２

　　２^2＝４

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

　　２^（２^3）＝（（２^2）^2）^2＝２５６

　　２^（２^4）＝（（（２^2）^2）^2）^2＝６５５３６＝４６０

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

　　２^（２^6）＝（（（（（２^2）^2）^2）^2）^2）^2＝１０６０９＝５１１

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

　　２^（２^8）＝（（（（（（（２^2）^2）^2）^2）^2）^2）^2）^2＝４６０

　　２^（２^8）＝（（（（（（（（２^2）^2）^2）^2）^2）^2）^2）^2）^2＝１０３

　　２^561＝２^（１＋２^4＋２^5＋２^9）＝２・２^（２^4）・２^（２^5）・２^（２^9）

＝２・４６０・１０３・１０３＝２

２・４６０＝３５９

１０３・１０３＝１０６０９＝５１１

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

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