Hva er utvidet Euklids algoritme og hva brukes den til i RSA?
Klikk for å snu kortet
Finner s,ts, ts,t slik at s⋅a+t⋅b=gcd(a,b)s \cdot a + t \cdot b = \gcd(a, b)s⋅a+t⋅b=gcd(a,b) (Bézout). I RSA: gitt eee og ϕ(n)\phi(n)ϕ(n) med gcd(e,ϕ(n))=1\gcd(e,\phi(n))=1gcd(e,ϕ(n))=1, gir s=e−1 mod ϕ(n)s = e^{-1} \bmod \phi(n)s=e−1modϕ(n) den private nøkkelen ddd.
Space / Enter for å snu