Rozdział Elementy teorii złożoności



Pobieranie 1,74 Mb.
Strona8/19
Data23.02.2018
Rozmiar1,74 Mb.
1   ...   4   5   6   7   8   9   10   11   ...   19

Twierdzenie 2.9


Przypuśćmy, że aZn*, ord(a) = k oraz am  1 mod n. Wtedy k|m.

    1. Dowód


Załóżmy przeciwnie, że istnieją liczby r, sN takie, że m = sk + r oraz r < k. Wtedy 1  amask+r  (ak)sar mod n, ale na mocy definicji 2.6 ak  1 mod n. Stąd wynika, że ar  1 mod n, co jest sprzeczne z założeniem (r < k i k jest najmniejszą liczbą spełniającą ak  1 mod n).



Definicja 2.7



Jeżeli aZn* i ord(a) = n – 1, to element a nazywamy generatorem Zn*.

    1. Twierdzenie 2.10


(d) = n dla dowolnego n > 0.


1   ...   4   5   6   7   8   9   10   11   ...   19


©operacji.org 2017
wyślij wiadomość

    Strona główna