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) |
Was der chinesische Restsatz ist
Der chinesische Restsatz löst Systeme von Kongruenzen der Art **„welche Zahl lässt bei Teilung durch 3 den Rest 2, durch 5 den Rest 3 und durch 7 den Rest 2?“**. Sind die Moduln alle paarweise teilerfremd, so gibt es genau eine Lösung innerhalb des durch ihr Produkt gesetzten Bereichs. Dieses Werkzeug nimmt bis zu fünf Kongruenzen und gibt die kleinste nichtnegative Lösung samt der allgemeinen zurück.
**Behandelt wird allein die klassische Form – jene, in der alle Moduln teilerfremd sind.** Teilen zwei von ihnen einen Teiler größer als eins, so lässt sich das System auf diesem Weg nicht lösen, und eine Meldung sagt es; der verallgemeinerte Satz für nicht teilerfremde Moduln liegt außerhalb des Umfangs. **Moduln müssen ganze Zahlen ab 2 sein**, und die Reste werden von selbst in den Bereich von null bis unter ihren Modul gebracht, sodass Werte auf oder über dem Modul sowie negative zulässig sind. Gerechnet wird mit ganzen Zahlen beliebiger Genauigkeit, eine Grenze der Stellenzahl gibt es also nicht.
So benutzen Sie den Rechner
- Rest und Modul eintragen Geben Sie je Kongruenz den Rest a und den Modul n an. Sie stehen für x ≡ a (mod n).
- Weitere Kongruenzen hinzufügen Über „Kongruenz hinzufügen“ reihen Sie bis zu fünf auf. Je mehr es sind, desto weiter der Bereich – das Produkt der Moduln –, über den die Lösung eindeutig bleibt.
- Lösen Drücken Sie auf Lösen, und Sie erhalten die kleinste nichtnegative Lösung samt der allgemeinen Lösung modulo dem Produkt der Moduln.
- Den Rechenweg verfolgen Zu jeder Kongruenz stehen Nᵢ (das Produkt der Moduln ohne den eigenen) und Mᵢ (das Inverse von Nᵢ). Sie dienen dem Prüfen einer von Hand gerechneten Lösung.
- Teilerfremde Moduln sind erforderlich Eine Meldung, die Moduln seien nicht teilerfremd, heißt, dass zwei von ihnen einen Teiler teilen – etwa 4 und 6. Sehen Sie die Zusammenstellung noch einmal an.
Tipps für die Nutzung
- 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.
Wofür sich der Satz eignet
Übungen zur Zahlentheorie und Prüfungsvorbereitung
Er dient dem Prüfen einer von Hand gerechneten Lösung. Da auch Nᵢ und Mᵢ erscheinen, lässt sich einengen, wo sich ein Fehler eingeschlichen hat.
Kryptographische Verfahren lernen
Die CRT-Optimierung, die die RSA-Entschlüsselung beschleunigt, wendet diesen Satz unmittelbar an. Der Mechanismus lässt sich in Zahlen verfolgen.
Finden, wann Zyklen zusammenfallen
Die Zeitpunkte, zu denen Ereignisse verschiedener Perioden zusammentreffen, lassen sich als System von Kongruenzen schreiben.
Das klassische Problem nachvollziehen
Die „unbekannte Zahl“ des Sunzi Suanjing – Rest 2 bei 3, 3 bei 5 und 2 bei 7 – ist 23 modulo 105. Tragen Sie es so ein und sehen Sie selbst.
Wenn Sie die verwandten zahlentheoretischen Werkzeuge wollen
Zu Inversen und Kongruenzen selbst siehe Modulare Arithmetik; zu größten gemeinsamen Teilern ggT und kgV; zur Zerlegung Primfaktorzerlegung.
Begriffe rund um den chinesischen Restsatz
- Chinesischer Restsatz
- Der Satz, der besagt, dass ein System von Kongruenzen mit teilerfremden Moduln eine eindeutige Lösung modulo deren Produkt besitzt.
- Kongruenz
- Ein Ausdruck der Form x ≡ a (mod n), der sagt, dass der Rest von x bei Teilung durch n gleich a ist.
- Modul
- Die Zahl, durch die geteilt wird. Hier auf ganze Zahlen ab 2 beschränkt.
- Teilerfremd
- Zwei ganze Zahlen, deren größter gemeinsamer Teiler 1 ist. Der klassische Restsatz verlangt, dass je zwei der Moduln teilerfremd sind.
- Paarweise teilerfremd
- Bei drei oder mehr Zahlen: dass je zwei von ihnen teilerfremd sind. Eine Menge kann den größten gemeinsamen Teiler 1 haben, ohne paarweise teilerfremd zu sein.
- Modulares Inverses
- Das x, das a·x ≡ 1 (mod n) erfüllt. Im Restsatz tritt es beim Finden von Mᵢ, dem Inversen von Nᵢ, auf.
- Erweiterter euklidischer Algorithmus
- Der Algorithmus, der neben dem größten gemeinsamen Teiler die Bézout-Koeffizienten liefert. Er ist es, der ein modulares Inverses berechnet.
- Allgemeine Lösung
- Die kleinste nichtnegative Lösung samt jedem ganzzahligen Vielfachen des Produkts der Moduln, hinzugefügt – geschrieben in der Form x ≡ 23 (mod 105).
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.