RSA: wie komme ich vom ggt zur vielfachsummendarstellung?

[qwertz543221]

hallo ich habe folgendes problem

Delphi-Quellcode:

function modinvers(e,n:ansistring):ansistring;
        var de,k:ansistring;
        begin
        k:='1';
        de:='1';
        while mathe.Modulo(de,e)<>'0'  do
        begin
        de:=mathe.produkt(k,phi);
        mathe.Plus1(de);
        mathe.Plus1(k);
        end;
        result:=mathe.Quotient(de,e);
       if mathe.ProduktModulo(result,e,n)<>'1'
          then showmessage('invmod falsch');  
        end;

das klappt soweit auch schon, nur - es ist einfach zu lngsam.
Daher hatte ich vor die "echte" berechnungsmethode zu benutzen, bei der habe ich leider einige probleme.

1)wähle p und q als primzahlen
2) n:=pq;
3) phi=(p-1)*(q-1)
4)wähle d mit ed mod phi=1
=> ed+k*phi=1=ggt(e,phi)

und hier hab ich probleme:

den einfachen euklidischen algorithmus kann ich durchführen, nur dann soll das ganze rückwärts wieder zur Vielfachsummendarstellung führen - dies ist der teil, der mir probleme bereitet.

(im moment noch auf dem papier - das coding folgt, sobald ich weiß wie ich vom ggt des einfachen euklidischen algo zur vielfachsummendarstellung komme, um das d zu berechnen. genau das ist mein problem)



beispiel:
p=11, q=13
n=143
phi=120
e=23

ed+k phi=1=ggt(e,phi)

120= 5*23+5
23= 4* 5+3
5= 1* 3+2
3= 1* 2+1
2= 1* 1+1 =>Ergebnis=1
1= 1* 1+0 =>Abbruchbedingung


Nur wie komme ich jetzt zur darstellung des ergebnisses als vielfachsumme, damit ich d ausrechnen kann? - und wie kann man das effizient und schnell (vom algorithmus her) in delphi beschreiben?

Danke für eure tips (ich hoffe ich hab nichts durcheinandergebracht, bisher hab ich das ganze wie oben durch den delphi code angegeben ausgerechnet)