[FEATURE REQUEST] Implement Chinese Remainder Theorem

[SuprHUlk]

What would you like to Propose?

Problem Statement:
Given several pairwise coprime moduli ( n1, n2, ..., nk ) and integers ( a1, a2, ..., ak ), the goal is to find an integer ( x ) such that:

x = a1 ( mod n1)
x = a2 ( mod n2)
.
.
.
x = ak ( mod nk)

This problem can be efficiently solved using the Chinese Remainder Theorem (CRT). The CRT provides a method for finding a unique solution modulo the product of the moduli ( N = n1 X n2 X ... X nk ), where ( N ) is the least common multiple of all moduli.

Issue details

The Chinese Remainder Theorem is a powerful algorithm used for solving systems of simultaneous congruences. It has applications in cryptography (like RSA), distributed computing, and error correction. The algorithm uses modular arithmetic and the extended Euclidean algorithm to find the modular inverses of the product of all moduli except one.

Approach:

• Input: A list of moduli ( n1, n2, ..., nk ) and their corresponding remainders ( a1, a2, ..., ak ).
• Output: The smallest ( x ) that satisfies the system of congruences ( x = ( mod ni ) ) for all ( i ).

Steps:

1. Compute ( N = n1 X n2 X ... X nk ).
2. For each ( ni ), compute ( Ni = N/ni ) and the modular inverse ( mi ) of ( Ni ) modulo ( ni ).
3. Sum the terms ( ai X Ni X mi ) for all ( i ), and reduce the result modulo ( N ).

Test Case

Input:

moduli: [3, 5, 7]

remainders: [2, 3, 2]

Explanation:
We are given the system of congruences:

x = 2 ( mod 3 )

x = 3 ( mod 5 )

x = 2 ( mod 7 )

• Compute ( N = 3 X 5 X 7 = 105 ).
• ( N1 = 35, N2 = 21, N3 = 15 ).
• Find the modular inverses: ( m1 = 2 ), ( m2 = 1 ), ( m3 = 1 ).

Final solution:

x = (2 X 35 X 2) + (3 X 21 X 1) + (2 X 15 X 1) (mod 105)
= 233 (mod 105) = 23

Expected Output:
The smallest solution ( x = 23 ).

Additional Information

This algorithm is highly efficient and has many practical applications, particularly in cryptography (such as RSA key generation), error detection in communication, and scheduling problems.

[07-Atharv]

Can i take this issue?

[saiteja9078]

i would like to take the issue ,can i? @SuprHUlk