C++

Doing Multiplication & Exponentiation Under Modulo


Modular Multiplication Property

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


Avoiding overflow errors while doing modular multiplication

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


Copyright (c) 2019-2021, Algotree.org.
All rights reserved.