Zahlentheoretische Algorithmen der Kryptografie Chinesischer Restsatz

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.

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.

Multiplikation 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 q von Moduln und eine Liste r 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 q_i und r_i ergibt, und dann die Zahl b modulo n, die sich aus der zweiten Hälfte der q_i und r_i ergibt. Die Produkte m und n sind teilerfremd, da alle q_i untereinander teilerfremd sind. Mithilfe des erweiterten euklidischen Algorithmus extgcd wird der Wert u berechnet; die Werte g und v werden nicht verwendet. 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-Wertzuweisung Gebrauch gemacht (so liefert etwa die Funktion extgcd ein Tupel von drei Werten). Die Notation q[:k] bezeichnet einen Ausschnitt (slice) aus der Liste q vom Beginn bis zum Index k (ausschließlich). In ähnlicher Weise bezeichnet q[k:] einen Ausschnitt vom Index k (einschließlich) bis zum Ende der Liste.

def chineseRemainder(q, r):
    if len(q)==1:
        return q[0], r[0]
    else:
        k=len(q)//2
        m, a=chineseRemainder(q[:k], r[:k])
        n, b=chineseRemainder(q[k:], r[k:])
        g, u, v=extgcd(m, n)
        x=(b-a)*u%n*m+a
    return m*n, x

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.

Beispiel

Literatur

Weiter mit:   [Faktorisierung: Quadratisches Sieb]   oder

H.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 26.02.2010   Updated: 22.04.2012