RSA: Privaten Schlüssel schneller berechnen

[Bjoerk]

Delphi-Quellcode:

function GreatestCommonDivisorAdvanced
  (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:= GreatestCommonDivisorAdvanced(B, A mod B, U0, V0);
    U:= V0;
    V:= U0-(A div B)*V0;
  end;
end;

function InversMod(A, B: int64): int64;
var
  V: int64;
begin
  GreatestCommonDivisorAdvanced(A, B, Result, V);
  if Result < 0 then Result:= Result+B;
end;