Вычисляет значение формулы ab mod n за время O(c), где c - количество бит в unsigned int b.

int ModExp(unsigned int a,unsigned int b,unsigned int n)
{
    int d = 1;
    int k = 31;
 
    while((b&(1<<k)) == 0)k--;
    while(k != -1)
    {
        d = (d*d)%n;
        if(b&(1<<k)) d = (d*a)%n;
        k--;
    }
    return d;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.