Izborni kolegij na Diplomskom sveučilišnom studiju Računarstvo i matematika
0+0 3+0 Raspored: četvrtak 12-15 u 004
Završni pismeni ispit će se održati u četvrtak 13.6.2024. u 12 sati (u terminu zadnjih predavanja) u predavaonici 004.
Ispit se piše 2 sata. Sastojat će se od 4 zadatka od koji svaki donosi 10 bodova.
Zadaci će biti iz gradiva 3. i 4. poglavlja u skripti (Testiranje i dokazivanje prostosti, Metode faktorizacije).
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" 13.6.2024. moguća je u ISVU-u do 10.6.2024 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 24.6.2024. ili 8.7.2024.). Studenti koji žele da im se upiše ocjena bez polaganja završnog ispita, trebaju to javiti nastavniku nakon što prijave ispit.
U četvrtak 14.3.2024. studenti će na e-mail adresu navedenu u sustavu Merlin dobiti 1. zadaću.
Rješenja treba poslati do 28.3.2024. na duje@math.hr, po mogućnosti kao jedan pdf file.
U četvrtak 28.3.2024. studenti će na e-mail adresu navedenu u sustavu Merlin dobiti 2. zadaću.
Rješenja treba poslati do 11.4.2024. na duje@math.hr, po mogućnosti kao jedan pdf file.
U četvrtak 11.4.2024. studenti će na e-mail adresu navedenu u sustavu Merlin dobiti 3. zadaću.
Rješenja treba poslati do 9.5.2024. na duje@math.hr, po mogućnosti kao jedan pdf file.
U četvrtak 9.5.2024. studenti će na e-mail adresu navedenu u sustavu Merlin dobiti 4. zadaću.
Rješenja treba poslati do 23.5.2024. na duje@math.hr, po mogućnosti kao jedan pdf file.
Bodovi iz završnog ispita, zadaća i aktivnosti na nastavi
Ako ima studenata koji ne žele prihvatiti ostvarenu ocjenu, molim da mi to jave do petka 14.6.2024. u 14 sati.
Molim da mi se do istog roka jave i studenti koji žele imati uvid u završni ispit.
Cilj ovog kolegija je osposobiti studente za razumijevanje uloge teorije brojeva u suvremenoj računalnoj kriptografiji
te izvod, primjenu i implementaciju algoritama za rješavanje problema s kongruencijama,
testiranje prostosti i faktorizacije velikih prirodnih brojeva.
Kolegij nema formalnih kolegija prethodnika. Za uspješno praćenje kolegija,
poželjno je da je položen kolegij Teorija brojeva s preddiplomskog studija matematike.
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. LLL-algoritam.
Kriptografija javnog ključa. Kriptosustavi zasnovani na problemu faktorizacije.
Kriptosustavi zasnovani na problemu diskretnog logaritma.
Primjena LLL-algoritma u kriptoanalizi.
Testiranje i dokazivanje prostosti. Distribucija prostih brojeva. Pseudoprosti brojevi.
Miller-Rabinov, AKS i drugi testovi prostosti.
Metode faktorizacije. Pollardova ρ-metoda. Pollardova p-1 metoda.
Metoda verižnog razlomka. Metoda kvadratnog sita.
Osnovna literatura
A. Dujella, M. Maretić: Kriptografija,
Element, Zagreb, 2007.
A. Dujella: Teorija brojeva,
Školska knjiga, Zagreb, prvo izdanje 2019, drugo izdanje 2024.
A. Dujella: Number Theory,
Školska knjiga, Zagreb, 2021.
Dodatna literatura
H. Cohen: A Course in Computational Algebraic Number Theory, Springer-Verlag, 1993.
R. Crandall, C. Pomerance: Prime Numbers. A Computational Perspective, Springer-Verlag, 2001.
A. Das: Computational Number Theory, CRC Press, 2013.
N. Koblitz: A Course in Number Theory and Cryptography, Springer-Verlag, 1994.
A. J. Menezes, P. C. Oorschot, S. A. Vanstone: Handbook of Applied Cryptography, CRC Press, 1996.
D. R. Stinson: Cryptography. Theory and Practice, CRC Press, 2005.
Domaće zadaće: Bit će četiri domaće zadaće (koje će se bodovati).
Rok za predaju zadaće će biti u pravilu dva tjedna.
Maksimalan broj bodova na svakoj zadaći je 15.
Aktivnost na nastavi: Na nastavi će se zadavati zadaci za samostalno rješavanje. Studenti koji budu najuspješniji
u rješavanju tih zadataka, dobit će u pravilu za svaki zadatak po 5 bodova.
Maksimalan broj bodova koji će se moći sakupiti u ovoj komponenti je 20.
Kolokviji i završni ispit: Neće biti kolokvija. Završni ispit je pismeni.
Zadaci će biti iz onih poglavlja koja nisu bila
obuhvaćena domaćim zadaćama.
Nema uvjeta za pristup završnom ispitu.
Maksimalan broj bodova koji je moguće dobiti na završnom ispitu je 40. Zaključivanje ocjene: Zbrojit će se bodovi iz domaćih zadaća (max. 60),
aktivnosti na nastavi (max. 20) i završnog ispita (max. 40). Ocjene: ≥ 85 bodova - ocjena 5; ≥ 70 bodova - ocjena 4;
≥ 55 bodova - ocjena 3; ≥ 40 bodova - ocjena 2; < 40 bodova - ocjena 1.