6161619783

Przykład:

a = 3 jest generatorem £ *7-

a°	a^1	a^2		a^4	ar
1	3	2	6	4	5

Q_p ={1,2,4}    Q_p ={3,5,6}

Sprawdzenie:

1 ² =1 (mod 7)    2 ² =4 (mod 7)    3² =2 (mod 7)

4 ² =2 (mod 7)    5 ² =4 (mod 7)    6 ² = 1 (mod 7)

(n = pq) a (p i q - liczby pierwszej => (b ^E $ _n jest resztą kwadratową modulo n <=> (b e Q _p ) a (b e Q q))

Z powyższego wynika: \Q _n\ = \Q _pV \Q _q\ = (p - l)(q -1) / 4 oraz \Q _n\ = 3 (p- l)(q -1) / 4

Niechb e Q_n .

x e %'_n spełnia zależność x ² = b (mod n) => x jest pierwiastkiem

kwadratowym z b modulo n (square root).

Liczba pierwiastków kwadratowych:

•    (p jest nieparzystą liczbą pierwszą) a (b e Q _p ) => b ma dokładnie dwa pierwiastki kwadratowe modulo p

•    Niech n = p, ^eI p₂ ^e2 ... Pk ^ek, gdzie p_t są różnymi nieparzystymi liczbami pierwszymi, zaś e, > 1 . Wtedy reszta kwadratowa b E Q _n ma dokładnie 2^k różnych pierwiastków kwadratowych modulo n.