text: 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
code: #include <stdio.h> NEW_LINE 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 = 10123465234878998 ; long long b = 65746311545646431 ; long long m = 10005412336548794 ; printf ( " % lld " , moduloMultiplication ( a , b , m ) ) ; return 0 ; }