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 code
using System ; class GFG { static long moduloMultiplication ( long a , long b , long mod ) { a %= mod ; while ( b > 0 ) { if ( ( b & 1 ) > 0 ) res = ( res + a ) % mod ; a = ( 2 * a ) % mod ; } return res ; } static void Main ( ) { long a = 10123465234878998 ; long b = 65746311545646431 ; long m = 10005412336548794 ; Console . WriteLine ( moduloMultiplication ( a , b , m ) ) ; } }