RSA	Nachricht-zu-Zahl modulo-Rechnen modulares Potenzieren Algorithmus von Euklid Euler-Funktion Satz von Euler modulares Inverses Primfaktorzerlegung Primzahlen finden Schlüsselpaar Angriff Sicherheit Pfad: Startseite / Fächer / Informatik / Kryptologie / RSA / Algorithmus von Euklid
Autor: mk 29.03.2011 15:54 1377	Algorithmus von Euklid

Algorithmus von Euklid

Python

def ggt(a,b):
    """
    berechnet iterativ den ggt von a und b
    """
    while b > 0:
        (a,b) = (b,a%b)
    return a

def ggtr(a,b):
    """
    berechnet rekursiv den ggt von a und b
    """
    if b == 0:
        return a
    else:
        return ggtr(b,a%b)

Wieso funktioniert der euklidische Algorithmus?

Ersetzt man a durch a₀ und b durch a₁, so stellt sich der Algorithmus als eine Folge von Gleichungen dar.

a₀ = a₁q₁ + a₂   mit 0 ≤ a₂ < a₁

a₁ = a₂q₂ + a₃   mit 0 ≤ a₃ < a₂

a₂ = a₃q₃ + a₄   mit 0 ≤ a₄ < a₃

⁝

a_n-2 = a_n-1q_n-1 + a_n   mit 0 ≤ a_n < a_n-1

a_n-1 = a_nq_n + a_n+1

Man erhält eine absteigende Folge von Resten a₁ > a₂ > a₃ > ... . Da es unterhalb von a₁ nur endlich viele Zahlen ≥ 0 gibt und die Reste alle ≥ 0 sind, muss es ein n mit der Eigenschaft a_n+1 = 0 geben. Die letzte Gleichung zeigt a_n|a_n-1. Damit und mit der vorletzten Gleichung folgt a_n|a_n-2. Analog erhält man a_n|a_n-3 ,..., a_n|a₁, a_n|a₀ . Damit ist klar, dass (1) a_n|ggt(a₀,a₁) gilt. Umgekehrt zeigt die erste Gleichung von oben, dass der ggt(a₀,a₁) auch a₂ teilt. Aus der zweiten Gleichung folgt, dass der ggt(a₀,a₁) auch a₃ teilt. Setzt man die Schlussweise fort, so erhält man schließlich (2) ggt(a₀,a₁)|a_n. Aus (1) und (2) folgt

a_n = ggt(a₀,a₁).

Delphi

  function ggt(a,b : int64) : int64;
  var
    r : int64;
  begin
    a := abs(a); b := abs(b);
    r := b;
    while r > 0 do
    begin
      r := a mod b;
      a := b;
      b := r;
    end;
    result := a;
  end;

euklid.zip