Algoritmi u teoriji brojeva

Osnovni podaci
Detaljne informacije
Nastava
Termini konzultacija

Šifra:	213173
ECTS:	5.0
Nositelji:	prof. dr. sc. Andrej Dujella

Opterećenje:

1. komponenta

Vrsta nastave Ukupno

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:

prof. dr. sc. Andrej Dujella:
ponedjeljak 16-18
Lokacija: 301

završni ispit

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.

4. 6. 2024.

Autor: Andrej Dujella

Popis obavijesti

Algoritmi u teoriji brojeva

Repozitorij

Anketa

Algoritmi u teoriji brojeva

1. komponenta

završni ispit

PRIRODOSLOVNO-MATEMATIČKI FAKULTET