Calculating A^B mod N

Binary Exponentiation

We frequently need to calculate terms like a^b and most programming contests have a need to find modulo of the above exponent i.e. (a^b)%Mod_value.  Now there is a Brute force and a simple and a clever method to find that.

suppose for integers A, q, B, r we can have A = qB + r

now the modulo is the simple manipulation of the above property.

we can rewrite the above as A = r (mod q) or conversely we can say that 

A = r (mod Mod_value ) is an expression equivalent to A = q*Mod_value + r where q can be any integer.

Some properties of the modulo 

1. if a = r1 (mod q)  and  b = r2 (mod q) then :

             a + b = (r1 + r2) (mod q) and same goes for subtraction,

             a*b = (r1 * r2) (mod q)

the above can be proved easily by taking the expanded form of the expression i.e a = qz + r1, b = qw + r2

2. Now the above multiplication property can be used to get the exponent part which we are interested in.

suppose we have a = b , then we r1 = r2,  so we have a^2 = r^2 (mod q)

we could also get by multiplying a = r(mod q)

 = a^2 * a = r^2 * r (mod q) 

 = a^3 = r^3 (mod q)

lets find a^5 (mod q). we could surely use five times multiplication of a = r (mod q), taking 5 steps or we could use a = r (mod q) and a^4 = r^4 (mod q), we can get a^4 in 2 steps or lg(4) steps and a total of 3 steps to get the answer. (Observe 5 = 101 in base 2 and the no of steps is the number of bits or more precisely { lg(N) } where {.} is the largest integer function), (Similarly we can get 2^K th power of a in K steps getting a logarithmic complexity.)

Note that we used a^1 and a^4 exponents, and the places with 1's in 5's binary representation is also 1 and 4. 

Lets jump into the algorithm

 Now we just use the values that have 1 in their bit positions. 

 r = (127 x 17 x 289 x 917 x 44 x 66 x 842 ) (mod 1007) 

 r = 1399034822210256 (mod 1107)

 r = 867

which is the answer we need.

Why did we just take the bits with 1 in it ?

5223 = 1010001100111

thus we just need 2^0, 2^1, 2^2, 2^5, 2^6, 2^10, 2^12. just add them up and we get 5223

using the property we use a^(2^0) * (a^(2^1) * (a^(2^2)) * (a^(2^5)) * .. * (a^(2^10) * a(^(2^12))

which is equal to a^(1+2+4+32+64+1024+4096) = a^(5223) which is what we require.

pseudo Code:

function(a, n, mod_value):
       ans = 1
       d = a
       repeat :
              if (n%2 == 1):
                     ans = (ans * d)%mod_value //use the value with bit 1
              d = (d*d)%mod_value //keep squaring
              n = n/2
       return ans

Python Implementation:

pow_mod(a, n, mod_value):
        ans = 1, d = n
        while n:
                if b&1:
                        ans = (ans * d)%mod_value
                d = (d*d)%mod_value
                b = b>>1
        return ans

C++ Function

define LL long long

LL pow_mod(LL a , LL n, LL mod_value)

{
LL ans = 1, d = n;
  while (n)   
  {
     if(n&1)
          ans = (ans * d)%mod_value;
      d = (d*d)%mod_value;
    n = n>>1;
  }
    return ans;
}

Time Complexity : O(Log(N))
Space Complexity : O(1)