Calculating the Modular Inverse in JavaScript

This implementation of modular inverse can accept any type of inputs. If input types are not supported, NaN is returned. Also, it does not use recursion.

function modInverse(a, m) {
  // validate inputs
  [a, m] = [Number(a), Number(m)]
  if (Number.isNaN(a) || Number.isNaN(m)) {
    return NaN // invalid input
  }
  a = (a % m + m) % m
  if (!a || m < 2) {
    return NaN // invalid input
  }
  // find the gcd
  const s = []
  let b = m
  while(b) {
    [a, b] = [b, a % b]
    s.push({a, b})
  }
  if (a !== 1) {
    return NaN // inverse does not exists
  }
  // find the inverse
  let x = 1
  let y = 0
  for(let i = s.length - 2; i >= 0; --i) {
    [x, y] = [y,  x - y * Math.floor(s[i].a / s[i].b)]
  }
  return (y % m + m) % m
}

// Tests
console.log(modInverse(1, 2))       // = 1
console.log(modInverse(3, 6))       // = NaN
console.log(modInverse(25, 87))     // = 7
console.log(modInverse(7, 87))      // = 25
console.log(modInverse(19, 1212393831))     // = 701912218
console.log(modInverse(31, 73714876143))    // = 45180085378
console.log(modInverse(3, 73714876143))     // = NaN
console.log(modInverse(-7, 87))     // = 62
console.log(modInverse(-25, 87))    // = 80
console.log(modInverse(0, 3))       // = NaN
console.log(modInverse(0, 0))       // = NaN

I was just going through the definition of modular multiplicative inverse and from what I understand:

ax = 1 (mod m)
=> m is a divisor of ax -1 and x is the inverse we are looking for
=> ax - 1 = q*m (where q is some integer)
And the most important thing is gcd(a, m) = 1
i.e. a and m are co-primes

In your case:

ed = 1 mod((p-1)(q-1)) //p, q and e are given 
=> ed - 1 = z*((p-1)(q-1)) //where z is some integer and we need to find d

Again from the wikipedia entry, one can compute the modular inverse using the extended Euclidean GCD Algorithm which does the following:

 ax + by = g //where g = gcd(a,b) i.e. a and b are co-primes
 //The extended gcd algorithm gives us the value of x and y as well.

In your case the equation would be something like this:

 ed - z*((p-1)(q-1)) = 1; //Compare it with the structure given above

 a -> e
 x -> d
 b -> (p-1)(q-1)
 y -> z

So if we just apply that algorithm to this case, we will get the values of d and z.

For ax + by = gcd(a,b), the extended gcd algorithm could look something like (source):

 function xgcd(a, b) { 

   if (b == 0) {
     return [1, 0, a];
   }

   temp = xgcd(b, a % b);
   x = temp[0];
   y = temp[1];
   d = temp[2];
   return [y, x-y*Math.floor(a/b), d];
 }

This algorithm runs in time O(log(m)^2), assuming |a| < m, and is generally more efficient than exponentiation.

I don't know if there is an inbuilt function for this in javascript. I doubt if there is, and I am a fan of algorithms, so I thought you might want to give this approach a try. You can fiddle with it and change it to handle your range of values and I hope it gets you started in the right direction.