##  [Rationale Rekonstruktion](/de/node/62927) 

 Definition

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

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

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

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

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

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

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

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

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.