Modular Exponentiation ( Power in Modular Arithmetic ) | Iterative Function to calculate ( x ^ y ) % p in O ( log y ) ; Initialize result ; Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now ; Driver Code
< ? php function power ( $ x , $ y , $ p ) { $ res = 1 ; $ x = $ x % $ p ; if ( $ x == 0 ) return 0 ; while ( $ y > 0 ) { if ( $ y & 1 ) $ res = ( $ res * $ x ) % $ p ; y = $ y / 2 $ y = $ y >> 1 ; $ x = ( $ x * $ x ) % $ p ; } return $ res ; } $ x = 2 ; $ y = 5 ; $ p = 13 ; echo " Power ▁ is ▁ " , power ( $ x , $ y , $ p ) ; ? >