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:

Obavijesti

Studenti koji žele izaći na predrok, a zbog bilo kojeg razloga nisu u mogućnosti na vrijeme prijaviti ispit, mogu izaći na predrok. Dovoljno je da mi pošalju e-mail poruku. Ocjena će im biti upisana nakon što prijave ispit na nekom od idućih rokova. 

Autor: Andrej Dujella

Završni pismeni ispit će se održati u četvrtak 12.6.2025. u 12 sati (u terminu zadnjih predavanja) u predavaonici 004.
Ispit se piše 2 sata. Sastojat će se od 5 zadatka od koji svaki donosi 10 bodova. Primjeri zadataka koji se mogu očekivati na završnom ispitu mogu se naći dnu web stranice kolegija. 
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."
Prijava ispita za "predrok" 12.6.2025. moguća je u ISVU-u do 9.6.2025. u 12:00. 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, no također moraju prijaviti ispit kako bi im se mogla upisati ocjena (na predroku ili na nekom od narednih rokova 18.6.2025. ili 2.7.2025.). Studenti koji žele da im se upiše ocjena bez polaganja završnog ispita, trebaju to javiti nastavniku nakon što prijave ispit.

Autor: Andrej Dujella

Za kolegij Algoritmi u teoriji brojeva (213173) otvoren je predrok 12.6.2025., prijave su moguće do 9.6.2025. u 12 sati, a odjave do 11.6.2025. u 12 sati.

Autor: Andrej Dujella

Bodovi iz sve četiri zadaće i aktivnosti na nastavi nalaze se na https://web.math.pmf.unizg.hr/~duje/algortb/rezultati/Algoritmi_u_teoriji_brojeva-2025.pdf

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

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

Autor: Andrej Dujella