Une technique de reconstruction qui combine les restes d'un entier (ou d'un polynôme) modulo plusieurs modules deux à deux premiers entre eux pour retrouver l'entier original (ou le polynôme) modulo le produit des modules, l'unicité étant garantie modulo ce produit.

Principe

D'après le Théorème Chinois des Restes, un système cohérent de congruences x ≡ r_i (mod m_i) avec gcd(m_i,m_j)=1 admet une solution unique modulo M = ∏ m_i ; des algorithmes constructifs assemblent les restes à l'aide d'inverses modulaires ou de développements en base mixte pour récupérer x mod M.

Démonstration

Étant donné x ≡ 2 (mod 3), x ≡ 3 (mod 5) et x ≡ 2 (mod 7), calculer la solution unique modulo 105 en combinant les restes (ici x ≡ 23 (mod 105)), reconstruisant ainsi la classe entière à partir de ses morceaux modulaires.

Mauvaise application

Appliquer le CRT lorsque les modules ne sont pas deux à deux premiers sans vérifier la compatibilité, ou penser que le CRT reconstruit l'entier absolu plutôt que seulement la classe modulo le produit, conduit à des reconstructions globales erronées ou ambiguës.

Conséquence

Une reconstruction CRT correcte permet des algorithmes modulaires : effectuer des calculs lourds modulo des petits nombres premiers et combiner les résultats pour obtenir des valeurs modulo de grands modules composés, favorise la parallélisation et soutient la reconstruction rationnelle/entière.

Inversion

La réduction modulo chaque module est l'opération inverse : étant donné un entier, calculer ses restes. Dans certains algorithmes, on inverse le CRT en divisant un calcul modulaire en calculs indépendants de faible module pour des raisons d'efficacité.

Limite

Exige des modules deux à deux premiers pour le résultat d'unicité standard ; des généralisations existent pour modules non coprimes mais requièrent des vérifications de compatibilité et peuvent donner plusieurs ou aucune solution ; des bornes entières sont aussi nécessaires pour relever une classe de restes en entier canonique.

Tension sémantique

Tension avec le relèvement de Hensel et la reconstruction rationnelle : le CRT combine des données modulaires indépendantes globalement, tandis que Hensel élève localement la précision p-adique ; la reconstruction rationnelle peut nécessiter CRT et bornes pour retrouver des rationnels petits.

Synthèse

La Reconstruction par le Théorème Chinois des Restes est l'assemblage constructif de restes modulaires en une classe de restes unique modulo le produit de modules deux à deux premiers, permettant la récupération globale à partir de calculs modulaires locaux et constituant l'épine dorsale de nombreux algorithmes modulaires.