Matematyka.pl

Witam

Mam takie zadanko

Odszyfruj wiadomość ZS jeżeli nadawca użył do kodowania przekształcenia afinicznego z kluczem (9,21)

Ok, no to numeruje sobie alfabet od 0 do 25. Problem w tym, że umiem zakodować wiadomość, ale odszyfrować to już średnio.
Szukam liczby \(\displaystyle{ f(x)=9x+21\pmod{21}=26}\) tylko że zgadywanie to chyba zła metoda, wydaje mi się, że muszę wyznaczyć funkcję odwrotną, tylko nie wiem jak.

Od czego wyjść, wskazówki, gotowe rozwiązania wszystko mile widziane.
Pozdrawiam

Szyfrujesz funkcją \(\displaystyle{ y = ax + b}\) dla \(\displaystyle{ a = 9}\) i \(\displaystyle{ b = 21}\), tak? W takim razie podpowiem Ci, co masz robić, a Ty wykonasz rachunki.

Skoro \(\displaystyle{ y = ax +b}\), to \(\displaystyle{ y - b = ax}\) i \(\displaystyle{ x = (y-b)a^{-1}}\). Wszystko dzieje się w pierścieniu \(\displaystyle{ \ZZ_{26}}\). Liczba \(\displaystyle{ a^{-1}}\) jest tak wybrana, żeby po przemnożeniu przez \(\displaystyle{ 9}\) dawała jedynkę. Standardowo znajduje się ją rozszerzonym algorytmem Euklidesa.

Nie rozumiem. Mam \(\displaystyle{ x\equiv \frac{21}{-9} -y\pmod{26}}\) Jak ja mam tutaj skorzystać z rozszerzonego algorytmu euklidesa. Z czego tu liczyć nwd?

Masz równanie do rozwiązania \(\displaystyle{ -9x = -9x + 26y = 1}\)
\(\displaystyle{ 9,26}\)są względnie pierwsze i tak dostajemy równanie algorytm.