Die Originalform des Chinesischen Restsatzes stammt aus einem Buch des chinesischen Mathematikers Sun Zi aus dem Jahr 100-300 n. Christi. Der CRT besitzt eine Aussage über simultane Kongruenzen für den Fall, dass die Moduln teilerfremd sind.
Chinesischer Restsatz Seien m1, m2, ... , mt paarweise teilerfremde, natürliche Zahlen und seien a1, a2, ... , at beliebig natürliche Zahlen (ai < mi, i = 1, ..., t). Dann hat die simultane Kongruenz x ≡ a1 mod m1 x ≡ a2 mod m2 : x ≡ at mod mt eine Lösung x, die eindeutig ist mod M mit M = m1 ∙ m2 ∙ … ∙ mt. |
Wenn eine Lösung x existiert, dann sind die Zahlen x + k ∙ M (k in Z) genau alle Lösungen.
Finden einer Lösung
Für jedes i sind die Zahlen mi und Mi := M / mi teilerfremd, also kann man mit dem erweiterten Euklidischen Algorithmus zwei Zahlen r und s finden, so dass
r ∙ mi + s ∙ Mi = 1
eine Darstellung des größten gemeinsamen Teilers (ggT) von mi und Mi als Linearkombination ergibt.
Wir erhalten mit der Zahl s die Inverse von Mi mod mi (s = Mi -1 mod mi).
Setzen wir nun ei := s ∙ Mi, dann gilt
ei ≡ 1 mod mi
ei ≡ 0 mod mj, j ≠ i
und die Zahlen e1,..., et werden dabei als Basis bezeichnet.
Die Zahl x := a1e1+a2e2 +...+ atet ist dann die gesuchte Lösung der simultanen Kongruenz.
Beispiel
Gesucht sei eine ganze Zahl x mit der Eigenschaft
x ≡ 2 mod 3
x ≡ 3 mod 5
x ≡ 2 mod 7
Hier ist M = 3 · 5 · 7 = 105,
M1 = M/3 = 35,
M2 = M/5 = 21,
M3 = M/7 = 15.
Mit Hilfe des erweiterten Euklidischen Algorithmus kann man stets ganze Zahlen r und s finden, so dass mi · r + Mi · s = 1 ist bzw.
r · mi + s · Mi = 1:
(-23) · 3 + 2 · 35 = 1, also e1 = s · M1 =70
(-4) · 5 + 1 · 21 = 1, also e2 = s · M2 = 21
(-2) · 7 + 1 · 15 = 1, also e3 = s · M3 = 15
Eine Lösung ist dann x = 2 · 70 + 3 · 21 + 2 · 15 = 233.
Wegen 233 ≡ 23 mod 105 sind alle anderen Lösungen x also kongruent zu 23 mod 105.
Eine praktische Demonstration der Anwendungen des Chinesischen Restsatzes (CRT) wird anhand der 3 Themen Astronomie und Planetenbewegung, Modulare Hin- und Rücktransformation und Secret Sharing mittels CRT gezeigt.