Algoritmi u teoriji brojeva

Izborni kolegij na Diplomskom sveučilišnom studiju Računarstvo i matematika 0+0 3+0

Raspored: srijeda 15-18 u 004

U srijedu 11.3.2026. studenti će na e-mail adresu navedenu u sustavu Merlin dobiti 1. zadaću.
Rješenja treba poslati do 25.3.2026. na duje@math.hr, po mogućnosti kao jedan pdf file.

U srijedu 25.3.2026. studenti će na e-mail adresu navedenu u sustavu Merlin dobiti 2. zadaću.
Rješenja treba poslati do 8.4.2026. na duje@math.hr, po mogućnosti kao jedan pdf file.

U srijedu 8.4.2026. studenti će na e-mail adresu navedenu u sustavu Merlin dobiti 3. zadaću.
Rješenja treba poslati do 6.5.2026. na duje@math.hr, po mogućnosti kao jedan pdf file.

U srijedu 6.5.2026. studenti će na e-mail adresu navedenu u sustavu Merlin dobiti 4. zadaću.
Rješenja treba poslati do 20.5.2026. na duje@math.hr, po mogućnosti kao jedan pdf file.

Bodovi iz zadaća i aktivnosti na nastavi

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.

Snimke predavanja iz akad. god. 2020/2021

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. 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.

Algoritmi u teoriji brojeva, skripta
(u pdf formatu)

Primjeri u PARI/GP

Način polaganja ispita:

Domaće zadaće: Tijekom semestra zadaju se projektni zadaci koji prate do tada obrađeno gradivo kolegija. Bit će ukupno 10 zadataka podijeljenih u 3-4 seta zadataka. Maksimalan ukupni broj bodova koji moguće dobiti iz projektnih zadataka je 50.
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 dodatnih 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. Nema uvjeta za pristup završnom ispitu. Pisani ispit sastoji od pitanja iz onih poglavlja koja nisu bila obuhvaćena projektnim zadacima. Pisani ispit se piše u za to predviđenim ispitnim terminima. U dogovoru sa studentima, moguće je organizirati predrok u zadnjem tjednu nastave. Maksimalan broj bodova koji je moguće dobiti na pisanom ispitu je 50.
Zaključivanje ocjene: Zbrojit će se bodovi iz projektnih zadataka (max. 50), završnog ispita (max. 50) i aktivnosti na nastavi (max. 20 dodatnih bodova).
Ocjene: ≥ 85 bodova - ocjena 5; ≥ 70 bodova - ocjena 4; ≥ 55 bodova - ocjena 3; ≥ 40 bodova - ocjena 2; < 40 bodova - ocjena 1.

Obavijesti na web forumu kolegija "Kriptografija"

Kriptografija i sigurnost mreža - kolegij na diplomskom studiju računarstva

Eliptičke krivulje u kriptografiji - kolegij na diplomskom studiju računarstva i teorijske matematike

Teorija brojeva - kolegij na preddiplomskom studiju

Elementarna teorija brojeva - kolegij na preddiplomskom studiju

Diofantske aproksimacije i primjene - poslijediplomski kolegij (2011/2012)

Algoritmi za eliptičke krivulje - poslijediplomski kolegij (2008/2009)

Teorija brojeva u kriptografiji - poslijediplomski kolegij (2003/2004)

Studentski seminar - Eliptičke krivulje i njihova primjena u kriptografiji (2002/2003)

Popis dostupne literature iz teorije brojeva

PARI/GP home page

PARI/GP in browser