Kleinste Lösung
Modul
Moduln

    Gleichungen

    Mehr über den chinesischen Restsatz

    Rechner für den chinesischen Restsatz

    Zählt man einen Haufen Dinge zu dritt, bleiben 2 übrig, zu fünft 3, zu siebt 2: Es sind 23, oder 128, oder 233, alle 105 eine Lösung. Das ist die Aufgabe aus dem Sunzi Suanjing, die dem chinesischen Restsatz seinen Namen gab. Geben Sie ein beliebiges Kongruenzsystem x ≡ a (mod n) ein, mit so vielen Gleichungen und so großen Zahlen, wie Sie möchten, und sehen Sie die Lösung, den Rechenweg mit Ihren Zahlen und ein Bild, warum es funktioniert. Können die Gleichungen nicht alle gelten, nennt der Rechner die beiden, die sich widersprechen, und zeigt, warum. Geben Sie die Gleichungen x ≡ a (mod n) ein, eine pro Zeile: a ist der Rest und n der Modul. Mit Gleichung hinzufügen, oder mit Enter im letzten Modul, kommt eine Zeile dazu, mit × wird eine entfernt. Ganze Zahlen mit bis zu 200 Stellen sind möglich, und a darf negativ sein. Oder wählen Sie ein Rechenbeispiel. Die Kacheln zeigen die kleinste Lösung und wie oft sie sich wiederholt; darunter stehen die ersten positiven Lösungen und eine Probe für jede Gleichung. Das Bild markiert die Zahlen, die jede Gleichung erfüllen, und die Spalte, in der jede Zeile eine Markierung hat, ist die Lösung; die Resttabelle zeigt zwei Gleichungen auf einmal. Der Rechenweg steht mit Ihren Zahlen da, über die Lehrbuchkonstruktion oder über Einsetzen.

    Wie es funktioniert

    1. Geben Sie die Gleichungen x ≡ a (mod n) ein, eine pro Zeile, oder wählen Sie ein Rechenbeispiel wie Sunzis Aufgabe, den Eierkorb oder die Julianische Periode.
    2. Lesen Sie die kleinste Lösung, den Modul, mit dem sie sich wiederholt, und die ersten positiven Lösungen ab, jede mit Probe für jede Gleichung.
    3. Verfolgen Sie den Rechenweg Schritt für Schritt, über die Konstruktion oder über Einsetzen, und schalten Sie das Bild zwischen Zahlenstrahl und Resttabelle um.

    So funktioniert die Konstruktion

    Haben keine zwei Moduln einen gemeinsamen Teiler, lässt sich die Lösung direkt bauen. Multiplizieren Sie die Moduln: Bei Sunzis Aufgabe ist N = 3 × 5 × 7 = 105. Nehmen Sie für jede Gleichung Nᵢ = N / nᵢ, ein Vielfaches jedes anderen Moduls: 35, 21 und 15. Bestimmen Sie dann das Inverse yᵢ von Nᵢ mod nᵢ mit dem erweiterten euklidischen Algorithmus: 35 lässt bei Division durch 3 den Rest 2, und 2 × 2 = 4 ≡ 1 (mod 3), also y₁ = 2; 21 und 15 lassen den Rest 1, ihre Inversen sind also 1. Nun ist x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233, und 233 mod 105 = 23. Jeder Term passt zu seiner eigenen Gleichung und ist ein Vielfaches der anderen Moduln, also passt die Summe zu allen.

    Wenn die Moduln einen gemeinsamen Teiler haben

    Auch ein System, dessen Moduln gemeinsame Teiler haben, kann eine Lösung haben. Zwei Gleichungen x ≡ a (mod m) und x ≡ b (mod n) können genau dann zugleich gelten, wenn a − b ein Vielfaches von gcd(m, n) ist, und die Lösung wiederholt sich dann alle lcm(m, n) statt alle m × n. Zwei Busse, die zur Minute 5 und 11 abfahren, alle 12 und alle 18 Minuten, treffen sich zur Minute 29 und danach alle 36 Minuten, weil 11 − 5 = 6 ein Vielfaches von gcd(12, 18) = 6 ist. Aber x ≡ 1 (mod 4) und x ≡ 4 (mod 6) können nie zugleich gelten: Die erste macht x ungerade, die zweite gerade. Ein ganzes System hat genau dann eine Lösung, wenn jedes Paar seiner Gleichungen eine hat, und so findet der Rechner die beiden, die sich widersprechen.

    Häufig gestellte Fragen

    Was besagt der chinesische Restsatz?

    Haben keine zwei der Moduln n₁, n₂, … einen gemeinsamen Teiler, so gibt es für beliebige Reste a₁, a₂, … genau ein x von 0 bis N − 1 mit x ≡ aᵢ (mod nᵢ) für jedes i, wobei N das Produkt der Moduln ist. Jede andere Lösung unterscheidet sich davon um ein Vielfaches von N: Bei Sunzis Aufgabe sind die Lösungen 23, 128, 233 und so weiter, alle 105 eine.

    Warum heißt er chinesisch?

    Die älteste bekannte Aufgabe dieser Art steht im Sunzi Suanjing, einem chinesischen Rechenbuch aus dem 3. bis 5. Jahrhundert: Zu dritt, zu fünft und zu siebt gezählt, lässt eine Anzahl Dinge die Reste 2, 3 und 2. Qin Jiushao gab 1247 ein allgemeines Verfahren für solche Aufgaben an, und Carl Friedrich Gauß formulierte den Satz 1801 in seiner heutigen Form.

    Was, wenn die Moduln nicht teilerfremd sind?

    Dann gibt es vielleicht keine Lösung, und wenn es eine gibt, wiederholt sie sich alle kleinsten gemeinsamen Vielfachen der Moduln statt alle Produkte. Zwei Gleichungen passen zusammen, wenn ihre Reste modulo dem gcd ihrer Moduln gleich sind. Das Eierrätsel verwendet 2, 3, 4, 5, 6 und 7, die gemeinsame Teiler haben, und hat trotzdem eine Lösung: 301, die sich alle 420 wiederholt.

    Wie nutzt RSA den chinesischen Restsatz?

    Eine RSA-Nachricht zu entschlüsseln heißt, c^d mod n zu berechnen, mit n = p × q. Schneller ist es, c^d mod p und c^d mod q getrennt zu berechnen, mit dem Exponenten reduziert mod p − 1 und q − 1, und die beiden Ergebnisse mit dem Satz zusammenzufügen. Mit halb so langen Zahlen kostet jede der beiden Potenzen etwa ein Achtel der Arbeit, also ist die Entschlüsselung etwa viermal schneller, und die meiste RSA-Software macht es so.

    Wie groß dürfen die Zahlen sein?

    Bis zu 20 Gleichungen mit Zahlen von je bis zu 200 Stellen. Der Rechner arbeitet mit exakten ganzen Zahlen in Ihrem Browser, also ist die Lösung exakt, wie lang sie auch ist, und nichts wird irgendwohin gesendet.

    Bereit, es auszuprobieren?

    Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

    Zum Editor