Multiplicative inverse of n mod m ((Euclidean algorithm))In cryptography, we often need \(n^{−1}\), which is a multiplicative inverse of n mod m, i.e. \(n/(n^{−1}) = 1 \mod m\). It is used in the calculation of the decryption key in RSA, and in other cryptography methods. With RSA, we get (e x d) mod (N) = 1, where we have e and N, and must calculate d using the multiplicative inverse of n mod m. |
Coding
An outline of the code is:
def extended_euclidean_algorithm(a, b): """ Returns a three-tuple (gcd, x, y) such that a * x + b * y == gcd, where gcd is the greatest common divisor of a and b. This function implements the extended Euclidean algorithm and runs in O(log b) in the worst case. """ s, old_s = 0, 1 t, old_t = 1, 0 r, old_r = b, a while r != 0: quotient = old_r // r old_r, r = r, old_r - quotient * r old_s, s = s, old_s - quotient * s old_t, t = t, old_t - quotient * t return old_r, old_s, old_t def inverse_of(n, p): """ Returns the multiplicative inverse of n modulo p. This function returns an integer m such that (n * m) % p == 1. """ gcd, x, y = extended_euclidean_algorithm(n, p) assert (n * x + p * y) % p == gcd if gcd != 1: # Either n is 0, or p is not a prime number. raise ValueError( '{} has no multiplicative inverse ' 'modulo {}'.format(n, p)) else: return x % p val1=65537 val2=1034776851837418226012406113933120080 print("Inverse of ",val1," mod ",val2) print("Result:\t:",inverse_of(val1,val2))