rădăcini primitive

Teorema. Fie p - un prim ciudat (care este simplu, nu este egal cu 2). Apoi, prin modulele de forma p k și k 2p. unde k = 1, 2, 3, ..., există rădăcini primitive.
A se vedea dovada. Yu.S.Harin în carte, și altele. „Matematică și criptografie bazate pe calculator“

O multitudine de numere mai mici, m și relativ prime la m reprezintă o grupă multiplicativ ciclică, rădăcina primitivă este elementul constitutiv al grupului.

logaritm discret

In exemplele de mai sus tabelate logaritmilor discrete (indici) pentru numere prime între ele pentru modulul (linia galbenă cu headere) sunt antetele de coloane - celule cu un fundal verde. După cum se poate observa din exemplele, unicitatea algoritmului de determinare discretă este asigurată numai în cazul în care baza este o rădăcină primitivă. Mai mult decât atât, în scopul de a logaritmilor discreți există pentru toate numerele de mai puțin decât modulul m. trebuie să m să fie un număr prim, și anume, unicitatea reciprocă și izolarea operațiunilor de construcție în măsura și logaritmul discret se efectuează numai în câmpul Galois.

Proprietatea. Logaritmul discret al produsului este suma logaritmilor:

Proprietatea. Exponentul impus ca un factor de multiplicare pentru semnul logaritmului discret:

Dovada. Noi credem prima k = 2 și, pe baza anterioare de proprietate logaritm discret, dovedește că, pentru orice k prin inducție.