在 JavaScript 中实现中国剩余定理

Question

我一直在尝试解决 Advent of Code 2020 day 13 part 2 task. I found a lot of hints talking about something called Chinese Remainder Theorem. I have tried some implementations following npm's nodejs-chinesse-remainders 但这个实现似乎很旧（2014 年）并且还需要额外的库来处理 Big Int 案例。

如何实现模乘逆？我如何重构 npm 模块中定义的 CRT 算法，我为其提供了 link?

Answer 1

作为自我回应，目的是制作一个 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

为了与 bigints 一起工作，余数和模块的数组应该对应于 ES2020 的 BigInt

例如：

  x mod 5 = 1
  x mod 59 = 13
  x mod 24 = 7

// Declare the problem and execute function
// You can not parse them to BigInt here, but TypeScript will complain of operations between int and bigint
const remainders : bigint[] = [1, 13, 7].map(BigInt)
const modules: bigint[] = [5, 59, 24].map(BigInt)

solveCRT(remainders, modules) // 6031

在 JavaScript 中实现中国剩余定理

Implementing Chinese Remainder Theorem in JavaScript

javascript

typescript

algorithm

crt