def mod_inverse(x, n):
  """
  Compute the inverse of x in the multiplicative
  group of Z/nZ, i.e. the integer y such that

  x * y = 1 mod N.

  The algorithm uses the extended Euclidean
  algorithm to find the inverse efficiently.

  """
  a, b = n, x
  ta, tb = 0, 1
  while b != 0:
    q = a / b
    a, b = b, a % b
    ta, tb = tb, ta - (q * tb)
  if ta < 0:
    ta += n
  return ta