modInv function

dynamic modInv(
  1. num a,
  2. num m
)

Returns the modular inverse of 'a' mod 'm' if it exists.

Make sure 'm' > 0 and 'a' & 'm' are relatively prime.

  • Parameter a the number for which to find the modular inverse m the modulus (must be > 0)

  • Returns: the modular inverse of 'a' mod 'm', or null if it does not exist

Example:

 // Prints 3 since 2*3 mod 5 = 1
 print(modInv(2, 5));

 // Prints null because there is no
 // modular inverse such that 4*x mod 18 = 1
 print(modInv(4, 18));

Implementation

dynamic modInv(num a, num m) {
  if (m <= 0) throw ArgumentError("mod must be > 0");

  // Avoid a being negative
  a = ((a % m) + m) % m;

  var v = egcd([a, m]).first;
  num gcd = v[0];
  num x = v[1];

  if (gcd != 1) return null;
  return ((x + m) % m) % m;
}