Modularitmetik - Affinkryptering

Hejsan. Jag har den affina funktionen

$y = f (x) = [34 x + 7]_{41} J a g s k a b e s t ä m m a x \in ℤ_{41} f ö r v i l k e t y = f (x) = [32]_{41}$

För att lösa denna, kan jag skriva om det såhär;

$[[34 x]_{41} + [7]_{41}]_{41} = [32]_{41} [34 x]_{41} = [25]_{41}$

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

$[34 x]_{41} = [25]_{41} [34 * (- 150)]_{41} = [- 5100]_{41} = [25]_{41} = [[25]_{41} + [7]_{41}] = [32]_{41} K a n j a g f o r m u l e r a m i g p å d e t t a s ä t t e t ?$

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

$(x_0, y_0)$ kunna konstruera en allmänn lösning $(x_n, y_n)$ . 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!!

Svara

Visa senaste svar