Zum Inhalt springen

Erweiterter euklidischer Algorithmus

Aus FLBK-Wiki

Der erweiterte euklidische Algorithmus liefert nicht nur den größten gemeinsamen Teiler zweier Zahlen, sondern auch eine Gleichung, die ihn aus den beiden Zahlen zusammensetzt. Aus dieser Gleichung ergibt sich beim RSA-Verfahren die Zahl [math]\displaystyle{ d }[/math] des privaten Schlüssels.

Definition

Der erweiterte euklidische Algorithmus berechnet zu zwei natürlichen Zahlen [math]\displaystyle{ a }[/math] und [math]\displaystyle{ b }[/math] den größten gemeinsamen Teiler [math]\displaystyle{ \operatorname{ggT}(a; b) }[/math] und zwei ganze Zahlen [math]\displaystyle{ x }[/math] und [math]\displaystyle{ y }[/math] mit

[math]\displaystyle{ \operatorname{ggT}(a; b) = x \cdot a + y \cdot b }[/math]

Von Hand rechnet man meist in zwei Teilen: zuerst der euklidische Algorithmus mit seiner Divisionskette, danach das Rückwärtseinsetzen. Die Tabellenform erledigt beides in einem Durchgang.

Vielfachsummendarstellung

Die Gleichung [math]\displaystyle{ \operatorname{ggT}(a; b) = x \cdot a + y \cdot b }[/math] heißt Vielfachsummendarstellung des größten gemeinsamen Teilers: Er wird als Summe aus einem Vielfachen von [math]\displaystyle{ a }[/math] und einem Vielfachen von [math]\displaystyle{ b }[/math] geschrieben. Dass es solche Zahlen [math]\displaystyle{ x }[/math] und [math]\displaystyle{ y }[/math] immer gibt, sagt das Lemma von Bézout.

  • Einer der beiden Faktoren [math]\displaystyle{ x }[/math] und [math]\displaystyle{ y }[/math] ist in der Regel negativ.
  • Die Faktoren sind nicht eindeutig. Der Algorithmus liefert ein mögliches Paar.

Rückwärts einsetzen

  1. Die Divisionskette des euklidischen Algorithmus aufstellen.
  2. Jede Zeile nach ihrem Rest auflösen: Aus [math]\displaystyle{ a = k \cdot b + r }[/math] wird [math]\displaystyle{ r = a - k \cdot b }[/math].
  3. Mit der letzten Zeile beginnen, deren Rest nicht 0 ist. Aufgelöst stellt sie den größten gemeinsamen Teiler durch zwei Zahlen der Kette dar.
  4. Von unten nach oben vorgehen: Die kleinere der beiden Zahlen ist jeweils der Rest der nächsten Zeile darüber. Sie wird durch diese aufgelöste Zeile ersetzt, dann wird ausmultipliziert und zusammengefasst.
  5. Das wiederholen, bis nur noch [math]\displaystyle{ a }[/math] und [math]\displaystyle{ b }[/math] vorkommen.

Wichtig beim Zusammenfassen: Die Zahlen der Divisionskette bleiben als Zahlen stehen, nur ihre Faktoren werden zusammengerechnet. Wer ein Produkt aus Faktor und Kettenzahl ausrechnet, kann im nächsten Schritt nichts mehr ersetzen.

Tabellenform

Dieselbe Rechnung lässt sich ohne Rückwärtseinsetzen in einer Tabelle führen. Jede Zeile enthält einen Rest [math]\displaystyle{ r }[/math] und zwei Faktoren [math]\displaystyle{ x }[/math] und [math]\displaystyle{ y }[/math], für die [math]\displaystyle{ r = x \cdot a + y \cdot b }[/math] gilt.

  1. Die ersten beiden Zeilen enthalten die Zahlen selbst: [math]\displaystyle{ a = 1 \cdot a + 0 \cdot b }[/math] und [math]\displaystyle{ b = 0 \cdot a + 1 \cdot b }[/math].
  2. Für jede weitere Zeile wird der Quotient [math]\displaystyle{ k }[/math] bestimmt: Wie oft passt der letzte Rest ganz in den vorletzten?
  3. Der neue Rest und die neuen Werte von [math]\displaystyle{ x }[/math] und [math]\displaystyle{ y }[/math] entstehen alle nach derselben Regel: vorletzter Wert minus [math]\displaystyle{ k }[/math] mal letzter Wert.
  4. Die Tabelle endet mit der Zeile, deren Rest der größte gemeinsame Teiler ist. In ihr stehen [math]\displaystyle{ x }[/math] und [math]\displaystyle{ y }[/math].

Modulares Inverses

Das modulare Inverse einer Zahl [math]\displaystyle{ e }[/math] zum Modul [math]\displaystyle{ n }[/math] ist die Zahl [math]\displaystyle{ d }[/math] zwischen 1 und [math]\displaystyle{ n - 1 }[/math] mit

[math]\displaystyle{ e \cdot d \equiv 1 \pmod{n} }[/math]

Es übernimmt beim Rechnen mit Resten die Rolle des Kehrwerts (siehe Rechenregeln).

  • Das Inverse existiert genau dann, wenn [math]\displaystyle{ e }[/math] und [math]\displaystyle{ n }[/math] teilerfremd sind.
  • Berechnung: Der erweiterte euklidische Algorithmus liefert [math]\displaystyle{ 1 = x \cdot n + y \cdot e }[/math]. Modulo [math]\displaystyle{ n }[/math] fällt das Vielfache von [math]\displaystyle{ n }[/math] weg, es bleibt [math]\displaystyle{ y \cdot e \equiv 1 \pmod{n} }[/math]. Also ist [math]\displaystyle{ d = y \bmod n }[/math].
  • Ist [math]\displaystyle{ y }[/math] negativ, addiert man [math]\displaystyle{ n }[/math].

Beim RSA-Verfahren ist die Zahl [math]\displaystyle{ d }[/math] des privaten Schlüssels das modulare Inverse der Zahl [math]\displaystyle{ e }[/math] des öffentlichen Schlüssels zum Modul [math]\displaystyle{ \varphi(N) }[/math].

Umsetzung in Java

Die Methode rechnet in der Tabellenform. Sie merkt sich von jeder Spalte nur die letzten beiden Werte und liefert am Ende den größten gemeinsamen Teiler und die Faktoren [math]\displaystyle{ x }[/math] und [math]\displaystyle{ y }[/math] als Array.

public static long[] vielfachsumme(long a, long b) {
    long r0 = a;
    long r1 = b;
    long x0 = 1;
    long x1 = 0;
    long y0 = 0;
    long y1 = 1;
    while (r1 != 0) {
        long quotient = r0 / r1;
        long r2 = r0 - quotient * r1;
        long x2 = x0 - quotient * x1;
        long y2 = y0 - quotient * y1;
        r0 = r1;
        r1 = r2;
        x0 = x1;
        x1 = x2;
        y0 = y1;
        y1 = y2;
    }
    return new long[] {r0, x0, y0};
}

Für das modulare Inverse von [math]\displaystyle{ e }[/math] zum Modul [math]\displaystyle{ n }[/math] ruft man die Methode mit [math]\displaystyle{ n }[/math] und [math]\displaystyle{ e }[/math] auf. Ist das erste Element des Arrays 1, dann ist das dritte Element der Faktor [math]\displaystyle{ y }[/math] vor [math]\displaystyle{ e }[/math]. Ist er negativ, wird noch der Modul addiert (siehe Reste in Java).

Beispiele

Vielfachsummendarstellung durch Rückwärtseinsetzen bestimmen

Gesucht sind der größte gemeinsame Teiler von 179 und 69 und seine Vielfachsummendarstellung.

Divisionskette, jede Zeile nach dem Rest aufgelöst:

Zeile Division mit Rest nach dem Rest aufgelöst
1 [math]\displaystyle{ 179 = 2 \cdot 69 + 41 }[/math] [math]\displaystyle{ 41 = 179 - 2 \cdot 69 }[/math]
2 [math]\displaystyle{ 69 = 1 \cdot 41 + 28 }[/math] [math]\displaystyle{ 28 = 69 - 41 }[/math]
3 [math]\displaystyle{ 41 = 1 \cdot 28 + 13 }[/math] [math]\displaystyle{ 13 = 41 - 28 }[/math]
4 [math]\displaystyle{ 28 = 2 \cdot 13 + 2 }[/math] [math]\displaystyle{ 2 = 28 - 2 \cdot 13 }[/math]
5 [math]\displaystyle{ 13 = 6 \cdot 2 + 1 }[/math] [math]\displaystyle{ 1 = 13 - 6 \cdot 2 }[/math]
6 [math]\displaystyle{ 2 = 2 \cdot 1 + 0 }[/math] –

Der letzte Rest ungleich 0 ist der größte gemeinsame Teiler: [math]\displaystyle{ \operatorname{ggT}(179; 69) = 1 }[/math].

Rückwärts einsetzen, beginnend mit Zeile 5:

Rechnung Schritt
[math]\displaystyle{ 1 = 13 - 6 \cdot 2 }[/math] letzte Zeile mit Rest
[math]\displaystyle{ 1 = 13 - 6 \cdot (28 - 2 \cdot 13) }[/math] 2 ersetzt
[math]\displaystyle{ 1 = 13 \cdot 13 - 6 \cdot 28 }[/math] zusammengefasst
[math]\displaystyle{ 1 = 13 \cdot (41 - 28) - 6 \cdot 28 }[/math] 13 ersetzt
[math]\displaystyle{ 1 = 13 \cdot 41 - 19 \cdot 28 }[/math] zusammengefasst
[math]\displaystyle{ 1 = 13 \cdot 41 - 19 \cdot (69 - 41) }[/math] 28 ersetzt
[math]\displaystyle{ 1 = 32 \cdot 41 - 19 \cdot 69 }[/math] zusammengefasst
[math]\displaystyle{ 1 = 32 \cdot (179 - 2 \cdot 69) - 19 \cdot 69 }[/math] 41 ersetzt
[math]\displaystyle{ 1 = 32 \cdot 179 - 83 \cdot 69 }[/math] zusammengefasst

Die Vielfachsummendarstellung lautet [math]\displaystyle{ 1 = 32 \cdot 179 - 83 \cdot 69 }[/math].

Dieselbe Aufgabe in Tabellenform lösen

Jede Zeile erfüllt [math]\displaystyle{ r = x \cdot 179 + y \cdot 69 }[/math].

Schritt Quotient Rest [math]\displaystyle{ x }[/math] [math]\displaystyle{ y }[/math]
1 – [math]\displaystyle{ 179 }[/math] [math]\displaystyle{ 1 }[/math] [math]\displaystyle{ 0 }[/math]
2 – [math]\displaystyle{ 69 }[/math] [math]\displaystyle{ 0 }[/math] [math]\displaystyle{ 1 }[/math]
3 2 [math]\displaystyle{ 41 }[/math] [math]\displaystyle{ 1 }[/math] [math]\displaystyle{ -2 }[/math]
4 1 [math]\displaystyle{ 28 }[/math] [math]\displaystyle{ -1 }[/math] [math]\displaystyle{ 3 }[/math]
5 1 [math]\displaystyle{ 13 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ -5 }[/math]
6 2 [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ -5 }[/math] [math]\displaystyle{ 13 }[/math]
7 6 [math]\displaystyle{ 1 }[/math] [math]\displaystyle{ 32 }[/math] [math]\displaystyle{ -83 }[/math]

Die letzte Zeile liefert dieselbe Darstellung wie das Rückwärtseinsetzen: [math]\displaystyle{ 1 = 32 \cdot 179 - 83 \cdot 69 }[/math].

Modulares Inverses berechnen

Gesucht ist die Zahl [math]\displaystyle{ d }[/math] mit [math]\displaystyle{ 5 \cdot d \equiv 1 \pmod{108} }[/math].

Schritt 1: Divisionskette für 108 und 5, jede Zeile nach dem Rest aufgelöst:

Zeile Division mit Rest nach dem Rest aufgelöst
1 [math]\displaystyle{ 108 = 21 \cdot 5 + 3 }[/math] [math]\displaystyle{ 3 = 108 - 21 \cdot 5 }[/math]
2 [math]\displaystyle{ 5 = 1 \cdot 3 + 2 }[/math] [math]\displaystyle{ 2 = 5 - 3 }[/math]
3 [math]\displaystyle{ 3 = 1 \cdot 2 + 1 }[/math] [math]\displaystyle{ 1 = 3 - 2 }[/math]
4 [math]\displaystyle{ 2 = 2 \cdot 1 + 0 }[/math] –

Der letzte Rest ungleich 0 ist 1, also sind 108 und 5 teilerfremd, und das Inverse existiert.

Schritt 2: rückwärts einsetzen

Rechnung Schritt
[math]\displaystyle{ 1 = 3 - 2 }[/math] letzte Zeile mit Rest
[math]\displaystyle{ 1 = 3 - (5 - 3) }[/math] 2 ersetzt
[math]\displaystyle{ 1 = 2 \cdot 3 - 5 }[/math] zusammengefasst
[math]\displaystyle{ 1 = 2 \cdot (108 - 21 \cdot 5) - 5 }[/math] 3 ersetzt
[math]\displaystyle{ 1 = 2 \cdot 108 - 43 \cdot 5 }[/math] zusammengefasst

Schritt 3: Inverses ablesen

Aus [math]\displaystyle{ 1 = 2 \cdot 108 - 43 \cdot 5 }[/math] folgt [math]\displaystyle{ (-43) \cdot 5 \equiv 1 \pmod{108} }[/math], denn das Vielfache von 108 fällt modulo 108 weg. Der Faktor -43 ist negativ, deshalb wird der Modul addiert:

[math]\displaystyle{ d = -43 + 108 = 65 }[/math]

Probe: [math]\displaystyle{ 5 \cdot 65 = 325 = 3 \cdot 108 + 1 }[/math]

Methode in Java aufrufen

Die Methode vielfachsumme aus dem Abschnitt Umsetzung in Java liefert ein Array mit drei Werten:

  • vielfachsumme(179, 69) liefert 1, 32, -83, also [math]\displaystyle{ 1 = 32 \cdot 179 - 83 \cdot 69 }[/math] wie im ersten Beispiel.
  • vielfachsumme(108, 5) liefert 1, 2, -43. Das erste Element ist 1, also gibt es das modulare Inverse von 5 zum Modul 108. Aus dem dritten Element folgt [math]\displaystyle{ d = -43 + 108 = 65 }[/math].
  • vielfachsumme(108, 6) liefert 6, 0, 1. Das erste Element ist nicht 1: Zu 6 gibt es zum Modul 108 kein Inverses.