Kryptologi opgave!

Skal du finde d eller hvordan?

Ja... Jeg skal finde b, undskyld, det havde jeg helt glemt at skrive!
Ser det så rigtigt ud den første omskrivning jeg har lavet, eller er det helt forkert??

#2:
Ej, nu må du lige bestemme dig :)

Skal du finde d (som er nævnt i kongruensen) eller b, og hvad betegner b i givet fald?

//Epsilon

Det må i sgu undskylde, lige en fejl fra min side, det er d jeg skal finde, ikke b! Har det med at bytte rundt på dem!

#4:
Jeg ved ikke, hvad I har arbejdet med inden for emnet; men jeg ville nok ty til den euklidiske algoritme.

I ved sikkert, at den største fælles divisor gcd(a,b) af to heltal, a,b E Z, er det entydigt bestemte naturlige tal, som går op i både a og b.

Den (udvidede) euklidiske algoritme udsiger, at for givne a,b E Z findes p,q E Z således, at

ap + bq = gcd(a,b) (*),

og algoritmen giver en effektiv metode til at bestemme p og q, nemlig ud fra division med rest.

I opgaven ønskes bestemt d, som løser kongruensen

11d (kongruent med) 1 (mod 24)

Per definition betyder dette, at 24 går op i '11d - 1', dvs. at vi kan finde c E Z, så

11d - 1 = 24c

Bemærk, at gcd(11,24) = 1, og flytter vi rundt, har vi

11d + 24(-c) = 1

Men dette er jo et udtryk af formen (*). Lad os skrive

11d + 24q = 1

Nu kommer det essentielle. Division med rest giver successivt:

(1) 24 = 2*11 + 2 (rest 2)
(2) 11 = 5*2 + 1 (rest 1)
(3) 2 = 2*1 + 0

Tricket er nu at skrive 11, 24 og resterne som linearkombinationer af 11 og 24. Bemærk, hvorledes vi bruger (1)-(3)

24 = 1*24 + 0*11
11 = 0*24 + 1*11
2 = 24 - 2*11 = 1*24 - 2*11
1 = 11 - 5*2 = 1*11 - 5(1*24 - 2*11) =
(-5)*24 + 11*11

Heraf ses, at d = 11 (q = -5) er en løsning, og det er da i hvert fald sandt, thi

11*11 - 1 = 120 = 5*24

Er der mon andre løsninger? Tja, det vil jeg overlade til dig at spekulere lidt over. :)

//Epsilon

Jeg er godt med på det, indtil efter dette led:

Men dette er jo et udtryk af formen (*). Lad os skrive

11d + 24q = 1

Ikke helt med på den måde man kan skrive det på?

#6:
Vi sætter q = -c, et helt tal (c er jo et helt tal). Det er blot notation for at gøre det helt tydeligt, at vi har et udtryk på formen (*), med a = 11, b = 24, gcd(a,b) = 1 og p = d.

//Epsilon

Det er jeg godt med på, det er mere hvordan jeg kommer videre derfra jeg ikke helt er med på?

#8:
Vi foretager division med rest. Jeg minder i den forbindelse om følgende:

Lad n > 0 være et helt tal. Så findes til ethvert m E Z præcis én rest r E N sådan, at

(*) m = qn + r,

hvor q E Z og 0 =< r < n. Vi omtaler dette som 'division (af m med n) med rest (r)'.

I praksis ser vi således, at resten af 24 ved division med 11 er 2;

(1) 24 = 2*11 + 2,

at resten af 11 ved division med 2 er 1;

(2) 11 = 5*2 + 1,

og at resten af 2 ved division med 1 er 0;

(3) 2 = 2*1 + 0

I dette trin går divisionen altså op.

Motivationen for disse divisioner med rest er måske ikke helt åbenlys. Det bygger på den observation, at hvis vi har to heltal, m og n, så gælder

gcd(m,n) = gcd(m-qn,n) for _alle_ q E Z

I al sin enkelhed siger dette, at et naturligt tal d (den største fælles divisor) går op i m og n, hvis og kun hvis d går op i m-qn og n.

Den grundlæggende observation er nu, at hvis vi dividerer m med n og skriver (jf. (*))

m = qn + r,

så får vi direkte, at

gcd(m,n) = gcd(r,n) = gcd(n,r)

og r < n. I (1)-(3) ses, hvorledes dette fungerer i praksis. Med m = 24 og n = 11 har vi da, at

gcd(24,11) = gcd(11,2) = gcd(2,1) = gcd(1,0) = 1.

Vi ved altså, at gcd(24,11) = 1, og (jf. #5) at der findes d og q, så

11d + 24q = 1

Den euklidiske algoritme er en metode til at bestemme d og q. Tricket er at skrive 11 og 24 samt ikke-nul resterne (2 hhv. 1 fra (1) og (2)) som en vægtet sum af 11 og 24. Det ses, at

24 = 1*24 + 0*11
11 = 0*24 + 1*11,

og af (1) og (2) fås

2 = 24 - 2*11 = 1*24 - 2*11
1 = 11 - 5*2 = 1*11 - 5(1*24 - 2*11) = (-5)*11 + 11*11

Dermed har vi produceret identiteten

11*11 + (-5)*24 = 1,

som nok ville have været svær at gætte sig til fra starten af.

En løsning til kongruensen

11d (kongruent med) 1 (mod 24)

er således d = 11. Og hermed vil jeg igen henvise til spørgsmålet sidst i #5.

//Epsilon

#9: En lille, men ikke ubetydelig korrektion:

1 = 11 - 5*2 = 1*11 - 5(1*24 - 2*11) = (-5)*24 + 11*11.

('(-5)*11' var en slåfejl).

//Epsilon