Eine Klasse von Algorithmen, die eine rationale Zahl p/q aus ihrem Bild modulo einer ganzen Zahl N oder aus einer approximativen modularen Residue rekonstruieren, unter Größenbeschränkungen für Zähler und Nenner, meist mittels Kettenbrüche oder erweitertem euklidischem Algorithmus.

Prinzip

Interpretiere das Residuum r ≡ p·q^{-1} (mod N) als rationale Näherung r/N und berechne Konvergenten über Kettenbrüche oder nutze erweiterten ggT, um kleine ganze Zahlen (p,q) mit |p|≤P, 0

Demonstration

Konkretes Beispiel: N=97, r ≡ 57 soll p/q mit q≤12 entsprechen. Die modulare Inverse von 12 ist 89, 5·89≡57 (mod 97), daher lässt sich r=57 als 5/12 rekonstruieren mittels Kettenbruch/erweitertem ggT unter der Schranke q≤12.

Fehlanwendung

Rekonstruktion ohne gültige Größenbeschränkungen (zu großer Nenner) oder aus Residuen bei zu kleinem N durchzuführen, was zu falschen rationalen Kandidaten oder mehreren spuriösen Lösungen führen kann.

Konsequenz

Ermöglicht die Wiedergewinnung exakter rationaler Koeffizienten aus modularen Rechnungen, modulare Rekonstruktion in der Computeralgebra und rationale Interpolation, und vermeidet große Ganzzahlarithmetik bis zur Nachbearbeitung.

Umkehrung

Die Vorwärtsabbildung (p/q modulo N zu r reduzieren) ist einfach; die Rekonstruktion invertiert diese Abbildung, verlangt aber Größenbeschränkungen — ohne diese entsteht Mehrdeutigkeit statt eindeutiger Wiederherstellung.

Abgrenzung

Benötigt explizite Schranken für Zähler und Nenner und ein N, das groß genug ist, Kollisionen zu vermeiden; gilt für rationale Zahlen mit moderaten Größen und für ganze Moduln; nicht anwendbar auf irrationale Zahlen oder Rationale mit arbiträr großem Nenner relativ zu N.

Semantische Spannung

Spannung zwischen Äquivalenzklassen modulo N (viele rationale Zahlen können dasselbe Residuum liefern) und der durch Größenbeschränkungen erzielten Eindeutigkeit; zudem Spannung zwischen Kettenbruchmethoden und gitter/ggT‑basierten Ansätzen.

Synthese

Rationale Rekonstruktion verbindet modulare Arithmetik und diophantische Approximation: unter gegebenem Residuum und Größenbeschränkungen liefern Kettenbrüche oder erweiterter ggT die eindeutige kleine rationale Zahl, deren modulare Abbildung mit dem Residuum übereinstimmt.