I have been trying to solve 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 but this implementation seems to be quite old (2014) and also requires extra libraries for Big Int cases.

How could I implement the modular multiplicative inverse ? How could I refactor the CRT algorithm define in the npm module for which I provided a link?

1 Answer

As a self response and with the purpose of make a wiki to find this solution for those who in the future need a CRT implementation in javascript/typescript:

First think is to implement Modular Multiplicative Inverse, for this task what we try to find is 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); // 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;
}

Then following the article and the sample code you gave:

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

This way you use ES6 functions such as reduce

For this to work with bigints the array of remainders and modules should correspond to a ES2020's BigInt

E.g:

 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

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy