Find ( a ^ b ) % m where ' b ' is very large | Function to find power ; Update x if it is more than or equal to p ; If y is odd , multiply x with the result ; y must be even now $y = $y >> 1 ; y = y / 2 ; Driver Code ; String input as b is very large ; Reduce the number B to a small number using Fermat Little
< ? php function power ( $ x , $ y , $ p ) { $ x = $ x % $ p ; while ( $ y > 0 ) { if ( $ y & 1 ) $ res = ( $ res * $ x ) % $ p ; $ x = ( $ x * $ x ) % $ p ; } return $ res ; } $ a = 3 ; $ b = "100000000000000000000000000" ; $ remainderB = 0 ; $ MOD = 1000000007 ; for ( $ i = 0 ; $ i < strlen ( $ b ) ; $ i ++ ) $ remainderB = ( $ remainderB * 10 + $ b [ $ i ] - '0' ) % ( $ MOD - 1 ) ; echo power ( $ a , $ remainderB , $ MOD ) ; ? >