在JavaScript中计算模逆

Question

我想要解决ed = 1 mod((p-1)(q-1))的问题，就像RSA算法一样。请帮我翻译出d的值。

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

我已经在javascript中尝试了很多代码，例如：

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

或者

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

我就是想不出在JavaScript中计算模反元素d的正确方法。

- Lizziej

---

System.out.println？这是Java语言的写法，不是Javascript。 - Barmar

有点尴尬...我对编程真的很新。我需要它用于JavaScript而不是Java！我知道在JavaScript中有一个modInverse()函数，但我不知道如何正确使用它。 - Lizziej

你怎么知道 JavaScript 中有 modInverse() 函数？因为我非常确定它没有内置函数可以实现这个功能。 - Matti Virkkunen

不，肯定没有内置的函数可以做到这一点（JavaScript 的标准库相当简单）。你可能会发现其他人编写的库中有这样的功能，但绝对不会在浏览器本身中找到。 - Qantas 94 Heavy

Answer 1

我正在阅读模数乘法逆元的定义，据我所知：

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

根据您的情况：

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

可以再次从维基百科条目中得知，可以使用扩展欧几里得GCD算法来计算模反元素，该算法执行以下操作:

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.

在您的情况下，方程式可能是这样的：

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

因此，如果我们将该算法应用于这种情况，我们将获得d和z的值。

对于方程ax + by = gcd(a,b)，扩展的欧几里得算法可能会像这样（来源）：

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];
}

假设|a|<m，则此算法运行时间为O(log(m)^2)，通常比指数运算更有效。

我不知道JavaScript中是否有内置函数可以实现此功能。我怀疑是否有，而且我喜欢算法，所以认为您可能想尝试这种方法。您可以调整它并更改它以处理您的值范围，希望它能让您朝着正确的方向开始。

- Vivek Pradhan

---

你可以实现扩展欧几里得算法而不使用递归，这样它就可以在常数空间中运行。 - icktoofay

非常感谢。我知道代码肯定与扩展欧几里得算法有关。我不确定该如何存储值。使用数组是个不错的选择！ - Lizziej

Answer 2

这个模块逆运算的实现可以接受任何类型的输入。如果不支持输入类型，则返回NaN。此外，它不使用递归。

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

- Dipu