Fast exponentiaion and multiplication

general
, ,
1

Hi,

I am unable to understand the iterative version of fast modular exponentiation code.

long long prod(long long a, long long b, long long mod = MOD)
{
    long long res = 0;

    while(b)
    {
        if(b & 1)
            res = (res + a) % mod;
        a = (a + a) % mod;

        b >>= 1;
    }

    return res;
}

long long bpow(long long a, long long b, long long mod = MOD)
{
    long long res = 1;

    while(b)
    {
        if(b & 1)
            res = prod(res, a, mod);
        a = prod(a, a, mod);

        b >>= 1;
    }

    return res;
}

The prod function does overflow safe multiplication, again similar to fast exponentiation code, but hard to get.

2

Recursive version of fast modular exponentiation is easy to understand, so first you should try the recursive version

function power (a,b,m):
    if b == 0: return 1
    else if b == 1: return a % m
    t = power (a,b/2)
    if b % 2 == 0: return (t * t) % m
    else : return (t * t * a) % m

It is the recursive algorithm for fast exponentiation, try to get it first.