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

rezultati završnog ispita

Ispravljen je završni ispit.

Rezultati i ocjene se mogu vidjeti na

https://web.math.pmf.unizg.hr/~duje/algortb/rezultati/Algoritmi_u_teoriji_brojeva-2023.pdf

Kratka rješenja:

A grupa: 1. 21; 2. nije spsp, 512,147,1; 3. 7*167, (3,8),(8,461),(63,531),(461,755); 4. 421*1103, 204607.

B grupa: 1. 21; 2. nije spsp, 1737,1520,1; 3. 29*41, (3,8),(8,401),(63,372),(401,227); 4. 421*1109, 438683.

Ako ima studenata koji ne žele prihvatiti ostvarenu ocjenu, molim da mi to jave do srijede 14.6.2022. u 12 sati.
Molim da mi se do istog roka jave i studenti koji žele izaći na popravni završni ispit, te studenti koji žele imati uvid u završni ispit.

13. 6. 2023.

Autor: Andrej Dujella

Popis obavijesti

Algoritmi u teoriji brojeva

Repozitorij

Anketa

Algoritmi u teoriji brojeva

1. komponenta

rezultati završnog ispita

PRIRODOSLOVNO-MATEMATIČKI FAKULTET