Multiply large integers under large modulo | 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
< ? php function moduloMultiplication ( $ a , $ b , $ mod ) { $ a %= $ mod ; while ( $ b ) { if ( $ b & 1 ) $ res = ( $ res + $ a ) % $ mod ; $ a = ( 2 * $ a ) % $ mod ; } return $ res ; } $ a = 10123465234878998 ; $ b = 65746311545646431 ; $ m = 10005412336548794 ; echo moduloMultiplication ( $ a , $ b , $ m ) ; ? >