在JavaScript中实现中国剩余定理
我一直在尝试解决2020 年代码出现第 13 天第 2 部分的任务。我发现了很多关于中国剩余定理的提示。我在 npm 的nodejs-chiesse-remainders之后尝试了一些实现，但这个实现似乎很旧（2014）并且还需要额外的库来处理 Big Int 情况。
我怎样才能实现模块化乘法逆？我如何重构我提供链接的 npm 模块中定义的 CRT 算法？
回答
作为自我回应，目的是创建一个 wiki，以便为将来需要在 javascript/typescript 中实现 CRT 的人找到此解决方案：
首先想到的是实现Modular Multiplicative Inverse，对于这个任务，我们试图找到一个 x 使得：
a*x % modulus = 1
const modularMultiplicativeInverse = (a: bigint, modulus: bigint) => {
// Calculate current value of a mod modulus
const b = BigInt(a % modulus);
// We brute force the search for the smaller hipothesis, as we know that the number must exist between the current given modulus and 1
for (let hipothesis = 1n; hipothesis <= modulus; hipothesis++) {
if ((b * hipothesis) % modulus == 1n) return hipothesis;
}
// If we do not find it, we return 1
return 1n;
}
然后按照您提供的文章和示例代码进行操作：
const solveCRT = (remainders: bigint[], modules: bigint[]) => {
// Multiply all the modulus
const prod : bigint = modules.reduce((acc: bigint, val) => acc * val, 1n);
return modules.reduce((sum, mod, index) => {
// Find the modular multiplicative inverse and calculate the sum
// SUM( remainder * productOfAllModulus/modulus * MMI ) (mod productOfAllModulus)
const p = prod / mod;
return sum + (remainders[index] * modularMultiplicativeInverse(p, mod) * p);
}, 0n) % prod;
}
这样您就可以使用 ES6 函数，例如 reduce
为了与 bigint 一起使用，余数和模块的数组应该对应于 ES2020 的BigInt
例如：
x mod 5 = 1
x mod 59 = 13
x mod 24 = 7
x mod 5 = 1
x mod 59 = 13
x mod 24 = 7