Matematik
Regne baglæns i Euklids algoritme
Hej, jeg sidder og skriver SRP og er for det første lidt bagud da jeg skal aflevere i om 1½ dag og for det andet er jeg gået i stå.
Jeg skal lave et eksempel på RSA kryptering og til dekrypteringen skal jeg udregne v og u ved sætningen
k*u - φ(n)*v = 1
I mit tilfælde er det 17u + 120v = 1
Først er det noget med at indsætte tallene i euklids algoritme således at jeg får
120 = 17 * 7 + 1
Og nu skal jeg så regne baglæns og det kan jeg bare ikke få til at give mening! Jeg kan ikke finde en eneste forklaring på hvorfor tallene skal stå som de gør og hvordan man deraf får u og v. Jeg er ved at gå i spåner og jeg håber virkelig der er nogen der kan hjælpe mig fordi ellers kan jeg ikke rigtig lave min matematikdel.
På forhånd tak
Freja
Svar #3
20. december 2012 af PeterValberg
Du skal jo "bare" løse ligningen:
k·u ≡ 1 (mod φ(n))
altså:
17·u ≡ 1 (mod 120)
hvilket opfyldes af: u = 113
Bruger du Euklids (udvidede) algoritme (jf #2)
så ender du med at u = -7 hvilket svarer til 113 (mod 120)
se vedhæftede
Svar #4
20. december 2012 af midget1 (Slettet)
Tusind tak for hjælpen.
Men kan du måske uddybe hvordan det kan passe at -7 svarer til 113 mod 120? Det tror jeg ikke helt jeg forstår
Svar #5
20. december 2012 af PeterValberg
Fordi 120 - 7 = 113
--------------------------------------------------------------------
Tror denne grafik skulle vise idéen bag det (det er modulo 26)
-3 svarer til 23 (i modulo 26 altså)
Skriv et svar til: Regne baglæns i Euklids algoritme
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.