Multiply large integers under large modulo | C ++ program of finding modulo multiplication ; Returns ( a * b ) % mod ; Update a if it is more than or equal to mod ; If b is odd , add a with result ; Here we assume that doing 2 * a doesn 't cause overflow ; b >>= 1 ; b = b / 2 ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long moduloMultiplication ( long long a , long long b , long long mod ) { a %= mod ; while ( b ) { if ( b & 1 ) res = ( res + a ) % mod ; a = ( 2 * a ) % mod ; } return res ; } int main ( ) { long long a = 426 ; long long b = 964 ; long long m = 235 ; cout << moduloMultiplication ( a , b , m ) ; return 0 ; }