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:
srijeda 14-16
Lokacija: 301

završni ispit

Završni pismeni ispit će se održati u utorak 15.6.2021. u 16 sati (u terminu zadnjih predavanja). Ispit će se održati online. Studenti će se na početku ispita trebati spojiti preko zooma u 16:00 (link je isti kao za predavanja https://zoom.us/j/94784020820?pwd=eFZPRXhwZjdjdEo5WTY5aDdxMjdJdz09) zbog evidencije i uputa na početku pisanja ispita.

Studenti će svoje zadatke za završni pismeni ispit moći naći na poveznici
https://web.math.pmf.unizg.hr/~duje/algortb/zavrsni2021/
u 16 sati. Zadaci se nalaze u pdf fileu nazvanom po prezimenu studenta.

Ispit se piše 2 sata. Sastojat će se od 4 zadatka od koji svaki donosi 10 bodova. Primjer zadataka koji se mogu očekivati na završnom ispitu može se vidjeti ovdje (rješenja zadataka su: 1. NE; 259, 781, 1; 2. n=31*79, x1=3, y1=8, x2=8, y2=1519, x3=63, y3=2418, x4=1519, y4=775; 3. n=211*3001, 37559; 4. n=97*263; 1, -230, 89, -158, 145, -115, 61, -227, 50, -167, 145).

Po završetku ispita, studenti trebaju poslati svoja rješenja e-mailom na duje@math.hr, konačna rješenja zadataka napišite u tekstu poruke, a postupak rješavanja pošaljite u prilogu poruke uslikan ili skeniran.

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.

Studenti koji bi zbog opravdanih razloga bili spriječeni pristupiti ispitu u predviđenom terminu, mogu mi se javiti oko dogovora o dodatnom terminu, a ovisno o okolnostima i o modifikaciji završnog dijela polaganja ispita.

14. 6. 2021.

Autor: Andrej Dujella

Popis obavijesti

Algoritmi u teoriji brojeva

Repozitorij

Anketa

Algoritmi u teoriji brojeva

1. komponenta

završni ispit

PRIRODOSLOVNO-MATEMATIČKI FAKULTET