Algoritmi u teoriji brojeva

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

Raspored: utorak 16-19 (online)
Nastava će početi u utorak 16.3.2021. u 16:15 (online). Upute će biti objavljene nekoliko dana prije prvog predavanja.
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.


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. Ostali kriptosustavi s javnim ključem. 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

  1. A. Dujella: Teorija brojeva, Školska knjiga, Zagreb, 2019.

  2. A. Dujella: Number Theory, Školska knjiga, Zagreb, 2021. (u tisku)

  3. A. Dujella, M. Maretić: Kriptografija, Element, Zagreb, 2007.

Dodatna literatura

  1. H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, 1993.

  2. R. Crandall, C. Pomerance, Prime Numbers. A Computational Perspective, Springer-Verlag, 2001.

  3. A. Das, Computational Number Theory, CRC Press, 2013.

  4. N. Koblitz: A Course in Number Theory and Cryptography, Springer-Verlag, 1994.

  5. D. R. Stinson, Cryptography. Theory and Practice, CRC Press, 2005.


Skripta je u nastajanju. Uskoro će biti dostupnja ovdje. Do tada se može pogledati ovaj tekst.


Način polaganja ispita:

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šna provjera znanja: Neće biti kolokvija. Završna provjera znanja je pismena. Zadaci će biti iz onih poglavlja koja nisu bila obuhvaćena domaćim zadaćama. Nema uvjeta za pristup završnoj provjeri. Završna provjera znanja će se održati u redovitom terminu nastave iz ovog kolegija (vjerojatno zadnji tjedan nastave). Maksimalan broj bodova koji je moguće dobiti na završnom ispitu je 40.
Bit će jedan termin za popravak završnog ispita u dogovoru za zainteresiranim studentima. Nema uvjeta za izlazak na popravak.
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.


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

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

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

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

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

Number Theory and PARI/GP

SageMathCell

MAGMA Calculator


Andrej Dujella home page