chińskie twierdzenie o resztach

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
arti88
Użytkownik
Użytkownik
Posty: 51
Rejestracja: 18 lis 2012, o 13:58
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 22 razy
Pomógł: 1 raz

chińskie twierdzenie o resztach

Post autor: arti88 »

Witam
Mam pewien problem w zrozumieniu fragmentu dotyczącego znajdowania pierwiastków kwadratowych z liczby \(\displaystyle{ a \pmod{n}}\) przy danych czynnikach pierwszych \(\displaystyle{ p}\) oraz \(\displaystyle{ q}\).
Cytując książkę Kryptografia Stosowana, Alfred J. Menezes:
"Jeśli znane są czynniki \(\displaystyle{ p}\) i \(\displaystyle{ q}\) liczby \(\displaystyle{ n}\), to problem SQROOT (problem pierwiastków kwadratowych modulo n) może być rozwiązany efektywnie najpierw przez znalezienie pierwiastków kwadratowych z \(\displaystyle{ a \pmod{p}}\) i \(\displaystyle{ a \pmod{q}}\) a następnie powiązanie ich za pomocą chińskiego twierdzenia o resztach w celu uzyskania pierwiastków z \(\displaystyle{ a \pmod{n}}\)"


Następnie podany jest algorytm wyznaczania pierwiastków poprzez wyznaczanie pierwiastków kwadratowych \(\displaystyle{ \pm a \pmod{p}}\) i \(\displaystyle{ \pm a \pmod{q}}\). Otrzymujemy odpowiednio \(\displaystyle{ r,-r}\) oraz \(\displaystyle{ s, -s}\). Następnie zastosowany jest rozszerzony algorytm Euklidesa do znalezienia liczb całkowitych \(\displaystyle{ c}\) i \(\displaystyle{ d}\) takich,że \(\displaystyle{ cp+ dq =1}\)
Jako pierwiastki zwracane są \(\displaystyle{ \pm x \pmod{n}, \pm y \pmod{n}}\),
gdzie \(\displaystyle{ x = \left( rdq +scp\right) \pmod{n}}\) oraz \(\displaystyle{ y = \left( rdq - scp\right) \pmod{n}}\)

Chciałbym zapytać w jaki sposób rozwiązania powiązane są za pomocą chińskiego twierdzenia o resztach i na podstawie jakich twierdzeń czy wniosków stosowany jest w tym wypadku algorytm Euklidesa a także postaci rozwiązań \(\displaystyle{ x}\) oraz \(\displaystyle{ y}\). Trudno mi to odnaleźć i zrozumieć.

Proszę o pomoc w zrozumieniu tych przekształceń
Pozdrawiam
ODPOWIEDZ