Szyfr RSA

[Scoler]

\(\displaystyle{ p=7}\), \(\displaystyle{ q=13}\)

Wyznaczyłem \(\displaystyle{ e,n, φ(n)}\).
\(\displaystyle{ e=5}\)
\(\displaystyle{ n=91}\)
\(\displaystyle{ φ(n)=72}\)

Teraz muszę wyznaczyć \(\displaystyle{ d}\). Z wikipedii się dowiedziałem, że \(\displaystyle{ d \equiv e ^{-1} (mod φ(n))}\)
Można to zapisać prościej: \(\displaystyle{ d⋅e \equiv 1 (mod φ(n))}\)

Podstawiam: \(\displaystyle{ 5d \equiv 1(mod 72)}\) i nie rozumiem tego zapisu.
PROSZĘ O POMOC.

[Premislav]

Ten zapis oznacza, że istnieje taka liczba całkowita \(\displaystyle{ k}\), iż \(\displaystyle{ 5d=72k+1}\).
To, co nazywasz \(\displaystyle{ d}\) wyznacza się zazwyczaj z rozszerzonego algorytmu Euklidesa:
\(\displaystyle{ 72=14\cdot 5+2\\5=2\cdot 2+1\\ 1=5-2\cdot 2=5-2\cdot (72-14\cdot 5)=29\cdot 5-2\cdot 72}\)
czyli \(\displaystyle{ 29\cdot 5=2\cdot 72+1}\), a więc w \(\displaystyle{ \ZZ_{72}}\) mamy
\(\displaystyle{ 5^{-1}=29}\).

[Scoler]

Czyli mam znaleźć takie \(\displaystyle{ d}\), że po pomnożeniu przez \(\displaystyle{ 5}\) i podzieleniu przez \(\displaystyle{ 72}\) reszta z tego dzielenia wyjdzie \(\displaystyle{ 1}\)?

[Premislav]

No tak, masz znaleźć takie \(\displaystyle{ d}\), że reszta z dzielenia iloczynu \(\displaystyle{ 5d}\) przez \(\displaystyle{ 72}\) wyniesie \(\displaystyle{ 1}\). W linku masz z grubsza wyjaśnione postępowanie, bo może na takim krótkim przykładzie z dwoma krokami to niewiele widać.

[Scoler]

Wydawało mi się, że w miarę ogarniam rozszerzony algorytm Euklidesa, ale mam problem z \(\displaystyle{ 7d=120k+1}\). Mógłbyś pomóc?

[Premislav]

Tutaj to się szybko kończy:
\(\displaystyle{ 120=17\cdot 7+1}\)
Zatem \(\displaystyle{ 1=(-1)\cdot 120+7\cdot(-17)}\) i teraz warto zauważyć, że będzie też prawdziwa równość \(\displaystyle{ 1=(-1+7t)\cdot 120+7\cdot(-7+120t)}\) dla dowolnego \(\displaystyle{ t}\) całkowitego. Jak chcemy mieć element \(\displaystyle{ d}\) należący do \(\displaystyle{ \ZZ_{120}}\), który spełnia \(\displaystyle{ 7d\equiv 1\pmod{120}}\), to dobieramy takie \(\displaystyle{ t\in \ZZ}\), by liczba \(\displaystyle{ -7+120t}\) należała do \(\displaystyle{ \ZZ_{120}}\), tj. biorąc \(\displaystyle{ t=1}\) dostaniemy to, czego byśmy sobie życzyli i \(\displaystyle{ d=-17+120=103}\).

Ogólnie jak masz taką liczbę \(\displaystyle{ d\in \ZZ}\), że
\(\displaystyle{ ad \equiv c\pmod{b}}\) (tutaj znaleźliśmy \(\displaystyle{ d=-17}\), zaś \(\displaystyle{ a=7, c=1, b=120}\)), to reszta z dzielenia liczby \(\displaystyle{ d}\) przez \(\displaystyle{ b}\) też spełnia tę zależność, gdyż reszta ta różni się o wielokrotność \(\displaystyle{ b}\) (tutaj wielokrotność \(\displaystyle{ 120}\)) od \(\displaystyle{ d}\).
I taka reszta z dzielenia należy już do \(\displaystyle{ \ZZ_{120}}\). Mamy \(\displaystyle{ -17=-1\cdot 120+103}\), stąd ta reszta to \(\displaystyle{ 103}\) i to jest nasze \(\displaystyle{ 7^{-1}}\) w \(\displaystyle{ \ZZ_{120}}\).