GCD of a number raised to some power and another number | Calculates modular exponentiation , i . e . , ( x ^ y ) % p in O ( log y ) ; x = x % p Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now y = y >> 1 y = y / 2 ; Returns GCD of a ^ n and b ; Driver code
def power ( x , y , p ) : NEW_LINE INDENT while ( y > 0 ) : NEW_LINE INDENT if ( y & 1 ) : NEW_LINE INDENT res = ( res * x ) % p NEW_LINE DEDENT x = ( x * x ) % p NEW_LINE DEDENT return res NEW_LINE DEDENT def gcd ( a , b ) : NEW_LINE INDENT if ( a == 0 ) : NEW_LINE INDENT return b NEW_LINE DEDENT return gcd ( b % a , a ) NEW_LINE DEDENT def powerGCD ( a , b , n ) : NEW_LINE INDENT e = power ( a , n , b ) NEW_LINE return gcd ( e , b ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = 5 NEW_LINE b = 4 NEW_LINE n = 2 NEW_LINE print ( powerGCD ( a , b , n ) ) NEW_LINE DEDENT