Berechnungsverfahren

Herr A. hat in diesem Jahr einen runden Geburtstag gefeiert; gleichzeitig hat er auch ein volles Jahrsiebt vollendet. Wie alt ist Herr A. geworden? Die Antwort – 70 Jahre – ist nicht schwer zu erraten. Herr L. dagegen hat das letzte volle Jahrsiebt vor 2 Jahren vollendet; sein letzter runder Geburtstag liegt bereits 8 Jahre zurück. Wie alt ist Herr L.?

Interessant ist, dass tatsächlich auch das Alter x von Herrn L. durch diese beiden Angaben eindeutig festliegt, jedenfalls wenn man von einem realistischen Alter eines Menschen ausgeht, nämlich Jahre.

Problem

Die Zahl x ergibt bei ganzzahliger Division durch 7 den Rest 2 und bei ganzzahliger Division durch 10 den Rest 8. Welche Zahl ist x?

Die Zahl x lässt sich also darstellen als

x   =   s·7 + 2   =   t·10 + 8

oder allgemein

x   =   s·m + a   =   t·n + b

Anders ausgedrückt gilt

x ≡ a  (mod m)   und

x ≡ b  (mod n).

Die Zahlen m und n werden in diesem Zusammenhang als Moduln bezeichnet, die Zahlen a und b als die zugehörigen Reste.

Der sogenannte chinesische Restsatz sagt aus, dass wenn die Moduln m und n teilerfremd sind, es modulo m·n eine eindeutige Lösung x gibt.

Durch Anwendung des chinesischen Restsatzes lassen sich Berechnungen in ℤ_n zurückführen auf Berechnungen in ℤ_p0 ×  ...  × ℤ_pi-1, wobei p₀, ..., p_i-1 die Primfaktor­potenzen von n sind.

Berechnung

Da m und n teilerfremd sind, lässt sich der größte gemeinsame Teiler 1 darstellen als

1   =   u·m + v·n

Die Koeffizienten u und v sind hier nicht eindeutig bestimmt, sondern es gibt viele Werte für u und v, die die Gleichung erfüllen. Der erweiterte euklidische Algorithmus berechnet aus m und n den größten gemeinsamen Teiler sowie jeweils einen möglichen Wert für u und v.

Multi­plikation mit (b-a) ergibt

b-a   =   (b-a)·u·m + (b-a)·v·n

Durch Umordnen ergibt sich

(b-a)·u·m + a   =   -(b-a)·v·n + b

Damit sind die gesuchten Koeffizienten s und t für m und n gefunden. Somit ist

x  =  (b-a)·u·m + a

eine mögliche Lösung.

Gesucht ist jedoch die eindeutige Lösung modulo m·n. Um den Wert von x modulo m·n zu berechnen, genügt es, das Produkt (b-a)·u modulo n zu reduzieren, denn es ist

(b-a)·u mod n · m + a

 <   (b-a)·u mod n · m + m   (da a < m)

=  ((b-a)·u mod n + 1) · m

 ≤  ((n-1) + 1 ) · m

=  n · m

Somit ist

x  =  (b-a)·u mod n · m + a

die gesuchte, eindeutig bestimmte Zahl.

Implementierung

Der chinesische Restsatz lässt sich allgemein für k teilerfremde Moduln und zugehörige Reste formulieren.

Die folgende rekursive Funktion chineseRemainder erhält als Parameter eine Liste nn von Moduln und eine Liste rr von zugehörigen Resten. Wenn diese Listen nur aus jeweils einem Element bestehen, gibt die Funktion diese Elemente zurück. Ansonsten berechnet sie rekursiv zuerst die Zahl a modulo m, die sich nach dem chinesischen Restsatz aus der ersten Hälfte der n_i und r_i ergibt, und dann die Zahl b modulo n, die sich aus der zweiten Hälfte der n_i und r_i ergibt. Die Produkte m und n sind teilerfremd, da alle n_i unter­einander teilerfremd sind. Der Wert u wird durch die Funktion extgcd mithilfe des erweiterten euklidischen Algorithmus berechnet; die beiden anderen berechneten Werte g und v werden nicht gebraucht. Aus m und n sowie den zugehörigen Resten a und b lässt sich dann nach dem oben angegebenen Verfahren die Lösung x berechnen. Die Funktion gibt außer dieser Lösung x auch den zugehörigen Modul m·n zurück.

Es folgt die Implementierung in der Programmier­sprache Python. Es wird wiederum von der Möglichkeit der Tupel-Wert­zuweisung Gebrauch gemacht. Die Notation nn[:k] bezeichnet einen Ausschnitt (slice) aus der Liste nn vom Beginn bis zum Index k (aus­schließ­lich). In ähnlicher Weise bezeichnet nn[k:] einen Ausschnitt vom Index k (einschließ­lich) bis zum Ende der Liste.

Chinesischer-Restsatz-Algorithmus

Eingabe:

Liste nn von teilerfremden Moduln, Liste rr von Resten

Ausgabe:

Produkt der Moduln, Zahl x nach dem chinesischen Restsatz

Methode:

Der Vorteil dieser Implementierung nach dem Divide-and-Conquer-Prinzip besteht darin, dass in den unteren Rekursions­ebenen viele Berechnungen mit kleinen Zahlen stattfinden und erst in den oberen Rekursions­ebenen wenige Berechnungen mit großen Zahlen.

Implementierung in Haskell

Eine mögliche Implementierung in der funktionalen Programmier­sprache Haskell ist im Folgenden angegeben. Die Parameter der Funktion sind wiederum eine Liste nn von Moduln und eine Liste rr von zugehörigen Resten. Bestehen diese Listen nur aus einem Element n bzw. einem Element r, so wird (n, r) zurück­gegeben. Ansonsten wird rekursiv nach dem oben angegebenen Verfahren gerechnet.

Die Funktion extgcd führt die Berechnung des erweiterten euklidischen Algorithmus aus.

Beispiel

Übung

Auf der Demo

Stellen wir uns in Zehnerreihen auf, ist einer zu wenig. Stellen wir uns in Neunerreihen auf, ist ebenfalls einer zu wenig. So geht es weiter bis zu Zweierreihen, wo auch einer fehlt. Wieviele sind wir? (Unter 3000).

Hinweis: Bei der Anwendung des chinesischen Restsatzes müssen die Moduln teilerfremd sein.

In diesem Fall ist die Lösung sogar noch einfacher. Wenn die Reste alle gleich sind, so ergibt sich die Lösung als das kleinste gemeinsame Vielfache (kgV) der Moduln plus diesem Rest. Dieser Rest ist hier -1.

Literatur

[AHU 74]   A.V. Aho, J.E. Hopcroft, J.D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)

[CLRS 01]   T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. 2. Auflage, The MIT Press (2001)

[Lan 18]   H.W. Lang: Kryptografie für Dummies. Wiley (2018)

[Weitere Informationen]