As a self response and with the intention of creating a repository for future reference on CRT implementation in javascript/typescript:
The first step is to implement Modular Multiplicative Inverse, where we are looking for an x such that:
a*x % modulus = 1
const modularMultiplicativeInverse = (a: bigint, modulus: bigint) => {
// Calculate current value of a mod modulus
const b = BigInt(a % modulus);
// Search for the smallest hypothesis as the number must lie between given modulus and 1
for (let hipothesis = 1n; hipothesis <= modulus; hipothesis++) {
if ((b * hipothesis) % modulus == 1n) return hipothesis;
}
// If not found, return 1
return 1n;
}
Following the article and the provided sample code:
const solveCRT = (remainders: bigint[], modules: bigint[]) => {
// Multiply all the moduli
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;
}
This application makes use of ES6 functions like reduce
To make it work with bigints, the array of remainders and modules should be based on ES2020's BigInt
Example:
x mod 5 = 1
x mod 59 = 13
x mod 24 = 7
// Define the problem and execute the function
// Parsing to BigInt can't be done here, but TypeScript will detect 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