Consider two large integers M and N. The multiplication of M and N under modulo P is calculated as below
( M * N ) mod P = ( M mod P * N mod P ) mod P
or
( M * N ) % P = ( M % P * N % P ) % P
Example: If M = 6, N = 8 and P = 5 then
( 6 * 8 ) % 5 = [ ( 6 % 5 ) * ( 8 % 5) ] % 5
Evaluating the L.H.S
( 6 * 8 ) % 5 = 48 % 5 = 3
Evaluating the R.H.S
[ ( 6 % 5 ) * ( 8 % 5 ) ] % 5 = [ 1 * 3 ] = 3
Consider very large intergers a and b and we need to evaluate ( a * b ) % p.
As we know from the modular multiplication property ( a * b ) % p = [ ( a % p ) * ( b % p ) ] % p
If [ ( a % p ) * ( b % p ) ] evaluates to [ x * y ] and the size of ( x * y ) exceeds the size of unsigned long long, we would run into overflow error.
To overcome this problem we do the below
( x * y ) % p = ( x + x + x + ….. y times ) % p
If y is even, then x could be multiplied with 2, ( y / 2 ) times.
i.e ( x * y ) % p = [ ( ( 2 * x ) % p ) * ( y / 2 ) ] % p.
If y is odd, then x could be added to the result once and then x could be multiplied with 2, ( y / 2 ) times.
This way we could easily avoid overflow error. Thus we have the below algorithm.
For evaluating : ( a * b ) % p
Algorithm Modular_Multiplication ( Integer a , Integer b , Integer (modulo) p )
0. Initialize result = 0
1. a = a % p
2. While ( b > 0 ) do
3. If b is odd then,
result = ( result + a ) % p
4. a = ( a * 2 ) % p
5. b = b / 2
6. return ( result % p )
For evaluating : ( base power ) % p
Algorithm Modular_Exponentiation ( Integer base , Integer power , Integer (modulo) p )
0. Initialize result = 1
1. While ( power > 0 ) do
2. If power is odd then,
3. Instead of evaluating result as result = ( result * base ) % p, do the multiplication of base with result under modulo
result = Modular_Multiplication ( result, base, p )
4. Instead of evaluating base as base = ( base * base ) % p, do the multiplication of base with base under modulo
base = Modular_Multiplication ( base, base, p )
5. power = power / 2
6. return ( result % p )
C++ : Calculating the exponentation under modulo.
#include<iostream>
using namespace std;
typedef unsigned long long ULL;
// Evaluates ( a * b ) mod p. This is needed when a * b exceeds the sizeof of ULL;
ULL Mod_Mul (ULL a, ULL b, ULL p) {
ULL result = 0;
a = a % p;
while ( b > 0 ) {
if ( b & 1 ) {
result = ( result + a ) % p;
}
a = ( 2 * a ) % p;
b /= 2;
}
return result % p;
}
// Below function evaluates ( base ^ power ) mod p
ULL Mod_Expo (ULL base, ULL power, ULL p) {
cout << "\nBase : " << base << ", Power : " << power << ", Modulo p : " << p << endl;
ULL result = 1;
while ( power > 0 ) {
if ( power & 1 ) {
// Instead of evaluating result as result = ( result * base ) % p
// Do the multiplication under modulo
result = Mod_Mul(result, base, p);
}
// Instead of evaluating base as base = ( base * base ) % p
// Do the multiplication of base under modulo
base = Mod_Mul(base, base, p);
power >>= 1; // power = power / 2
}
result = result % p;
cout << "Result : " << result << endl;
return result;
}
int main() {
ULL result = 0;
result = Mod_Expo(9899888889444, 77777774434334, 44434343);
result = Mod_Expo(9, 3, 4);
result = Mod_Expo(2, 5, 7);
result = Mod_Expo(1234569899888889444, 323277777774434334, 5544434343);
return 0;
}
Output
Base : 9899888889444, Power : 77777774434334, Modulo p : 44434343
Result : 9533174
Base : 9, Power : 3, Modulo p : 4
Result : 1
Base : 2, Power : 5, Modulo p : 7
Result : 4
Base : 1234569899888889444, Power : 323277777774434334, Modulo p : 5544434343
Result : 1266639207