Erweiterter Euklidischer Algorithmus

[Meisterschmied]

Noch mal Abend an alle!

Es geht mir wie immer um RSA, diesmal um den Erweiterten Euklidischen Algorithmus. Wie kann ich die normale Variante

Delphi-Quellcode:

procedure TForm1.AdvancedGcd(a, b : integer);
var
  x1, xtmp, y1, ytmp, r, t, q : integer;
begin
  // Erweiterter Euklidischer Algorithmus
  x0 := 1; x1 := 0;
  y0 := 0; y1 := 1;
  t  := 1;

  while b <> 0 do
    begin
      r := a mod b;
      q := a div b;
      a := b;
      b := r;
      xtmp := x1;
      ytmp := y1;
      x1 := q*x1 + x0;
      y1 := q*y1 + y0;
      x0 := xtmp;
      y0 := ytmp;
      t  := -t;
    end;

    x0 := t*x0;
    y0 := -t*y0;

end;

so umschreiben, dass ich zum Beispiel bei den Werten a=3 und b=220 nicht die Resultate x0 := -73 und y0 = 1 bekomme, die ich beim RSA-Verfahren nicht gebrauchen kann, sondern die Werte x0 = 147 und y0 = -2?

Ich persönlich hab nicht mal einen Ansatz? Schon mal besten Dank

Thanks,

Meisterschmied

[mirage228]

x0 * (-2) + 1
y0 * (-2)

?

mfG
mirage228

[Meisterschmied]

Glaubst du, dass das allgemein anwendbar ist? Oder war das geraten?

Meisterschmied

[mirage228]

ich hab einfach mal nachgedacht wie ich von dem x,y der funktion auf deine x,y komme...

mfG
mirage228

[negaH]

Code:

 b = 220
x0 = -73
--------
x0 = 147

-73 mod 220 = 147 !

Dein Algorithmus arbeitet also korrekt.

Achso, jetzt müssen wir noch den Unterschied von mod zu rem erklären.

mod sollte nach der Reduktion eigentlich immer Zahlen liefern mit dem Vorzeichen des Modulis, mathematisch gesehen.
rem sollte so arbeiten wie es mod in Delphi macht. D.h. rem liefert das Vorzeichen der zu reduzierenden Zahl.

D.h. mathematisch gesehen arbeitet der mod Operator in Delphi falsch und müsste korrekter weise rem heissen.

Gruß Hagen