Predmet Kriptografija in teorija kodiranja - 10. mar. 2010
predavanja: nazaj
| naprej
povzetek predavanja
| dodatna gradiva
| domače naloge
Povzetek predavanja:
- RSA sistem in faktorizacija (nadaljujemo s 4. poglavjem):
teorija števil
- binarni algoritem,
- Lehmerjev algoritem,
- Kitajski izrek o ostankih (KIO)
(za zgled uporabe KIO na kratko omenimo tokovne šifre
s pomočjo primera - glej nalogo spodaj),
- red elementa in Lagrangov izrek,
- primitiven element, Eulerjeva funkcija,
Fermatov in Eulerjev izrek
Za Prosojnice glej naslednje predavanje.
Dodatna gradiva:
Domače naloge:
- Dokaži pravilnost delovanja binarnega evklidovega algoritma
(pravilna rešitev te naloge lahko nadomesti eno celotno
domačo nalogo prvemu, ki jo odda).
- (neobvezna) Generiramo zaporedje 1 9 7 9,
naslednja števka je vsota prejšnjih štirih po modulu 10,
torej 1+9+7+9 mod 10 = 6, 9+7+9+6 mod 10 = 1, 7+9+6+1 mod 10 = 3, itd.:
1 9 7 9 6 1 3 9 9 2 3 3 7 5 8 3 3 9 3 8 3 3 7 1 4 5 7 7 3 2 9 1 5 7 2 5 9 3 9 6 ...
Gotovo veš, zakaj se v tem zaporedju kot podzaporedje ne pojavi
1 2 3 4 (v črno beli varianti je prvo zaporedje oblike NNNN,
ki se nadaljuje s P, nakar se NNNNP periodično ponavlja,
torej ne moremo najti podzaporedja oblike NPNP).
Ugotovi koliko je dolg cikel ali pa koliko je vseh različnih ciklov!
Bi znal priti do teh števil tudi brez računalnika?
Pod kakšnimi pogoji bi bila cikla lahko samo 2
(npr. če ne bi seštevali, ampak bi vzeli neko linearno kombinacijo
zadnjih štirih števk ali morda samo bitov)?