Rozdział Elementy teorii złożoności



Pobieranie 1,74 Mb.
Strona7/19
Data23.02.2018
Rozmiar1,74 Mb.
1   2   3   4   5   6   7   8   9   10   ...   19

Dowód


Niech x, yZn oraz x2y2 mod n. Z definicji 2.3 wynika, że n|x2y2, więc n|(xy)(x + y). Ale n jest liczbą pierwszą, więc n|(xy) lub n|(x + y). Stąd istnieją takie liczby całkowite k1 i 2, że: xy = k1nx + y = k2n, co oznacza, że x = y + k1n lub x = – y + k2n. Zachodzi więc xy mod n lub x– y mod n.



Twierdzenie 2.8



Jeżeli n = pq oraz p i q są liczbami pierwszymi, to każdy element w Zn może mieć co najwyżej cztery pierwiastki kwadratowe.

    1. Dowód


Niech aZ­­­n będzie resztą kwadratową elementu xZn tzn. ax2 mod n. Wtedy: ax2 mod pqax2 mod pax2 mod q. Liczby p i q są pierwsze więc na mocy twierdzenia 2.7 otrzymujemy cztery układy kongruencji:



Wobec tego, stosując chińskie twierdzenie o resztach, w Zn można znaleźć co najwyżej cztery pierwiastki kwadratowe.





              1. Generatory grup multiplikatywnych


Definicja 2.6

Niech aZn*, wtedy liczbę min{0 < k < n: ak  1 mod n} nazywamy rzędem elementu a i oznaczamy ord(a).





1   2   3   4   5   6   7   8   9   10   ...   19


©operacji.org 2017
wyślij wiadomość

    Strona główna