Algoritmi u teoriji brojeva

Osnovni podaci
Detaljne informacije
Nastava
Termini konzultacija

Šifra:	213173
ECTS:	5.0
Nositelji:

Opterećenje:

1. komponenta

Vrsta nastave Ukupno

Opis predmeta:

CILJEVI KOLEGIJA:

Studente osposobiti za:
- razumijevanje uloge teorije brojeva u suvremenoj računalnoj kriptografiji
- izvod, primjenu i implementaciju algoritama za rješavanje problema s kongruencijama, testiranje prostosti te faktorizacije velikih prirodnih brojeva

SADRŽAJ KOLEGIJA:
Osnovni algoritmi u teoriji brojeva. Algoritmi za množenje velikih prirodnih brojeva. Euklidov algoritam. Kineski teorem o ostacima. Verižni razlomci. Kvadratne kongruencije. Kvadrati i kvadratni korijeni.
Kriptografija javnog ključa. Kriptosustavi zasnovani na problemu faktorizacije. Kriptosustavi zasnovani na problemu diskretnog logaritma. Ostali kriptosustavi s javnim ključem.
Testiranje i dokazivanje prostosti. Distribucija prostih brojeva. Pseudoprosti brojevi. Miller-Rabinov, AKS i drugi testovi prostosti.
Metode faktorizacije. Pollardova ro metoda. Pollardova p-1 metoda. Metoda verižnog razlomka. Metoda kvadratnog sita.

Literatura:

Termini konzultacija:

Za termin konzultacija obratite se predmetnim nastavnicima.

rješenja

Kratka rješenja završnog ispita:

Grupa A

1. 15; 2. DA (687,355,701,1648=-1); 3. 23*53 ((3,8),(8,311),(63,24),(311,275),(419,896)); 4. 281*1021 (232107); 5. 107*113 (npr. t2=9)

Grupa B

1. 35; 2. NE (207,859,846,781,1); 3. 17*73 ((3,8),(8,245),(63,688),(245,704)); 4. 281*1019 (186585); 5. 19*673 (npr. t2=121)

12. 6. 2025.

Autor: Andrej Dujella

Popis obavijesti

Algoritmi u teoriji brojeva

Repozitorij

Anketa

Algoritmi u teoriji brojeva

1. komponenta

rješenja