Szyfrowanie metodą Rabina - step by step

[Ceplusplusik]

Witam. Nie umiem ostatniego kroku w odszyfrowaniu \(\displaystyle{ m}\) powyższą metodą. Przedstawię wszystko na przykładzie, prosiłbym o opinie, jak dokończyć całość.

\(\displaystyle{ 1)}\) \(\displaystyle{ p = 11}\), \(\displaystyle{ q = 23}\), \(\displaystyle{ m = 243}\)

\(\displaystyle{ x^{2} = 243 (\pmod {11 \cdot 23})}\)

\(\displaystyle{ x^{2} = 243 \pmod {11} \wedge x^{2} = 243 \pmod {23}}\)

\(\displaystyle{ x^{2} = 1 \pmod {11} \wedge x^{2} = 13 \pmod {23}}\)

Ad. Left: \(\displaystyle{ x \in {1,10}}\)

Ad. right:

\(\displaystyle{ x = 13^{ \frac{23+1}{4}}\pmod {23} = 13^{6} \pmod {23} = 13^{2} \cdot 13^{2} \cdot 13^{2} \pmod {23} = 18 \cdot 8 \pmod {23} = 6}\)
\(\displaystyle{ \vee}\) \(\displaystyle{ x = 17 (253-6 \pmod {23}}\)

Stąd powstają nam 4 układy równań:

\(\displaystyle{ \begin{cases} x \equiv 1 \pmod{11} \\ x \equiv 6 \pmod{23} \end{cases}}\)

\(\displaystyle{ \begin{cases} x \equiv 1 \pmod{11} \\ x \equiv 17 \pmod{23} \end{cases}}\)

\(\displaystyle{ \begin{cases} x \equiv 10 \pmod{11} \\ x \equiv 6 \pmod{23} \end{cases}}\)

\(\displaystyle{ \begin{cases} x \equiv 10 \pmod{11} \\ x \equiv 17 \pmod{23} \end{cases}}\)

Odpowiedzi: \(\displaystyle{ {109, 98, 155, 144}}\). Pytanie: Jak je uzyskać na podstawie naszych układów równań. No i kolejna sprawa: poprawne są oznaczenia przy pierwiastkach z \(\displaystyle{ x}\)? Inaczej mówiąc: czy tam powinien być \(\displaystyle{ x}\), skoro za moment oznaczamy go jako zmienną w układach? Nie ma tutaj konfliktu?

[Medea 2]

Z chińskiego twierdzenia o resztach.

[Ceplusplusik]

W porządku, trochę poczytałem na ten temat. W pewnym momencie korzystamy z algorytmu Euklidesa, żeby ustalić wielokrotność liczby, względem której liczymy modulo. I gdy już mamy odpowiedź, bierzemy jej odwrotność, którą nie wiem, jak wyznaczamy. Dam przykład:

\(\displaystyle{ \begin{cases} x \equiv 3 \pmod{13} \\ x \equiv 4 \pmod{37} \end{cases}}\)

korzystamy z zależności: \(\displaystyle{ x \equiv 3 + 13t, x \in Z}\)
stąd:
\(\displaystyle{ 3+13t = 4 mod 37}\)
\(\displaystyle{ 13t = 1 mod 37}\)

Rozbijamy Euklidesem do uzyskania NWD:
\(\displaystyle{ 37=2 \cdot 13 + 11}\)
\(\displaystyle{ 13 = 1 \cdot 11 + 1}\)
\(\displaystyle{ 11 = 5 \cdot 2 + 1}\)

odwracamy operację:

\(\displaystyle{ 1= 11 - 5 \cdot 2 = 11 - 5 \cdot (13-11) = 6 \cdot 11 - 5 \cdot 13 = 6 \cdot (37- 2 \cdot 13) - 5 \cdot 13= 6 \cdot 37 - 17 \cdot 13}\)

Stąd wychodzi nam:
\(\displaystyle{ -17 \cdot 13 \equiv 1 mod 37}\)
\(\displaystyle{ t \equiv -17 \equiv 20mod37}\)

Pytanie: skąd \(\displaystyle{ 13^{-1} = 20}\), jak to jest wyznaczone? Następnie w zadaniu była taka odpowiedź:

\(\displaystyle{ x= 3 + 13 \cdot (20 + 37u) = 263 + 481u, u \in Z}\).

Pytanie: co jest "tą" odpowiedzią? \(\displaystyle{ 263}\), jak mniemam? Prawa strona z niewiadomą nie jest nam do niczego potrzebna?