RSA - Erweiterter Euklidischer Algorithmus

[galaxy2k]

Ich habe leider mit dem folgenden Algorithmus Probleme in der Hinsicht, dass mir einfach nicht klar wird, wann u0/v0 ihre Werte zugewiesen bekommen. Was rauskommen soll usw. hab ich begriffen und das u0 den privaten Schlüssel ,laut der Formel d = e^-1 1 mod n bzw. u*e + v*n0 = 1, repräsentiert ist auch klar. Nur leider sehe ich vor lauter Bäumen den Wald nicht mehr. Der Algorithmus selbst funktioniert und gibt mir auch den relevanten Wert zurück, nur leider hab ich die bereits erwähnten Verständnisprobleme. Ich hoffe, dass mir hier einer im Forum den Rekursivaufruf näher erläutern kann.

mfg g2k

Delphi-Quellcode:

Function TMathe.ggTerw(a,b: int64; var u,v: int64):int64; 
  var u0, v0:int64; 
begin 
  if b = 0 then Begin 
    result := a; 
    u := 1; 
    v := 0; 
  End else Begin 
    result := ggTerw(b, a mod b, u0, v0);//rekursiv 
    u := v0; 
    v := u0 - (a div b)*v0; 
  End; 
end; 

function TMathe.invers_mod(e,m: int64): int64; 
  var d,v: int64; 
begin 
  ggTerw(e,m,d,v); //der Funktionswert von ggT wird nicht benötigt 
  if d < 0 then d := d + m; 
  result := d; 
end;

[galaxy2k]

nochmal nach oben

Die Frage ist einfach , wieso die beiden Werte u0 und v0 nicht die ganze Zeit null bleiben ??

[mirage228]

Am Anfang sind die beiden Variablen ja noch nicht initialisiert (sie werden ja auch noch nicht benötigt, falls doch, gibts ne CompilerMeldung "Variable ... ist möglicherweise nicht initialisiert worden").
Sie werden erst bei b = 0 initialisiert und bei dem Abschnitt wo b = 0 ist, hört die Rekursion auf und die Prozedur geht so oft an der Stelle nach der Rekursion weiter (wo die beiden Vars schon gesetzt sind) wie oft die Rekursion aufgerufen wurde.

Ich hoffe das war verständlich und richtig.^^

mfG
mirage228