Hei. Jeg prøver å gå gjennom et enkelt eksempel av RSA systemet, men sitter litt fast. Jeg skal altså regne ut verdien av d, som dere ser i eksempelet under, men vet ikke helt hvordan det går til, vidre her. I boken jeg har lest litt i står det at man finner denne verdien ved Eklids algoritme, men vet ikke helt hvordan den går eller fungerer.
Her er stykket.
[tex]5 \cdot d=1(mod(11-1)\cdot (9-1))[/tex]
[tex]5\cdot d=1(mod80)[/tex]
Det beste hadde vært om jeg kunne fått et svar med en enkel forklaring ved siden av, men det er ikke et must. En rask utregning duger også...
Si ifra hvis dere trenger å vite noe mer.. Takk for svar, er relativit viktig.
mvh luringen
Hjelp ved bruk av Euklids algoritme?
Moderators: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga
Hvordan du vil gripe fatt en slik oppgave avhenger av hvor god kjenskap du har til modulær aritmetikk.
En lineær kongruens [tex]ax \equiv b \ \pmod{m}[/tex] har kun løsninger dersom [tex]\gcd(a, m)[/tex] er en faktor av b. gcd(a,b) er største felles faktor til a og b. Dersom gcd(a, m) | b, har kongruensen gcd(a, m) ulike løsninger modulo m. Løsningene kan du isåfall finne ved å dele vekk felles faktor i kongruensen [tex]\frac{a}{\gcd(a, m)}x \equiv \frac{b}{\gcd(a, m)} \ \pmod{\frac{m}{\gcd(a,m)}} \ \Rightarrow cx \equiv d \ \pmod n \\ x \equiv c^{-1}d \ \pmod n[/tex]
Over til problemet ditt:
[tex]7d \equiv 1 \ \pmod {160}[/tex]
gcd(7, 160) = 1, så denne har en unik løsning modulo 160.
Du kan nå bruke "prøv og feil," eller mer sofistikerte metoder (eulers phi-funksjon) til å finne inversen til 7 modulo 160. Vi observerer at 7*23=161 = 1 (mod 160)
[tex]23\cdot7d \equiv 23\cdot 1 \ \pmod{160} \\ d \equiv 23 \pmod {160}[/tex]
gjorde dette problemet noe klarere? Hvis du heller vil løse denne som en diofantisk likning, går det også an. Spør igjen hvis det er uforståelig.
En lineær kongruens [tex]ax \equiv b \ \pmod{m}[/tex] har kun løsninger dersom [tex]\gcd(a, m)[/tex] er en faktor av b. gcd(a,b) er største felles faktor til a og b. Dersom gcd(a, m) | b, har kongruensen gcd(a, m) ulike løsninger modulo m. Løsningene kan du isåfall finne ved å dele vekk felles faktor i kongruensen [tex]\frac{a}{\gcd(a, m)}x \equiv \frac{b}{\gcd(a, m)} \ \pmod{\frac{m}{\gcd(a,m)}} \ \Rightarrow cx \equiv d \ \pmod n \\ x \equiv c^{-1}d \ \pmod n[/tex]
Over til problemet ditt:
[tex]7d \equiv 1 \ \pmod {160}[/tex]
gcd(7, 160) = 1, så denne har en unik løsning modulo 160.
Du kan nå bruke "prøv og feil," eller mer sofistikerte metoder (eulers phi-funksjon) til å finne inversen til 7 modulo 160. Vi observerer at 7*23=161 = 1 (mod 160)
[tex]23\cdot7d \equiv 23\cdot 1 \ \pmod{160} \\ d \equiv 23 \pmod {160}[/tex]
gjorde dette problemet noe klarere? Hvis du heller vil løse denne som en diofantisk likning, går det også an. Spør igjen hvis det er uforståelig.
Last edited by daofeishi on 18/02-2007 22:41, edited 1 time in total.
Må nok si at dette er ganske så uforståelig. Matematikken der er egentlig langt over mitt nivå, har aldri lært om det, men har behov for løse et slikt stykke i forhold til en oppgave jeg skriver.
Jeg skal bare gå gjennom RSA-systemet med så enkelt eksempel så mulig, med lave tall. Forstår alt, helt til det kommer til det å finne denne d-verdien, men dere sier altså at det ikke går med dette stykket? Da får jeg finne nye verdier...
Jeg skal bare gå gjennom RSA-systemet med så enkelt eksempel så mulig, med lave tall. Forstår alt, helt til det kommer til det å finne denne d-verdien, men dere sier altså at det ikke går med dette stykket? Da får jeg finne nye verdier...
There are only 10 kinds of people. Those who understand binary and those who don't.
Jeg så også i oppgaven min at det sto e og[tex](p-1)\cdot (q-1)[/tex] må ikke ha felles faktor. Det går vel dårlig her når e=5, og [tex](p-1)\cdot (q-1)=80[/tex]. Må prøve med nye tall da..
Og hva er forskjell når man bruker [symbol:identisk] (identisk med) og = (lik med) ?
Edit: Og hva betyr/er gcd?
begynner forresten å skjønne det
Og hva er forskjell når man bruker [symbol:identisk] (identisk med) og = (lik med) ?
Edit: Og hva betyr/er gcd?
begynner forresten å skjønne det
There are only 10 kinds of people. Those who understand binary and those who don't.
Ok, da får vi ta det fra de begynnende definisjonene. Jeg regner med du har fått med deg at [tex]a \equiv b \pmod m[/tex] betyr at a - b er delelig på m, eller, ekvivalent: a = b + km, for et heltall k.
Hvis du ikke har lært modulær aritmetikk, kan du løse en kongruens [tex]ax = b \ \pmod m[/tex] som en diofantisk likning, altså en likning der variablene er heltall.
[tex]ax \equiv b \ \pmod m[/tex] kan skrives om til:
ax = b + my, eller ax - my = b, der x og y er heltallige variable
Vi ønsker nå å finne x (og y) som tilfredsstiller dette. Fra teorien om diofantiske likninger, har likningen ax - my = b kun løsninger dersom største felles faktor av a og m, skrevet gcd(a, m), er en faktor av b.
Dersom gcd (a, m) deler b, kan vi bruke den euklidiske algoritmen til å løse problemet. Den bygger på det faktum at dersom a = um + v, er gcd(a, m) = gcd(m, v). Se om du forstår hvordan algoritmen fungerer her. Hvis ikke, spør igjen.
Hvis du ikke har lært modulær aritmetikk, kan du løse en kongruens [tex]ax = b \ \pmod m[/tex] som en diofantisk likning, altså en likning der variablene er heltall.
[tex]ax \equiv b \ \pmod m[/tex] kan skrives om til:
ax = b + my, eller ax - my = b, der x og y er heltallige variable
Vi ønsker nå å finne x (og y) som tilfredsstiller dette. Fra teorien om diofantiske likninger, har likningen ax - my = b kun løsninger dersom største felles faktor av a og m, skrevet gcd(a, m), er en faktor av b.
Dersom gcd (a, m) deler b, kan vi bruke den euklidiske algoritmen til å løse problemet. Den bygger på det faktum at dersom a = um + v, er gcd(a, m) = gcd(m, v). Se om du forstår hvordan algoritmen fungerer her. Hvis ikke, spør igjen.
En litt enklere forklaring av algoritmen er muligens http://www.cut-the-knot.org/blue/Euclid.shtml
Takk for all hjelp. Jeg har nå kommet til et stykke som lyder slik:
[tex]8\cdot d=1(mod(19-1)\cdot (13-1))[/tex]
[tex]8\cdot d=1(mod18)\cdot (12)[/tex]
[tex]8\cdot d=1(mod216)[/tex]
Hvis du kunne regnet ut resten der, så hadde jeg vært svært taknemelig. Forståelsen kommer litt etter litt nå
[tex]8\cdot d=1(mod(19-1)\cdot (13-1))[/tex]
[tex]8\cdot d=1(mod18)\cdot (12)[/tex]
[tex]8\cdot d=1(mod216)[/tex]
Hvis du kunne regnet ut resten der, så hadde jeg vært svært taknemelig. Forståelsen kommer litt etter litt nå
There are only 10 kinds of people. Those who understand binary and those who don't.
Vel, vi har et problem her: gcd(8, 216) = 8, og 8 er ikke en faktor av 1. Kongruensen har ingen løsning.
gcd er altså største faktor som to tall har felles. gcd(3, 6) = 3, fordi det er største faktor de deler, gcd(27, 90) = 9, siden det er største faktor de deler.
gcd er altså største faktor som to tall har felles. gcd(3, 6) = 3, fordi det er største faktor de deler, gcd(27, 90) = 9, siden det er største faktor de deler.
Det er nettopp det som er problemet. Vi ønsker i dette tilfellet at 8 IKKE skal være faktor i 216. Som skrevet ovenfor, dersom [tex]ax \equiv b \ \pmod m[/tex] skal ha en løsning, må største felles faktor til a og m være en faktor av b. [tex]8x \equiv 1 \ \pmod{216}[/tex] har bare en løsning dersom gcd(8, 216) = 8 er faktor av 1.
Ohh 
Ok, nå har jeg endret det slik:
[tex]11\cdot d=1(mod(19-1)\cdot (13-1))[/tex]
[tex]11\cdot d=1(mod(18)\cdot (12))[/tex]
[tex]11\cdot d=1(mod216)[/tex]
Jeg begynner å bli litt surrete Er takknemlig for at du er litt tålmodig.
Ok, nå har jeg endret det slik:
[tex]11\cdot d=1(mod(19-1)\cdot (13-1))[/tex]
[tex]11\cdot d=1(mod(18)\cdot (12))[/tex]
[tex]11\cdot d=1(mod216)[/tex]
Jeg begynner å bli litt surrete
Er takknemlig for at du er litt tålmodig.There are only 10 kinds of people. Those who understand binary and those who don't.
[tex]11\cdot 275=3025=1(mod216)[/tex]
[tex]275\cdot11d=275\cdot 1(mod216)[/tex]
[tex]d=275(mod216)[/tex]
[tex]d=59[/tex]
Regnet jeg ut, men det ser ut som det er ganske feil... :S
[tex]275\cdot11d=275\cdot 1(mod216)[/tex]
[tex]d=275(mod216)[/tex]
[tex]d=59[/tex]
Regnet jeg ut, men det ser ut som det er ganske feil... :S
There are only 10 kinds of people. Those who understand binary and those who don't.
