Chinesischer-Restsatz-Rechner (CRT) — Simultane Kongruenzen lösen
Löst ein System simultaner Kongruenzen x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂)... mit dem chinesischen Restsatz. Prüft automatisch, ob die Moduln paarweise teilerfremd sind, und liefert die kleinste nicht-negative Lösung sowie die allgemeine Lösung.
Beispielrechnung: das „Rätsel der unbekannten Zahl" aus dem Sunzi Suanjing
Ein klassisches Beispiel aus dem Sunzi Suanjing (dem „mathematischen Klassiker des Sunzi"), einem chinesischen Rechenbuch aus etwa dem 3. bis 5. Jahrhundert, das oft als Ursprung des chinesischen Restsatzes gilt. Die Frage „Welche Zahl lässt bei Division durch 3 den Rest 2, bei Division durch 5 den Rest 3 und bei Division durch 7 den Rest 2?" hat die Antwort 23, modulo 105.
| Bedingung 1 | x ≡ 2 (mod 3) |
|---|---|
| Bedingung 2 | x ≡ 3 (mod 5) |
| Bedingung 3 | x ≡ 2 (mod 7) |
| Lösung | x ≡ 23 (mod 105) |
Tipps
- Sind die Moduln (nᵢ) nicht paarweise teilerfremd, erscheint ein Fehler — mod 4 und mod 6 etwa teilen sich den Faktor 2, weshalb dieser Rechner das System nicht lösen kann (dafür wäre der verallgemeinerte CRT nötig).
- Du musst den Rest aᵢ nicht selbst reduzieren: Selbst wenn er negativ oder größer als nᵢ ist, normalisiert der Rechner ihn intern automatisch auf mod nᵢ, bevor er löst.
- Es lassen sich 2 bis 5 Kongruenzen hinzufügen. Das eignet sich für Rätsel, bei denen eine Zahl drei oder mehr periodische Bedingungen gleichzeitig erfüllen muss, etwa das klassische Rätsel „errate die Anzahl der Soldaten".
- Die allgemeine Lösung wird als x ≡ Ergebnis (mod N) angezeigt: Addiert man ein beliebiges Vielfaches von N zum Ergebnis, erfüllt das Resultat weiterhin alle ursprünglichen Kongruenzen.
Häufig gestellte Fragen
Übrigens – Von einem Rechenbuch aus dem 3. Jahrhundert zur Beschleunigung von RSA-Verschlüsselung
Der chinesische Restsatz geht auf ein Problem aus dem Sunzi Suanjing zurück, einem chinesischen Rechenklassiker, der vermutlich aus dem 3. bis 5. Jahrhundert n. Chr. stammt. Das berühmte „Rätsel der unbekannten Zahl" — finde eine Zahl, die bei Division durch 3, 5 und 7 die Reste 2, 3 bzw. 2 lässt — erfasste bereits den Kerngedanken des modernen Satzes: eine unbekannte Zahl aus mehreren Divisionsresten zu rekonstruieren.
Eine der praktisch wichtigsten modernen Anwendungen des chinesischen Restsatzes ist die Beschleunigung der RSA-Entschlüsselung. Dabei muss eine große Zahl potenziert und modulo einer zusammengesetzten Zahl n = p × q reduziert werden, wobei p und q große Primzahlen sind. Statt direkt modulo n zu rechnen, erlaubt der CRT, die Berechnung unabhängig modulo p und modulo q durchzuführen und die Ergebnisse anschließend zu kombinieren — eine als CRT-RSA bekannte Technik, die die Entschlüsselung theoretisch um fast das Vierfache beschleunigen kann und in vielen Kryptografie-Bibliotheken implementiert ist.
Dieses Tool unterstützt die klassische Form des Satzes, die voraussetzt, dass alle Moduln paarweise teilerfremd sind. Teilen sich die Moduln gemeinsame Faktoren (etwa mod 4 und mod 6), kann je nach Bedingungen dennoch eine Lösung existieren — deren Bestimmung erfordert jedoch den verallgemeinerten chinesischen Restsatz, der außerhalb des Umfangs dieses Tools liegt.