Kleine stelling van fermat

Kolio

Beste mensen,

Ik loop vast. Ik zie niet in hoe ik van de ene stap naar de andere kom. Hier komt het:

Ik weet

\(e*d Mod (p-1) = 1 \)

En nu zou ik met de kleine stelling van fermat ( a^p = a Mod p) aan het volgende moeten kunnen geraken

\( n^e^*^d Mod (p) = n \)

Ik zie alleen niet in hoe...

Wie kan mij helpen?

Bvd

EvilBro

Een begin:

\(n^{e \cdot d} = n^{(p-1)\cdot r + 1} = \cdots\)

Kolio

om eerlijk te zijn weet ik het nu nogsteeds niet. Het is ook geen opdracht ik probeer de theorie achter het cryptograferen te snappen. Dus misschien dat je het wil voorkauwen voor me :eusa_whistle:

EvilBro

Helemaal voorzeggen lijkt me niet nuttig, dus:

Je weet dat het volgende geldt:

\(e \cdot d \equiv 1 \mod (p-1)\)

De linker term moet dus de volgende vorm hebben:

\(e \cdot d = (p-1) \cdot r + 1\)

waarbij \(r\) een geheel getal is.

Nu weet je dat:

\(n^{e \cdot d} = n^{(p-1)\cdot r + 1} = n^{p\cdot r - r + 1} = n^{p\cdot r} \cdot n^{-r} \cdot n^{1} = \left(n^{r}\right)^{p} \cdot n^{-r} \cdot n\)

Vanaf hier denk ik dat je het zelf wel verder kan.

Kolio

sorry, kan er niks aan doen maar ik zie het echt niet...

Editje:

Ow wacht, dit zal wel een stapje zijn

\( (n^r)^p n^-^r n = n^r Mod[p] n^-^r n \)

Maar hoe zou dat dan in vredesnaam

\( n^e^d Mod[p] = n \)

moeten worden?

Klintersaas

Wel, als (volgens de kleine stelling van Fermat

\(a^p \equiv a \mod p\)

, wat is dan

\(\left(n^{r}\right)^{p} \cdot n^{-r} \cdot n \mod p\)

?

Of eenvoudiger, wat is

\(\left(n^{r}\right)^{p} \mod p\)

?

Kolio

nu snap ik het helemaal neit meer... Mod [p-1] ?? het is toch Mod[p]

Ik raak nu eerder verder van huis dan dat ik dichterbij kom...

EvilBro

Klinterklaas heeft een fout gemaakt. Zijn post zou ik even negeren. Probeer op het volgende eens antwoord te geven:

Stel:

\(a = x \cdot p + r\)

\(b = y \cdot p + s\)

Beantwoord nu:

\(a \mod p = \cdots\)

\(b \mod p = \cdots\)

\((a \mod p) \cdot (b \mod p) = \cdots\)

\(a \cdot b = \cdots\)

\((a \cdot b) \mod p = \cdots\)

Kolio

r

s

rs

(xp+r)(yp+s) = xyp^2+ryp+xps+rs

rs

Maar ik zie niet in hoe dit betrekking heeft tot mijn probleem

EvilBro

Maar ik zie niet in hoe dit betrekking heeft tot mijn probleem

Je zou gezien je antwoorden kunnen zien dat:

\((a \cdot b) \mod p \equiv ((a \mod p) \cdot (b \mod p)) \mod p\)

dus:

\(\left(n^{r}\right)^{p} \cdot n^{-r} \cdot n \mod p \equiv (\left(n^{r}\right)^{p} \mod p) \cdot (n^{-r} \cdot n \mod p) \mod p \)

Nu kun je Fermat toepassen.

Klintersaas

Klinterklaas heeft een fout gemaakt. Zijn post zou ik even negeren.

Mijn excuses, ik zag mijn copy/pastefout te laat en voor ik ze kon aanpassen was er al gereageerd.

Kolio

Dan krijg je dus

\(\left(n^{r}\right)^{p} \cdot n^{-r} \cdot n \mod p \equiv (\left(n^{r}\right)^{p} \mod p) \cdot (n^{-r} \cdot n \mod p) \mod p \)

\( = (n^r \mod p \mod p )(n\cdot n^{-r} \mod p) \mod p = (n^r \mod p )(n\cdot n^{-r} \mod p) \mod p \)

Maar hoe zou hier n uitkomen dan? (voel me echt dom onderhand)

EvilBro

\(\left(n^{r}\right)^{p} \cdot n^{-r} \cdot n \mod p \equiv (\left(n^{r}\right)^{p} \mod p) \cdot (n^{-r} \cdot n \mod p) \mod p \)

\( \equiv (n^r \mod p)(n\cdot n^{-r} \mod p) \mod p \equiv (n^r \cdot n\cdot n^{-r}) \mod p \)

Kolio

dat volg ik nog..

Alleen dan is

\( n^{ed} \mod p= n \mod p \)

Maar dit zou dan gelijk moeten zijn aan n, maar hoe?

Want ik moet de stap inzien dat

\( n^{ed} \mod p = n \)

EvilBro

Alleen dan is
\( n^{ed} \mod p= n \mod p \)

Ik vermoed dat dat ook het oorspronlelijke statement is.

Maar dit zou dan gelijk moeten zijn aan n, maar hoe?

Dat kan alleen als n kleiner is dan p. Als dat niet gegeven is dan kan het niet. Als dat wel gegeven is dan zijn de statements equivalent.

Wetenschapsforum

Laatste berichten

Nieuwsberichten

Kleine stelling van fermat

Kleine stelling van fermat

Re: Kleine stelling van fermat

Re: Kleine stelling van fermat

Re: Kleine stelling van fermat

Re: Kleine stelling van fermat

Re: Kleine stelling van fermat

Re: Kleine stelling van fermat

Re: Kleine stelling van fermat

Re: Kleine stelling van fermat

Re: Kleine stelling van fermat

Re: Kleine stelling van fermat

Re: Kleine stelling van fermat

Re: Kleine stelling van fermat

Re: Kleine stelling van fermat

Re: Kleine stelling van fermat