6161619782

Właściwości generatorów $ „ :

*    k    k

•    3 n ma generator <=> n - 2, 4, p lub 2p , gdzie p jest nieparzystą

liczbą pierwszą, zaś k >1

•    p jest liczbą pierwszą => f p ma generator

•    a jest generatorem ?«=>£« = { a' mod n : 0 < i < <f>(n) -1}

* . *

•    a jest generatorem f n => (b = a ' mod n jest generatorem $ n <=>

gcd(i, <!>(n)) = 1)

(z tego wynika także, że liczba generatorów $„ wynosi <P(<P(n)))

•    a jest generatorem $ n <=> a *^{(nl /p} $ 1 (mod n) dla każdej liczby pierwszej/; będącej dzielnikiem <J>(n)

Niech b ^s $ '_n.

7 x ^c p ',i : x ² = b (mod n) =5 b jest resztą kwadratową modulo n (ąuadratic residue modulo n), albo inaczej: kwadratem modulo n (sąitare modulo n).

Jeżeli takie x nie istnieje => h jest nieresztą kwadratową modulo n.

Q _n - zbiór wszystkich reszt kwadratowych modulo n

Q _n - zbiór wszystkich niereszt kwadratowych modulo n

Ponieważ 0 t %*„ , więc 0 e Q _n oraz 0 e Q _n

p - nieparzysta liczba pierwsza, a - generator    => (b jest resztą

kwadratową modulo p <=> b = a ' mod p, gdzie i jest nieujemną parzystą liczbą całkowitą).

Z powyższego wynika: \ Q \ = (p -1) /2 oraz \ Q \ = (p -1)/2