szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 24 maja 2015, o 21:58 
Użytkownik
Avatar użytkownika

Posty: 234
Lokalizacja: Kraków
Witam. Nie umiem ostatniego kroku w odszyfrowaniu m powyższą metodą. Przedstawię wszystko na przykładzie, prosiłbym o opinie, jak dokończyć całość.

1) p = 11, q = 23, m = 243

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

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

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

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

Ad. right:

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
\vee x = 17 (253-6 \pmod {23}

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

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

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

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

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

Odpowiedzi: {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 x? Inaczej mówiąc: czy tam powinien być x, skoro za moment oznaczamy go jako zmienną w układach? Nie ma tutaj konfliktu?
Góra
Kobieta Offline
PostNapisane: 25 maja 2015, o 05:51 
Użytkownik
Avatar użytkownika

Posty: 2505
Z chińskiego twierdzenia o resztach.
Góra
Mężczyzna Offline
PostNapisane: 25 maja 2015, o 13:47 
Użytkownik
Avatar użytkownika

Posty: 234
Lokalizacja: Kraków
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:

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

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

Rozbijamy Euklidesem do uzyskania NWD:
37=2 \cdot 13 + 11
13 = 1 \cdot 11 + 1
11 = 5 \cdot 2 + 1

odwracamy operację:

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:
-17 \cdot 13 \equiv 1 mod 37
t \equiv -17 \equiv 20mod37

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

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

Pytanie: co jest "tą" odpowiedzią? :lol: 263, jak mniemam? Prawa strona z niewiadomą nie jest nam do niczego potrzebna?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Obliczenie sumy metodą zaburzania  Szymon1993  4
 Metoda czynnika sumacyjnego - zadanie 3  matiifcb  2
 Równanie rekurencyjne - metoda podstawienia  Poszukujaca  7
 Udowodnić metodą indukcji mat. - zadanie 2  Kurzu  6
 metoda anihilatorów  kamzeso  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl