Beviset for RSA-kryptering

Hele mit problem ligger i at jeg føler at der er 1 styks modulo n for meget på venstre side af kongruent tegnet. Det er jo nok 100 % bare mig, men måske er der en eller anden herinde der kan følge mig og forhåbentlig forklare mig hvorfor det er jeg kigger forkert på det!

Vink: Brug den sætning som du spurgte om her; den er en konsekvens af Eulers sætning.

Hej Wintermute! Tak for tippet, jeg kan sagtens se ligheden, men dog forvirrer det mig at der i udledningen af Eulers sætning, står lig med tegn mellem de 2 udtryk hvor der i beviset for RSA kryptering er kongruent-med tegn mellem de 2 udtryk, kan du måske forklare mig hvordan vi anvender sætningen så? :-)

Mvh. Dolphii

Du skal se på hvad forskellen er mellem ≡ og = i den forbindelse. I matematikken bruges ≡ til at sige at to tal har samme rest ved divisionen med et tal n. Dette har medført at man mange steder i regneark, programmeringssprog og matematikprogrammer bruger funktioner eller operatorer hvor betydningen er at det er resten. Når der står lighedsteg mener man altså at det er specifikt resten. Ved ≡ kan det godt være resten men behøver ikke at være det.

Hej Dolphii. Notationen

    x ≡ y    (mod k)

betyder: "Tallene x og y efterlader samme rest efter division med k". (Bemærk at kongruenstegnet ≡ ikke kan stå alene; det skal altid efterfølges af "(mod et-eller-andet-tal)".) Hvis vi bruger notationen fra sætningen fra den anden tråd, har vi dermed:

    x (mod k) = y (mod k)   ⇔   x ≡ y    (mod k)    (*)

og

    x (mod k) ≡ x    (mod k).                                (**)

Sætningen giver at m^ed (mod n) = m^{ed (mod φ(n))} (mod n), så vi får fra (*):

    m^ed ≡m^{ed (mod φ(n))}    (mod n).

Det følger fra (**) at

    m^ed (mod n) ≡ m^ed   (mod n).

Sammensæt nu disse kongruenser. :)

Det var dog en umådelig behagelig og forståelig måde du fik forklaret det på. Endnu en gang skal du have tak!

Mvh. Dolphii

Hej Wintermute!

Jeg forstår fuldstændig alt hvad du har skrevet i beviset, dog kan jeg ikke finde belæg for sætningen (**):"x (mod k) ≡ x    (mod k)." Jeg går ud fra det er en regneregel fra et eller andet sted eller hvordan? For hvis det er sandt, kan jeg sagtens forstå hele din forklaring, men i min opgave må jeg jo nødt til at henvise, hvilke regler jeg anvender, hvis du forstår :-)

Mvh. Dolphii

Hej Dolphii. Beklager det sene svar; har først lige opdaget dit indlæg. Udsagnet du spørger om følger fra betydningen af notationen: Husk at "x (mod k)" betyder: "Den rest som fremkommer når man dividerer k op i x". Og notationen

    x ≡ y    (mod k)

betyder: "Tallene x og y efterlader samme rest efter division med k". For at vise udsagnet

    x (mod k) ≡ x    (mod k)

skal vi altså vise at den rest der fremkommer når man dividerer "x (mod k)" med k er lig med den rest der fremkommer når man dividerer x med k.

Hvis vi dividerer k op i x, får vi x = q·k + r, hvor q er et eller andet heltal, og hvor r (=resten) opfylder ulighederne 0 ≤ r < k. Per definition af notationen "x (mod k)" har vi at x (mod k) = r. Hvis vi dividerer tallet x (mod k) = r med k, så får vi r = 0·k + r. Dette viser:

    rest ved division af k op i x = r = rest ved division af k op i "x (mod k)",

hvilket var hvad vi skulle vise. Beklager at det blev lidt langt. Jeg gør det måske mere kompliceret end det behøver at være. Hovedsagen er at huske hvad al notationen betyder. :)

Nej det var meget forståeligt! Tak for svaret! Jeg har nu afleveret min opgave og har ikke skrevet det ind, men jeg føler jeg fik forklaret beviset tilstrækkeligt alligevel :-)

Mvh. Dolphii