クイックモードべき乗アルゴリズム

1、乗算モード演算規則:
(a * b) % n = (a % n * b % n) % n  
2,モードべき乗演算a^b mod c:
b比較的大きい場合は、いわゆる二分法を利用して、b=b 0+b 1*2^1+b 2*2^2+...+bn*2^nは、最下位ビットb 0から、右から左へビット毎に走査する.
3、インスタンスコード:

#include <iostream>
using namespace std;

//  a^bmodn
int modexp(int a,int b,int n)
{
    int ret=1;
    int tmp=a;
    while(b)
    {
       //    
       if(b&0x1) ret=ret*tmp%n;
       tmp=tmp*tmp%n;
       b>>=1;
    }
    return ret;
}

int main()
{
    cout<<modexp(2,10,3)<<endl;
    return 0;
}