Modularitmetik - Affinkryptering
Hejsan. Jag har den affina funktionen
För att lösa denna, kan jag skriva om det såhär;
Hur går jag vidare sedan? Ska jag använda euklides på 34 och 25 eller 34 och 41 och sedan euklides extended eller inget av det?
Ja, den omskrivningen går väl.
Det jag skulle göra är att konstatera att
34x-25 ska vara delbart med 41 och därmed att det finns något tal y sådant att
34x-25=41y
eller om man så vill
43x-41y=25
Vilket är en diofantiskt ekvation man kan lösa med euklides algoritm.
Skulle det stå 34-41y = 25 eller ? Annars förstår jag inte riktigt :)
När jag kör euklides extended så får jag fram 1 = 41 * 5 +34 (-6)
x = 25(34 * (-6))
y = 25(41 * 5)
Vilket ger: 25 = 5125 - 5100
x:et skulle i mitt fall bli (-6) ? Vilket det inte kan vara då det ska vara mellan 0 - 41 ...
Det borde stått
34x-41y =25 på sista raden ja.
Jag tycker att det här med att utrrycka det hela i []-notation mest förvirrar ganska enkla resonemang och sista raden är enligt mig knasig då det finns flera likheter som inte är likheter. Vad den där 7:an kommer ifrån ser jag inte.
Nåväl poängen är att
34x - 41y = 25
har en lösning
x = 14, y = 11
Så x = 14 kommer att vara en lösning till moduloekvationen vilket ses via
34(14) - 41(11)= 25
[34(14) - 41(11)]= [25]
[34(14)]= [25]
[34(14) + 7]= [25 + 7]
[34(14) + 7]= [32]
Detta är samma som i din skrivning ovan med x = -150 dår [-150] = [14] mod 41.
Då förstår jag! Jag ser hur du får -150 till [14] mod 41 men inte hur du får 125 till [11] mod...?
Det finns ju oändligt många lösningar till dofantiska ekvationer och finns ju formler för att från en enda lösningar
kunna konstruera en allmänn lösning . Från denna allmänna lösning kan man sedan extrahera den lösning där talen är positiva och så små som möjligt vilket är vad jag gjort för att få mina tal.
Så jag har inte fått gått vägen via mod 41 utan via formeln. Relationen är inte så enkelt men x-variabeln är ändå sådan att alla lösningar man hittar ska vara giltiga så fungera bättre där.
Tack så jättemycket!!