Eine Rekonstruktionsmethode, die Reste einer ganzen Zahl (oder eines Polynoms) modulo mehreren paarweise teilerfremden Moduli kombiniert, um die ursprüngliche Zahl (oder das Polynom) modulo dem Produkt der Moduli wiederherzustellen; Eindeutigkeit gilt modulo diesem Produkt.

Prinzip

Nach dem Chinesischen Restsatz hat ein konsistentes Kongruenzsystem x ≡ r_i (mod m_i) mit gcd(m_i,m_j)=1 eine eindeutige Lösung modulo M = ∏ m_i; konstruktive Algorithmen setzen die Reste mittels modularer Inversen oder gemischtradarischer Darstellungen zusammen, um x mod M zu rekonstruieren.

Demonstration

Bei den Resten x ≡ 2 (mod 3), x ≡ 3 (mod 5) und x ≡ 2 (mod 7) berechnet man die eindeutige Lösung modulo 105 durch Kombination der Reste (hier x ≡ 23 (mod 105)), womit die ganze Klasse aus modularen Teilen rekonstruiert wird.

Fehlanwendung

CRT anzuwenden, wenn die Moduli nicht paarweise teilerfremd sind, ohne Konsistenz zu prüfen, oder zu glauben, CRT rekonstruiere die absolute ganze Zahl statt nur die Klasse modulo Produkt, kann zu falscher Rekonstruktion oder Mehrdeutigkeit führen.

Konsequenz

Korrekte CRT‑Rekonstruktion ermöglicht modulare Algorithmen: aufwändige Rechnungen modulo kleiner Primzahlen durchführen und Ergebnisse kombinieren, um Werte modulo eines großen zusammengesetzten Moduls zu erhalten; fördert effektive Parallelisierung und trägt zur rationalen/ganzen Rekonstruktion bei.

Umkehrung

Reduktion modulo jedes Moduls ist der Umkehrprozess: aus einer ganzen Zahl ihre Reste berechnen. In manchen Algorithmen wird CRT umgekehrt, indem eine modulare Rechnung in unabhängige Kleinteile zerlegt wird, um Effizienz zu gewinnen.

Abgrenzung

Erfordert paarweise teilerfremde Moduli für das Standard-Eindeutigkeitsresultat; Verallgemeinerungen auf nicht-coprime Moduli benötigen Verträglichkeitsprüfungen und können mehrere oder keine Lösungen liefern; außerdem sind Schranken erforderlich, um eine Restklasse auf ein kanonisches Ganzes anzuheben.

Semantische Spannung

Spannung zu Hensel-Lifting und rationaler Rekonstruktion: CRT kombiniert unabhängige modulare Daten global, Hensel-Lifting erhöht lokal p-adische Genauigkeit; rationale Rekonstruktion kann sowohl CRT als auch Schranken benötigen, um kleine rationale Zahlen wiederzugewinnen.

Synthese

Die Rekonstruktion nach dem Chinesischen Restsatz ist die konstruktive Zusammensetzung modularer Reste zu einer eindeutigen Restklasse modulo dem Produkt paarweise teilerfremder Moduli; sie ermöglicht globale Wiederherstellung aus lokalen modularen Rechnungen und bildet die Grundlage vieler modularer Algorithmen.