Chinesischer Restsatz Rechner

Löse x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ... mit dem erweiterten euklidischen Algorithmus – Schritt für Schritt

Schnellbeispiele

Rest (aᵢ)

Modul (mᵢ)

Kongruenz

Was ist der Chinesische Restsatz (CRT)?

Der Chinesische Restsatz ist eines der ältesten Ergebnisse der Zahlentheorie. Er besagt: Wenn m₁, m₂, ..., mₙ paarweise teilerfremde positive ganze Zahlen sind (jedes Paar hat einen ggT von 1), dann hat das System simultaner Kongruenzen:

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
⋮
x ≡ aₙ (mod mₙ)

eine eindeutige Lösung modulo M = m₁ × m₂ × ... × mₙ. Das bedeutet, es gibt genau eine ganze Zahl x im Bereich [0, M), die alle Kongruenzen gleichzeitig erfüllt, und alle weiteren Lösungen haben die Form x₀ + kM für eine beliebige ganze Zahl k.

Der Satz stammt aus dem Sunzi Suanjing (China, 3.–5. Jahrhundert n. Chr.), das die klassische Aufgabe stellte: „Finde eine Zahl, die bei Division durch 3 den Rest 2 lässt, bei Division durch 5 den Rest 3 und bei Division durch 7 den Rest 2." Die Antwort lautet x = 23.

CRT-Formel und Algorithmus

Der konstruktive Beweis des CRT liefert eine explizite Formel für die Lösung:

M = m₁ × m₂ × ... × mₙ
Mᵢ = M / mᵢ (Produkt aller Moduln außer mᵢ)
yᵢ ≡ Mᵢ⁻¹ (mod mᵢ) (modulares Inverses von Mᵢ)
x = (a₁·M₁·y₁ + a₂·M₂·y₂ + ... + aₙ·Mₙ·yₙ) mod M

Die zentrale Erkenntnis ist, dass jeder Term aᵢ·Mᵢ·yᵢ ≡ aᵢ (mod mᵢ) und ≡ 0 (mod mⱼ) für j ≠ i erfüllt, weil Mᵢ durch jedes mⱼ außer mᵢ teilbar ist. Dadurch werden die Terme „orthogonal" — jeder Term erfüllt genau eine Kongruenz, ohne die anderen zu stören.

Durchgerechnetes Beispiel — Sunzis Aufgabe

Löse: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)

Schritt 1: M = 3 × 5 × 7 = 105

Schritt 2: Mᵢ-Werte berechnen
  M₁ = 105/3 = 35
  M₂ = 105/5 = 21
  M₃ = 105/7 = 15

Schritt 3: Modulare Inverse yᵢ = Mᵢ⁻¹ (mod mᵢ) finden
  y₁ = 35⁻¹ mod 3: 35 ≡ 2 (mod 3), 2×2=4≡1 (mod 3) → y₁ = 2
  y₂ = 21⁻¹ mod 5: 21 ≡ 1 (mod 5), 1×1=1 (mod 5) → y₂ = 1
  y₃ = 15⁻¹ mod 7: 15 ≡ 1 (mod 7), 1×1=1 (mod 7) → y₃ = 1

Schritt 4: Kombinieren
  x = (2×35×2) + (3×21×1) + (2×15×1) mod 105
  x = 140 + 63 + 30 = 233 mod 105
  x = 23 ✓

Probe: 23 mod 3 = 2 ✓, 23 mod 5 = 3 ✓, 23 mod 7 = 2 ✓. Allgemeine Lösung: x = 23 + 105k für eine beliebige ganze Zahl k.

Der erweiterte euklidische Algorithmus

Das modulare Inverse yᵢ = Mᵢ⁻¹ (mod mᵢ) wird mit dem erweiterten euklidischen Algorithmus bestimmt, der ganze Zahlen x und y berechnet, die die Bézout-Identität erfüllen: a·x + b·y = ggT(a, b). Wenn ggT(a, b) = 1 ist, ist x (reduziert mod b) das modulare Inverse von a.

extGGT(a, b):
  wenn b = 0: gib (a, 1, 0) zurück
  (g, x₁, y₁) = extGGT(b, a mod b)
  gib (g, y₁, x₁ - ⌊a/b⌋·y₁) zurück

Beispiel: Inverses von 35 mod 3
  extGGT(2, 3): → (1, -1, 1), weil 2×(-1) + 3×1 = 1
  (-1 mod 3 + 3) mod 3 = 2 → Inverses = 2

Der Algorithmus läuft in O(log(min(a,b))) Zeit — deutlich schneller als reines Ausprobieren, besonders bei den großen Moduln, die in der Kryptografie zum Einsatz kommen.

Voraussetzungen für den CRT

Paarweise teilerfremde Moduln: ggT(mᵢ, mⱼ) = 1 für alle i ≠ j. Ohne diese Bedingung garantiert der Satz keine eindeutige Lösung.
Wertebereich der Reste: Technisch kann aᵢ eine beliebige ganze Zahl sein, aber die kanonische Form verwendet 0 ≤ aᵢ < mᵢ. Werte außerhalb dieses Bereichs lassen sich reduzieren: aᵢ mod mᵢ verwenden.
Positive Moduln ≥ 2: Jedes mᵢ muss eine positive ganze Zahl von mindestens 2 sein, damit die Kongruenz sinnvoll ist.
Mindestens 2 Gleichungen: Eine einzelne Kongruenz hat trivialerweise unendlich viele Lösungen; der CRT wird erst bei Systemen mit 2 oder mehr Gleichungen aussagekräftig.

Anwendungen des CRT

RSA-Kryptografie: Der CRT beschleunigt die RSA-Entschlüsselung um etwa das Vierfache, indem die Berechnung in zwei kleinere modulare Potenzierungen mit den Primfaktoren p und q des RSA-Moduls aufgeteilt wird.
Astronomie und Kalenderzyklen: Die Bestimmung, wann mehrere periodische Ereignisse (Mondmonat, Sonnenjahr, bestimmte Himmelskonstellationen) zusammenfallen, nutzt eine dem CRT ähnliche Argumentation. Der antike chinesische metonische Zyklus ist ein klassisches Beispiel.
Fehlerkorrigierende Codes: Redundante Restklassen-Zahlensysteme (RNS) nutzen den CRT, um Originalwerte aus teilweisen (möglicherweise fehlerhaften) modularen Resten zu rekonstruieren, was Fehlertoleranz ermöglicht.
Computerarithmetik: Restklassen-Zahlensysteme stellen große ganze Zahlen als Tupel von Resten modulo kleiner, paarweise teilerfremder Basen dar. Die Arithmetik auf diesen Tupeln lässt sich massiv parallelisieren, und der CRT rekonstruiert das Endergebnis.
Hashfunktionen und Secret Sharing: Shamirs Secret-Sharing-Verfahren nutzt Polynominterpolation über endlichen Körpern — ein Konzept, das eng mit den Ideen des CRT verwandt ist, um ein Geheimnis auf mehrere Parteien zu verteilen.

Häufig gestellte Fragen

Was ist der Chinesische Restsatz?

Der Chinesische Restsatz (CRT) ist ein grundlegendes Ergebnis der Zahlentheorie. Er besagt: Wenn m₁, m₂, ..., mₙ paarweise teilerfremde positive ganze Zahlen sind, dann hat das System x ≡ a₁ (mod m₁), ..., x ≡ aₙ (mod mₙ) eine eindeutige Lösung modulo M = m₁ × m₂ × ... × mₙ. Der Satz stammt aus dem Sunzi Suanjing (3.–5. Jahrhundert n. Chr.) und wird heute in der Kryptografie, der Informatik und der Kalenderrechnung eingesetzt.

Was sind paarweise teilerfremde Moduln?

Zwei ganze Zahlen sind teilerfremd, wenn ihr ggT gleich 1 ist — sie haben keinen gemeinsamen Primfaktor. Eine Menge {m₁, m₂, ..., mₙ} ist paarweise teilerfremd, wenn jedes Paar (mᵢ, mⱼ) einen ggT von 1 hat. Zum Beispiel sind {3, 5, 7} paarweise teilerfremd (alle prim und verschieden), während {4, 6} nicht teilerfremd sind, da ggT(4, 6) = 2. Primzahlen sind untereinander stets paarweise teilerfremd.

Wie finde ich ein modulares Inverses?

Das modulare Inverse von a modulo m ist eine Zahl y, sodass a·y ≡ 1 (mod m) gilt. Es existiert nur, wenn ggT(a, m) = 1 ist. Die effizienteste Methode ist der erweiterte euklidische Algorithmus, der ganze Zahlen x, y findet, die a·x + m·y = ggT(a, m) erfüllen. Für kleine Werte kann man auch durch Ausprobieren vorgehen: das y in {1, 2, ..., m−1} finden, für das (a × y) mod m = 1 gilt.

Was bedeutet die Lösung x₀ + kM?

Der CRT garantiert eine eindeutige Lösung im Bereich [0, M). Das ist x₀. Da sich das System mit der Periode M wiederholt, erfüllen auch alle Zahlen der Form x₀ + kM (für jede ganze Zahl k ∈ ℤ) das System. Also sind x₀ + M, x₀ + 2M, x₀ − M und so weiter alle gültige Lösungen. x₀ ist der kanonische (kleinste nicht-negative) Vertreter.

Kann der CRT auch bei nicht teilerfremden Moduln verwendet werden?

Der klassische CRT setzt paarweise teilerfremde Moduln voraus. Sind die Moduln nicht teilerfremd, existiert möglicherweise keine Lösung. Für das Paar x ≡ a (mod m) und x ≡ b (mod n) existiert genau dann eine Lösung, wenn ggT(m, n) den Wert (b − a) teilt. Falls sie existiert, ist die Lösung eindeutig modulo kgV(m, n) statt m×n. Diese Verallgemeinerung wird manchmal als „verallgemeinerter CRT" bezeichnet.

Was ist der erweiterte euklidische Algorithmus?

Der erweiterte euklidische Algorithmus ist eine Erweiterung des klassischen euklidischen Algorithmus (der den ggT durch wiederholte Division bestimmt). Die erweiterte Version berechnet zusätzlich die Bézout-Koeffizienten x, y, sodass a·x + b·y = ggT(a, b) gilt. Er läuft in O(log min(a, b)) Zeit. Wenn ggT(a, b) = 1 ist, ist der Koeffizient x das modulare Inverse von a modulo b. Das ist entscheidend für den CRT, RSA und viele weitere Algorithmen.

Wo wird der CRT im echten Leben eingesetzt?

Der CRT hat viele Anwendungen im echten Leben: (1) RSA-Kryptografie nutzt den CRT, um die Entschlüsselung um etwa das 4-Fache zu beschleunigen. (2) Astronomie — die Berechnung, wann Kalenderzyklen (z. B. der 19-jährige metonische Zyklus) übereinstimmen. (3) Fehlerkorrigierende Codes — redundante Restklassen-Zahlensysteme rekonstruieren Daten aus Teilinformationen. (4) Parallele Berechnung — Restklassen-Zahlensysteme ermöglichen übertragsfreie, parallele Arithmetik mit großen Zahlen. (5) Secret-Sharing-Verfahren — Verteilung geheimer Schlüssel auf mehrere Parteien.