Jag sitter och klurar på hur man beräknar olika tal.
n = summan av två primtal
p = primtal 1
q = primtal 2
e = ett tal som är relativt prima (p-1)*(q-1)
d = ett tal som uppfyller (d*e mod (p-1)*(q-1) = 1)
Att räkna ut n gör jag genom
n = p*q (exempelvis; 3*11=33)
Nu skall jag räkna ut e och det skall alltså vara ett tal som är udda samt är relativt prima 20, eftersom (2*10 = 20) Som svar på detta finner jag exempelvis tal som 7 och 3, men hur beräknar man det?
Sedan när jag nu har e undrar jag hur jag beräknar d. Då d är av rätt värde så är följande sant: d*e mod (p-1)*(q-1) = 1
Om jag antar att det inte spelar någon roll vilket tal e är, eller om det är större eller mindre än (p-1)*(q-1), så länge det uppfyller de givna villkoren verkar det enklast att testa med några olika värden på e, dock alltid udda. Jag inför också ytterligare några beteckningar för att slippa skriva så mycket, jag är lat... ;)
n = produkten av primtalen p och q
r = (p-1)*(q-1) (alltid jämnt)
s = (p-1)*(q-1)/2
Att två tal är relativt prima innebär ju att de inte har några gemensamma delare (förutom 1), eller att den största gemensamma delaren (SGD) = 1. Man kan också dividera r med 2 (för att inte behöva kolla så många värden på e) innan man kollar SGD eftersom r alltid är jämnt. Så SGD(e, s) ska vara 1. SGD räknas enklast ut med Euklides algoritm. Lite info om den finns t.ex. här: http://www.maths.lth.se/matematiklth/vitahyllan/diskret/diskretlos020824.pdf eller här: http://www.nada.kth.se/~tomaso/GruDat/Ovning1/#head5 men det är nog enklare att kolla in någon av böckerna för grundkursen i algebra.
Om vi tar ditt exempel med p = 3 och q = 11 så blir ju n = 33, r = 20 och s = 10.
Då testar vi de udda talen e = 3, 5, 7... för att se om SGD(e, 10) = 1 (mha Euklides algoritm). Om du är nöjd med det första tal du hittar har du alltså e = 3.
Villkoret för d, att d*e mod r = 1 innebär ju att d*e = m*r + 1 där m = 1, 2, 3...
Vi har alltså d*3 = m*20 + 1, och vi vet redan att SGD(3, 20) = 1 så den diofantiska ekvationen har en lösning. Lösningen hittar du även denna gång mha Euklides algoritm (himla bra grej han kom på den där greken ;)).
T.ex. får man fram lösningen d=7 och m=1 till ekvationen d*3 = m*20 + 1.
Typ så skulle nog jag göra, men jag har aldrig varit bra på effektiva algoritmer... ;)
PeW, jag skulle aldrig drömma om att göra dig till åtlöje. :f
