Chinese Remainder Theorem
Théorème des restes chinois : si les modules sont premiers entre eux deux à deux, un système de congruences admet une solution unique modulo leur produit.
Objectif
Décomposer l'arithmétique à grand module en arithmétique parallèle à petits modules, accélérant le calcul modulaire des grands nombres.
Mécanisme
Étant donné x≡a_i (mod n_i) avec les n_i premiers entre eux deux à deux, x a une solution unique mod N (N=∏n_i). Utilisez N_i=N/n_i, M_i=N_i^(-1) mod n_i, et x=∑a_i*N_i*M_i mod N.
Cas d’usage
- Accélération de RSA
- Arithmétique modulaire des grands nombres
- Algorithmes de théorie des nombres