RSA: wie komme ich vom ggt zur vielfachsummendarstellung?

[gammatester]

Hier eine korrigierte Fassung namens InvModKlaus:

- Zuerst wird das hier unsägliche move entfernt (Pascal kennt schon seit > 20 Jahren die Zuweisung von arrays).

- Dann wird der Bug beseitigt: Wenn das Inverse kleiner 0 ist wird natürlich nicht der andere Bezout-Koeffizient genommen, sondern einfach phi addiert.

- Dann stellen wir fest, daß wir die 1-er Komponenten gar nicht brauchen; wir werfen sie also raus.

- Dann noch ein Kommentar: was wird gemacht, Voraussetzungen, wann ist das Ergebnis gültig

Delphi-Quellcode:

{---------------------------------------------------------------------------}
function InvModKlaus(e,phi: Int64; var gcd: Int64): Int64;
  {-Modulare Inverse mit erweitertem Euklidischen Algorithmus; e, phi > 0;}
  { gcd=gcd(e,phi); result = e^-1 mod phi, nur gültig wenn gcd=1 !!}
var
  u,v,t: array[2..3] of Int64;
  q: Int64;
begin
  u[2] := 0;
  u[3] := phi;
  v[2] := 1;
  v[3] := e;
  while v[3] <> 0 do begin
    q := u[3] div v[3];
    t[2] := u[2] - q * v[2];
    t[3] := u[3] - q * v[3];
    u := v;
    v := t;
  end;
  result := u[2];
  if result<0 then result := result + phi;
  gcd := u[3];
end;