[quote='floorball92','http://www.informatik-forum.at/testing/forum/…2112#post572112']
Danach kommt e, eine relativ prime Zahl zu (p-1)(q-1), also (p-1)(q-1) -- müsste gehen.
[\QUOTE]
Ich glaub 1<e<(p-1)(q-1) muß gelten, d.h. e=(p-1)(q-1) darf nicht sein...
[quote='floorball92','http://www.informatik-forum.at/testing/forum/…2112#post572112']
Nun kommt mein erstes hartes Problem: d wird ja mit dem erweiterten euklidischen Algorithmus errechnet, mit dem Probierverfahren durch umstellen der Gleichung kann ich das, aber eine Funktion dazu krieg ich nicht auf die Reihe. (*ganz-vorsichtig-fragend* wird das mit einer rekursiven Funktion gelöst)[\QUOTE]
wikipedia hat da ein ganz einfaches bsp. dazu:
http://de.wikipedia.org/wiki/RSA-Kryptosystem
im prinzip is ja
e * d + k * phi(n) = ggt(e, phi(n)) = 1
phi(n)=(p-1)(q-1) hast du ja schon ausgerechnet, und e hast du auch schon bestimmt.
Wie du richtig gesagt hast kannst du jetzt mit dem erweiterten euklidschen algorithmus d
bestimmen. ich verwend jetzt mal die zahlen von dem wikipedia example:
e=23 und phi(n) = 120
23 * d + k * 120 = ggt (23, 120) =1
jetzt rechnest du den euklidschen algorithmus runter:
120=5*23+5
23=4*5+3
5=1*3+2
3=1*2+1
und mit dem erweiterten euklidschen algorithmus wieder in die andere richtung:
1= 3-1*2 = 3 - 1*(5-1*3) = 2*3 - 1*5 = 2*(23-4*5) -1*5 =
=2*23 -9*5 = 2*23 -9 * (120- 5*23)= 47 * 23 - 9 *120
=> d= 47 und k=-9
ich hoff das hilft ein bißchen weiter (und stimmt...)
andi