C++ Program to find the power of a number modulo M in Logarithmic time














































C++ Program to find the power of a number modulo M in Logarithmic time



Discription:

Given three integers a , n & M (a > 0, n >= 0 and M > 0), Our task is to compute a^n % M.

 

Solution:

First Let's understand the properties of Modulo.

	I)   (A*B)%MOD = (A%MOD * B*MOD)%MOD
II)  (A+B)%MOD = (A%MOD + B%MOD)%MOD
III) (A-B)%MOD = (A%MOD - B%MOD)%MOD
IV)  A%MOD     = (A+MOD)%MOD , to make Modulo positive if it becomes negative
V)   (A/B)%MOD = (A%MOD * B')% MOD , B' is Modulo Multiplicative Inverse of B with respect of MOD

 

Now using the concept of my previous article we can find a^n % M in Logarithmic time with few changes:
Refer to this article for more details.

 

C++ Program:

#include<iostream> using namespace std; template<typename T> T power(T a, T n, T M) { T res = 1; while (n > 0) { if (n & 1) { res *= a; if (res >= M) { res %= M; } /* we can skip decrement of n by 1 because in next step we will divide n by 2 and it will produce the same result */ } n >>= 1; // Here division by 2 is done by bitwise right shift a *= a; if (a >= M) { a %= M; } } return res; } int main() { int a = 10023, n = 231344, m = 123414; cout << '(' <<a << '^' << n << ')' <<'%' << m << " = " << power(a, n, m) << '\n'; long long p = 12323221, q = 134224122344, r = 21331434; cout << '(' <<p << '^' << q << ')' <<'%' << r <<" = " << power(p, q, r) << '\n'; return 0; }

Output:


Comments