I am trying to take ed = 1 mod((p-1)(q-1)) and solve for d, just like the RSA algorithm.

e = 5, (p-1)*(q-1) = 249996

I've tried a lot of code in javascript such as:

function modInverse(){
var e = 5;
var p = 499;
var q = 503;
var d = e.modInverse((p-1) * (q-1));
DisplayResult(d, "privateKeyResultLabel")
}

or

function modInverse(){ 
System.out.println(BigInteger.valueOf(5).modInverse(BigInteger.valueOf(249996)));
}

I just can't figure out the correct way to solve for d, the modular inverse, in javascript.

I am trying to take ed = 1 mod((p-1)(q-1)) and solve for d, just like the RSA algorithm.

e = 5, (p-1)*(q-1) = 249996

I've tried a lot of code in javascript such as:

function modInverse(){
var e = 5;
var p = 499;
var q = 503;
var d = e.modInverse((p-1) * (q-1));
DisplayResult(d, "privateKeyResultLabel")
}

or

function modInverse(){ 
System.out.println(BigInteger.valueOf(5).modInverse(BigInteger.valueOf(249996)));
}

I just can't figure out the correct way to solve for d, the modular inverse, in javascript.

• javascript
• algorithm
• rsa
• inverse
• modular-arithmetic

• 8 System.out.println? That's Java, not Javascript. – Barmar Commented Nov 18, 2014 at 2:55
• Embarassing... I'm really new to coding. I need it for javascript not java then! I know there is a modInverse() function is javascript. I just dont know how to properly use it. – Lizziej Commented Nov 18, 2014 at 2:56
• 1 How do you know there is a modInverse() in JavaScript? Because I'm pretty sure there isn't a built-in function for that. – Matti Virkkunen Commented Nov 18, 2014 at 3:07
• No, there is certainly no built-in function for that (JavaScript's standard library is quite minimal). You might find libraries built by others which have such a function, but definitely not in the browser itself. – Qantas 94 Heavy Commented Nov 18, 2014 at 3:09

2 Answers 2

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.

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