Multiply large integers under large modulo | Java program of finding modulo multiplication ; Returns ( a * b ) % mod ; Initialize result ; 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
class GFG { static long moduloMultiplication ( long a , long b , long mod ) { long res = 0 ; a %= mod ; while ( b > 0 ) { if ( ( b & 1 ) > 0 ) { res = ( res + a ) % mod ; } a = ( 2 * a ) % mod ; } return res ; } public static void main ( String [ ] args ) { long a = 10123465234878998L ; long b = 65746311545646431L ; long m = 10005412336548794L ; System . out . print ( moduloMultiplication ( a , b , m ) ) ; } }