Matematik

rsa kryptering

17. december 2014 af zartorium (Slettet) - Niveau: B-niveau

hej i min sso opgaveformulering står der:

En smart metode til at opløfte til potens modulo et tal.

Er der nogen der forstår hvad der menes med det?


Brugbart svar (0)

Svar #1
17. december 2014 af Andersen11 (Slettet)

Der menes sikkert, at man skal have fat i Eulers teorem

http://en.wikipedia.org/wiki/Euler%27s_theorem


Svar #2
17. december 2014 af zartorium (Slettet)

hmm forstår ikke lige så meget hvad det jeg lige skal gøre, måske lidt hjælp?


Brugbart svar (0)

Svar #3
17. december 2014 af peter lind

Du skal for det første være klar over at du kan reducere modul n efter hver mellemregning. Hvis det ikke er for stor en potens kan du så nemt udføre det i et regneark.

Hvis det er en stor potens må man gå lidt snediger til værks. Her er en metode til det.

Det antages at du skal opløfte a til en eller anden stor potens e modulo n. Du laver så følgende rækker, hvor der underforstås at man efter hver multiplikation reducerer modulo n

Dan rækkerne (eller søjler)

a           a2           a3           a4             a5          a6          a7          a8        a9

a10        a20        a30          a40           a50         a60        a70        a80       a90

a100      a200       a300        a400         a500        a600       a700      a800      a900

a1000    a2000    a3000      a4000         a5000      a6000      a7000     a8000    a9000

Den første række danner du ved at beregne a2 = a*a   a3= a2*a    a4 = a3* a  o.s.v

Den anden række ved at beregne a20 = a10*a10    a30 = a20*a10   a40 = a30*a10  o.s.v

den tredje række a2000 = a1000    a3000 = a2000* a1000    o.sv

Hvis du nu skal beregne a6047  kan det beregnes som a6047 = a6000+40+7 = a6000*a40*a7.

I stedet for de 6046 multiplkationer du ellers skulle foretage slipper du dermed med mindre end 40.

De professionelle bruger en i princippet samme metode; men gør det mere effektivt. Det ovenstående er baseret på at potensen er skrevet i 10 tals systemet. Det er bare mere effektivt at bruge det skrevet i 2 tals systemet


Svar #4
17. december 2014 af zartorium (Slettet)

hej igen der står ikke at jeg skal bruge et stort tal det må gerne være små for at være mere sikker


Svar #5
17. december 2014 af zartorium (Slettet)

undskyld jeg bare lidt forvirret i det, men hvad gør jeg vis jeg nu tog et lille tal og viste, hvordan man opløftede det på en smart metode


Brugbart svar (0)

Svar #6
17. december 2014 af peter lind

Så skal du bare bruge at du skal reducere modulo n efter hver mellemregning

Beregn

a2 mod n  = r2

a3 mod n = a2*a modn = r2*a mod n = r3

a4 mod n = r3*a mod n = r4

o.s.v.
 


Svar #7
17. december 2014 af zartorium (Slettet)

hmmm jeg vender måske tilbage lyder meget indviklet, men jeg prøver sku. har du et link der kan forklarer det på en god måde?


Brugbart svar (0)

Svar #8
17. december 2014 af peter lind

desværre nej


Svar #9
17. december 2014 af zartorium (Slettet)

hvordan vil den som du lave slutte med? jeg er simpel lost i den opgave kan ikke forstå den


Brugbart svar (0)

Svar #10
17. december 2014 af peter lind

Den slutter når du er kommet op til den ønskede potens. Det nemmeste er at lave det i et regneark


Svar #11
17. december 2014 af zartorium (Slettet)

stadig lost beklager meget. Er det muligt og få en ommer, hvis sso er for svært og skrive og lave den i januar månede ligesom en sygeeksam?


Brugbart svar (0)

Svar #12
18. december 2014 af peter lind

Forstår ikke rigtigt dit problem. Hvis du ser bort fra det med at reducere modulo n.beregner du jo

a a2= a*a   a3 = a2*a  ...   ak+1 = ak*a  o.s.v til du er kommet op på den ønskede potens


Skriv et svar til: rsa kryptering

Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk? Klik her for at oprette en bruger.