Chinesischer Restsatz (CRT)

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.