Modular Exponentiation ( Power in Modular Arithmetic ) | Iterative Function to calculate ( x ^ y ) in O ( log y ) ; Initialize result ; If y is odd , multiply x with result ; y must be even now y = y / 2 ; Change x to x ^ 2
def power ( x , y ) : NEW_LINE INDENT res = 1 NEW_LINE while ( y > 0 ) : NEW_LINE INDENT if ( ( y & 1 ) != 0 ) : NEW_LINE INDENT res = res * x NEW_LINE DEDENT DEDENT DEDENT y = y >> 1 NEW_LINE x = x * x NEW_LINE INDENT return res NEW_LINE DEDENT