我正在阅读模数乘法逆元的定义,据我所知:
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中是否有内置函数可以实现此功能。我怀疑是否有,而且我喜欢算法,所以认为您可能想尝试这种方法。您可以调整它并更改它以处理您的值范围,希望它能让您朝着正确的方向开始。
System.out.println
?这是Java语言的写法,不是Javascript。 - BarmarmodInverse()
函数?因为我非常确定它没有内置函数可以实现这个功能。 - Matti Virkkunen