RSA: wie komme ich vom ggt zur vielfachsummendarstellung?

[qwertz543221]

ok ich hab hier mal ein schriftliches beispiel gerechnet, nur wie kann man das
in einen algorithmus packen? - d.h. wie lasse ich den algorithmus die umformungen bis zur vielfachsummendarstellung machen?
- so wie man es auf papier macht (s.o.) geht das kaum, oder?


Beispiel
p=31,q=97
n=3007
phi=2880
e=23

ed+k*phi=1=ggt(23,2880)

2880=125*23+ 5
23= 4* 5+ 3
5= 1* 3+ 2
3= 1* 2+ 1(**)
1= 1* 1+ 0


(**)
1=2-1*1

1=2-1(3-1*2)=2*2-1*3

1=2(5-1*3)-1(23-4*5)
=2*5 - 2*3 - 1*23 + 4*5
=6*5 - 2*3 - 1*23

1=2(5 - 1*3) - 1*3
=2*5 - 3*3

1=2(2880 - 125*23) - 3(23 - 4*5)
=2*2880 - 250*23 - 3*23 + 12*5
=2*2880 - 253*23 + 12*5

1=2*2880 - 250*23 - 3*23 + 12(2880 - 125*23)

1=14*2880 - 1753*23
1= k*phi + d*e
1=1 ok


da d<0:
d=-1753 + phi (vielfaches von phi)
d=1127


=>e=23,d=1127,n=3007