inverse static method

BigInt inverse(BigInt num, [ BigInt? md ])

Implementation

static BigInt inverse(BigInt num, [BigInt? md]) {
  md ??= P;
  if (num == BigInt.zero || md <= BigInt.zero) {
    // no neg exponent for now
    throw Exception('no inverse n=$num mod=$md');
  }
  BigInt a = mod(num, md);
  BigInt b = md;
  BigInt x = BigInt.zero;
  BigInt y = BigInt.one;
  BigInt u = BigInt.one;
  BigInt v = BigInt.zero;
  while (a != BigInt.zero) {
    // uses euclidean gcd algorithm
    final q = b ~/ a, r = b % a; // not constant-time
    final m = x - u * q, n = y - v * q;
    b = a;
    a = r;
    x = u;
    y = v;
    u = m;
    v = n;
  }
  if (b == BigInt.one) {
    return mod(x, md);
  }
  // b is gcd at this point
  throw Exception('no inverse');
}