Utiliser le Chinese Remainder Theorem
Le CRT solves systèmes de modular congruences. Apprendre le algorithme et its applications en RSA optimization et secret sharing.
- 1
The CRT states: if moduli m1, m2, ..., mn are pairwise coprime, then the system x ≡ a1 (mod m1), x ≡ a2 (mod m2), ..., x ≡ an (mod mn) has a unique solution modulo M = m1 * m2 * ... * mn. The CRT is used in RSA decryption (using p and q separately, then combining via CRT — 4x faster) and in Shamir's Secret Sharing.
- 2 Théorème des restes chinois →
Solve a system of congruences. Enter the remainders [a1, a2, ...] and moduli [m1, m2, ...]. The tool computes the solution x and the combined modulus M. Verify: x mod m1 = a1, x mod m2 = a2, etc.
- 3 Calculatrice de PGCD →
Verify that the moduli are pairwise coprime (gcd(mi, mj) = 1 for all i ≠ j). If any pair shares a common factor, the CRT does not apply directly — the system may have no solution or multiple solutions.
Questions fréquentes
- How does CRT speed up RSA?
- RSA decryption computes m = c^d mod n, where n = p*q. Using CRT: compute m_p = c^(d mod p-1) mod p and m_q = c^(d mod q-1) mod q separately (smaller exponents and moduli), then combine with CRT. This is 4x faster because the two exponentiations use half-size numbers and can be parallelized.
- What if the moduli are not coprime?
- The CRT requires pairwise coprime moduli. If they are not, the system may have no solution (if the congruences are inconsistent) or multiple solutions. Check pairwise GCDs first. For non-coprime moduli, use the generalized CRT or solve by substitution.