This is the problem of Modular Exponentiation. Given a,b,c we need to find (a^b) mod c for large a,b,c. If we do it the regular way, we can multiply a in a for loop for b times to find a^b. But since b is very large, this method is inefficient.
How do we do this fast?
Let us take an example. a = 6, b = 13, c = 7. We need to find 6^13 mod 7.
Now the binary representation of 13 is 1101. So 13 can be written as :
13 = 2^3 + 2^2 + 2^0
So, 6^13 mod 7 = 6^(2^3 + 2^2 + 2^0) mod 7
= (6^(2^3) * 6^(2^2) * 6^(2^0)) mod 7 (bcoz a^(b+c) = a^b*a^c)
= ([6^(2^3) mod 7] * [6^(2^2) mod 7] * [6^(2^0) mod 7] ) mod 7 (bcoz (ab)mod c = ((a mod c) * (b mod c)) mod c)
Now we have reduced the problem to finding a^b mod c where b is a power of 2. How can we use this fact to solve faster?
Consider a^(256) =a^(128) * a^(128). In general a^(2^i) = a^(2^(i-1)) * a^(2^(i-1)). So if we know modular exponentiation of a^(2^(i-1)) mod c we can compute a^(2^i) mod c
f(i) = a^(2^i) mod c = (a^(2^(i-1)) mod c * a^(2^(i-1)) mod c) mod c = (f(i-1)*f(i-1))mod c
f(0) = a^(2^0) mod c = a mod c //base case
So Let's solve this example.
f(0) = 6^(2^(0)) mod 7 = 6 mod 7 = 6
f(1) = 6^(2^(1)) mod 7 = (f(0) * f(0)) mod 7 = 36 mod 7 = 1
f(2) = 6^(2^(2)) mod 7 = (f(1) * f(1)) mod 7 = 1 mod 7 = 1
f(3) = 6^(2^(3)) mod 7 = (f(2) * f(2)) mod 7 = 1 mod 7 = 1
Now 6^13 mod 7 = ([6^(2^3) mod 7] * [6^(2^2) mod 7] * [6^(2^0) mod 7] ) mod 7
= (f(3) * f(2)* f(0) ) mod 7 = (1*1*6) mod 7 = 6
Let's verify our results. 6^13 mod 7 = 13060694016 mod 7 = 6
The C function for this :
// Computes base^exp % mod
long fastModularExponentiation(long base , long exp, long mod )
{
long result = 1;
/* basePow2iMod holds the value of (base ^ (2i) % mod*/
long basePow2iMod = base;
while(exp > 0)
{
/* extract the least significant bit*/
int lsb = exp % 2;
/* if lsb is 1 then multiply basePow2iMod to the result */
if(lsb == 1) result = (result * basePow2iMod) % mod;
/* update the exponent*/
exp = exp / 2;
/* update basePow2iMod */
basePow2iMod = (basePow2iMod * basePow2iMod) % mod;
}
return result;
}
Time Complexity = O(number of bits in b) = O(log b)
You can see the entire code: https://github.com/JanakyMurthy/programmingPractice/blob/master/math/fastModularExponentiation.c
There can be no better explanation than this:
https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation
