RSA: wie komme ich vom ggt zur vielfachsummendarstellung?

[Klaus01]

Delphi-Quellcode:

function TRSA.Gcd(n, m: Int64): Int64;
begin
  if m = 0 then
    Result := n
  else
    Result := Gcd(m, n mod m);
end;

Schau Dir zur folgenden Funktion mal diesen Link an - und auch mal durcharbeiten.

Delphi-Quellcode:

function TRSA.extEuclidian(e,phi:Int64;var gcd:Int64):Int64;
var
  u,v,t : Array[1..3] of Int64;
  q : Int64;
  i : Byte;

begin
  u[1] := 1;
  u[2] := 0;
  u[3] := phi;
  v[1] := 0;
  v[2] := 1;
  v[3] := e;
  while v[3] <> 0 do
    begin
      q := u[3] div v[3];
      for i:=1 to 3 do
        begin
          t[i] := u[i] - q * v[i];
        end;
      move(v[1],u[1],3*sizeOf(Int64));
      move(t[1],v[1],3*sizeOf(Int64))
    end;

  result := u[2];
  if u[2] < 0 then
    result := u[1];
  gcd := u[3];
end;

Grüße
Klaus