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:

Završni pismeni ispit će se održati u ponedjeljak 12.6.2023. u 17 sati (u terminu zadnjih predavanja) u predavaonici 001. Ispit se piše 2 sata. Sastojat će se od 4 zadatka od koji svaki donosi 10 bodova. Primjeri zadataka koji se mogu očekivati na završnom ispitu su zadaci iz prošlogodišnjeg ispita te treći zadatak iz prošlogodišnje četvrte zadaće.

Studenti koji su iz zadaća i aktivnosti na nastavi sakupili dovoljan broj bodova za prolaznu ocjenu nisu obavezni izaći na završni ispit ako su zadovoljni ocjenom.

Studenti koji zbog opravdanih razloga budu spriječeni pristupiti ispitu u predviđenom terminu ili ne budu zadovoljni s rezultatima završnog ispita, mogu mi se javiti oko dogovora o terminu dodatnog/popravnog kolokvija.

Na testu će pisati: "Dozvoljeno je korištenje džepnog kalkulatora, te dva papira s formulama. Kalkulatori se mogu koristiti za standardne operacije, ali nije dozvoljeno korištenje gotovih funkcija za algoritme iz teorije brojeva." 

Autor: Andrej Dujella
Popis obavijesti