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
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 DEDENT