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

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

Kratka rješenja:

A grupa: 1. nije spsp, 658,220,1; 2. 7*163, (3,8),(8,545),(63,139),(545,223); 3. 421*1091, 91779; 4. 103*109, t2=9,t6=81.

B grupa: 1. nije spsp, 736,155,1; 2. 31*37, (3,8),(8,527),(63,775),(527,341); 3. 421*1093, 268599; 4. 41*277, t2=92,t4=23.

C grupa: 1. nije spsp, 723,64,782,1; 2. 13*89, (3,8),(8,497),(63,999); 3. 421*1097, 172190; 4. 73*157, t4=36,t6=49.

Ako ima studenata koji ne žele prihvatiti ostvarenu ocjenu, molim da mi to jave do petka 17.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. 2022.

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