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

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

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

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

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

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

　　３７＝１＋２^2＋２^5

　　７９^37＝７９^（１＋２^2＋２^5）＝７９^1・７９^（２^2）・７９^（２^5）

　　７９＝７９

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

　　７９^（２^2）＝（７９^2）^2＝１２２５＝４８

　　７９^（２^3）＝（（７９^2）^2）^2＝２３０４＝５７

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

　　７９^（２^5）＝（（（（７９^2）^2）^2）^2）^2＝１５２１＝２３

　　７９^37＝７９^（１＋２^2＋２^5）＝７９^1・７９^（２^2）・７９^（２^5）＝７９・４８・２３＝８７２１６＝１１

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

剰余計算をより優しくするもう一つの方法は

（ｘ＋ｙ）^n＝ｘ^n＋ｙ^n 　ｍｏｄ　ｎ（ｎは素数）

がある。

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