Modular multiplicative inverse | Returns modulo inverse of a with respect to m using extended Euclid Algorithm Assumption : a and m are coprimes , i . e . , gcd ( a , m ) = 1 ; q is quotient ; m is remainder now , process same as Euclid 's algo ; Update x and y ; Make x positive ; Driver code ; Function call
def modInverse ( a , m ) : NEW_LINE INDENT m0 = m NEW_LINE y = 0 NEW_LINE x = 1 NEW_LINE if ( m == 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT while ( a > 1 ) : NEW_LINE INDENT q = a // m NEW_LINE t = m NEW_LINE m = a % m NEW_LINE a = t NEW_LINE t = y NEW_LINE y = x - q * y NEW_LINE x = t NEW_LINE DEDENT if ( x < 0 ) : NEW_LINE INDENT x = x + m0 NEW_LINE DEDENT return x NEW_LINE DEDENT a = 3 NEW_LINE m = 11 NEW_LINE print ( " Modular ▁ multiplicative ▁ inverse ▁ is " , modInverse ( a , m ) ) NEW_LINE