Algoritmi u teoriji brojeva

Repozitorij

Repozitorij je prazan

Anketa

Na ovoj stranici trenutno nije odabrana niti jedna anketa!

Algoritmi u teoriji brojeva

Šifra: 213173
ECTS: 5.0
Nositelji: prof. dr. sc. Andrej Dujella
Opterećenje:

1. komponenta

Vrsta nastaveUkupno
Predavanja 45
* Opterećenje je izraženo u školskim satima (1 školski sat = 45 minuta)
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:
1. semestar Ne predaje se
Izborni predmet 1, 2 - Redovni Studij - Računarstvo i matematika

2. semestar
Izborni predmet 1, 2 - Redovni Studij - Računarstvo i matematika

3. semestar Ne predaje se
Izborni predmet 3, 4, 5, 6 - Redovni Studij - Računarstvo i matematika

4. semestar
Izborni predmet 3, 4, 5, 6 - Redovni Studij - Računarstvo i matematika
Termini konzultacija:

Bodovi iz prve tri zadaće i aktivnosti na nastavi nalaze se na https://web.math.pmf.unizg.hr/~duje/algortb/rezultati/Algoritmi_u_teoriji_brojeva-2023.pdf

Molim vas da mi javite ako uočite neku grešku. 

Završni ispit će se pisati 12.6.2023. u 17 sati (u terminu zadnjih predavanja).  

Autor: Andrej Dujella
Popis obavijesti