Zahlentheoretische Algorithmen der Kryptografie

Chinesischer Restsatz

 aufwärts

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.richtig oder falsch

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 kongruent a  (mod m)   und

x kongruent 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 ganze Zahlenn zurückführen auf Berechnungen in ganze Zahlenp0 ×  ...  × ganze Zahlenpi-1, wobei p0, ..., pi-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-au·m + (b-av·n

Durch Umordnen ergibt sich

(b-au·m + a   =   -(b-av·n + b

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

x  =  (b-au·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-au modulo n zu reduzieren, denn es ist

(b-au mod n · m + a

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

=  ((b-au mod n + 1) · m

kleiner gleich ((n-1) + 1 ) · m

n · m

Somit ist

x  =  (b-au 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.

Satz:  (Chinesischer Restsatz)

Gegeben sind k Element natürliche Zahlen teilerfremde Moduln n0, ..., nk-1 und zugehörige Reste r0, ..., rk-1. Die Zahl x, die jeweils modulo ni den Rest ri ergibt, ist modulo des Produktes aller ni eindeutig bestimmt.

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 ni und ri ergibt, und dann die Zahl b modulo n, die sich aus der zweiten Hälfte der ni und ri ergibt. Die Produkte m und n sind teilerfremd, da alle ni unter­einander teilerfremd sind. Mithilfe der Funktion modinverse wird der Wert u als multi­plikativ inverses Element von m modulo n berechnet. 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.

 

 

Algorithmus Chinesischer Restsatz
Eingabe:Liste nn von teilerfremden Moduln, Liste rr von Resten
Ausgabe:Produkt der Moduln, Zahl x nach dem chinesischen Restsatz
Methode:
def chineseRemainder(nn, rr):
    if len(nn)==1:
        return nn[0], rr[0]
    else:
        j=len(nn)//2
        m, a=chineseRemainder(nn[:j], rr[:j])
        n, b=chineseRemainder(nn[j:], rr[j:])
        u=modinverse(m, n)
        x=u*(b-a)%n*m+a
    return m*n, x

 

Der Vorteil dieser Implementierung nach dem Divide-and-Conquer-PrinzipErklärung 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 modinverse liefert auch hier das multi­plikativ inverse Element von m modulo n.

 

-- chinesischer Restsatz
chineseRemainder :: [Integer] -> [Integer] -> (Integer, Integer)
chineseRemainder [n][r] = (n, r)
chineseRemainder nn rr = (m*n, x)
        where
        k = length nn `div` 2
        (m, a) = chineseRemainder (take k nn) (take k rr)
        (n, b) = chineseRemainder (drop k nn) (drop k rr)
        u = modinverse m n
        x = (b-a) * u `mod` n * m + a

 

Beispiel

 

Moduln:   
Reste: 
Ergebnis:           

 

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 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Das Berechnungsverfahren nach dem chinesischen Restsatz und andere zahlentheoretische Algorithmen finden Sie auch in meinem Buch.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

 

Weiter mit:   [Faktorisierung: Quadratisches Sieb]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 26.02.2010   Updated: 28.02.2017
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik