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;