Function to calculate ( x ^ y ) % p in O ( log y )
def power ( x , y , p ) : NEW_LINE INDENT result = 1 NEW_LINE while ( y > 0 ) : NEW_LINE INDENT if y & 1 == 1 : NEW_LINE INDENT result = ( result * x ) % p NEW_LINE DEDENT x = ( x * x ) % p NEW_LINE y >>= 1 NEW_LINE DEDENT return result NEW_LINE DEDENT