Chinesischer Restsatz: Geschichte und Aussage

Der Chinesische Restsatz (Chinese Remainder Theorem, CRT) ist eines der ältesten Ergebnisse der Zahlentheorie, erschien im chinesischen mathematischen Traktat von Sun Tzu (3.-5. Jhdt. n. Chr.) und wurde von Qin Jiushao im Shushu Jiuzhang (1247) verallgemeinert. Aussage: gegeben ein System von n Kongruenzen x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₙ (mod mₙ), wenn die Moduli m_i paarweise teilerfremd sind, existiert eine eindeutige Lösung x modulo M = m₁·m₂·...·mₙ. Wenn die Teilerfremdheit nicht gilt, existiert die Lösung nur, wenn die Kongruenzen verträglich sind (a_i ≡ a_j (mod gcd(m_i, m_j))) und ist eindeutig modulo lcm(m_i).

Konstruktive Formel

Für teilerfremde Moduli ist die Lösung x ≡ Σᵢ aᵢ·Mᵢ·yᵢ (mod M), wobei M = Πⱼ mⱼ, Mᵢ = M/mᵢ (Produkt aller Moduli außer m_i) und yᵢ = Mᵢ⁻¹ (mod mᵢ) das modulare Inverse ist, mit dem erweiterten Euklidischen Algorithmus berechenbar. Klassisches Sun-Tzu-Beispiel: „Wie viele Objekte mit Resten 2 mod 3, 3 mod 5, 2 mod 7?" → M=105, M₁=35, M₂=21, M₃=15; y₁=35⁻¹ mod 3 = 2 (35·2=70=23·3+1), y₂=21⁻¹ mod 5 = 1, y₃=15⁻¹ mod 7 = 1. x = 2·35·2 + 3·21·1 + 2·15·1 = 140 + 63 + 30 = 233 ≡ 23 (mod 105). Prüfung: 23 = 7·3+2 ✓, 23 = 4·5+3 ✓, 23 = 3·7+2 ✓.

Garner-Algorithmus (Effizienz)

Die direkte Konstruktion hat numerische Probleme für große Moduli (M kann explodieren). Garners Algorithmus verarbeitet die Kongruenzen einzeln in begrenzter Präzision: beginne mit x = a₁, dann x_neu = x + m₁·(a₂ − x)·(m₁⁻¹ mod m₂) mod (m₁·m₂), und iteriere für jede weitere Kongruenz. Hält Zwischenergebnisse klein, ideal für CPU mit fester Wortgröße (32 oder 64 Bit).

Anwendungen in der Kryptographie

RSA: bei der Entschlüsselung m = c^d mod n (mit n=pq, Produkt von Primzahlen) ermöglicht der CRT, m_p = c^d mod p und m_q = c^d mod q separat zu berechnen und dann über CRT zu m mod pq zu rekombinieren. Jede modulare Exponentiation ist ~4× schneller (2× kleinere Zahlen, Zeit O(k²) oder O(k log k), wobei k die Länge ist): 4× Gesamtbeschleunigung. Heißt RSA-CRT, Standard in OpenSSL, GnuPG, TLS. Vorsicht bei Seitenkanälen: Aciicmez-Schindler 2006 zeigten, dass CRT-Timing Informationen über p, q preisgibt.

Nicht teilerfremde Moduli (verallgemeinerter CRT)

Wenn gcd(m_i, m_j) = d > 1 für ein Paar, fällt die Teilerfremdheit. Kompatibilitätsbedingung: a_i ≡ a_j (mod d) für jedes Paar. Wenn verletzt, hat das System keine Lösung. Wenn erfüllt, existiert eine eindeutige Lösung modulo lcm(m₁, ..., mₙ). Methode: paarweise kombinieren mit Bezout-Identität. Für jedes Paar x ≡ a_i (mod m_i), x ≡ a_j (mod m_j): existieren u, v mit u·m_i + v·m_j = d; dann k = (a_j − a_i)/d; die Kombinierte ist x ≡ a_i + m_i·u·k (mod lcm(m_i, m_j)).

Verwandte Algorithmen

Shamir-Secret-Sharing: Geheimnis in n Fragmente aufteilen über ein Polynom vom Grad t−1 über F_p, Rekombination via CRT oder Lagrange-Interpolation. Lineares Hashing mit Multi-Primes: String auf Z/p₁ × Z/p₂, Rekombination via CRT für Hash mit nominaler Länge pk, aber mit Kollisionsresistenz p₁·p₂. Chinesischer Kalender: Kombination von Sonnenzyklus (10 Stämme), Tierkreis (12 Zweigen) und 60-Jahres-Zyklus via CRT (gcd(10,12)=2, kompatibel). Modulare Arithmetik auf GPU: FPGA und Spezial-Hardware nutzen CRT zur Beschleunigung von Big-Integer-Berechnungen (Mehrfach-Präzision).

Detailliertes Beispiel

System: x ≡ 1 (mod 5), x ≡ 2 (mod 7), x ≡ 3 (mod 9). M = 5·7·9 = 315. M₁ = 63, M₂ = 45, M₃ = 35. y₁ = 63⁻¹ mod 5: 63 ≡ 3 mod 5, 3⁻¹ mod 5 = 2 (3·2=6≡1). y₂ = 45⁻¹ mod 7: 45 ≡ 3 mod 7, 3⁻¹ mod 7 = 5. y₃ = 35⁻¹ mod 9: 35 ≡ 8 mod 9, 8⁻¹ mod 9 = 8 (8·8=64≡1). x = 1·63·2 + 2·45·5 + 3·35·8 = 126 + 450 + 840 = 1416 mod 315 = 156. Prüfung: 156 = 31·5+1 ✓, 156 = 22·7+2 ✓, 156 = 17·9+3 ✓.

Anwendung

Modus wählen: Lösen (Listen von Resten a_i und Moduli m_i CSV → x), Teilerfremdheit prüfen (Moduli-Liste → paarweise gcd), Zerlegen (x, Moduli → Reste), Nicht teilerfremd (System mit nicht teilerfremden Moduli → Lösung oder Unverträglichkeit). Positive ganze Zahlen, Moduli ≥ 2.

Aktualisiert im Juli 2026