inverseMod static method

BigInt inverseMod(BigInt a, BigInt m)

Calculates the modular multiplicative inverse of 'a' modulo 'm'.

Returns the value 'x' such that (a * x) % m == 1, or 0 if 'a' has no inverse.

Implementation

static BigInt inverseMod(BigInt a, BigInt m) {
  if (a == BigInt.zero) {
    // 'a' has no inverse; return 0.
    return BigInt.zero;
  }
  if (a >= BigInt.one && a < m) {
    // If 'a' is in the range [1, m-1], use the built-in modInverse method.
    return a.modInverse(m);
  }

  BigInt lm = BigInt.one,
      hm = BigInt.zero; // Initialize low and high quotients.
  BigInt low = a % m, high = m; // Initialize low and high remainders.

  while (low > BigInt.one) {
    // Continue the Euclidean algorithm until 'low' becomes 1.
    BigInt r = high ~/ low;
    BigInt nm = hm - lm * r;
    BigInt newLow = high - low * r;
    hm = lm;
    high = low;
    lm = nm;
    low = newLow;
  }

  return lm % m;
}