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

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

２^341　ｍｏｄ　３４１を計算するにあたっては、

２^10＝１　ｍｏｄ　３４１であることから運良く計算できたが、そんな基底ｂや指数ｎに対しても成り立つアルゴリズムが必要になる。

もっと正式にｂ^n　ｍｏｄ　ｍを計算するために、まずｎの2進数分解を求める。

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

　　３４１＝１＋２^2＋２^4＋２^6+２^8

　　２^341＝２^（１＋２^2＋２^4＋２^6+２^8）＝２・２^（２^2）・２^（２^4）・２^（２^6）・２^（２^8）

　　２＝２

　　２^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＝６４

　　２^341＝２^（１＋２^2＋２^4＋２^6+２^8）＝２・２^（２^2）・２^（２^4）・２^（２^6）・２^（２^8）

＝２・２^4・２^6・２^4・２^6＝２　　　（２^4・２^6＝１より）

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