Algoritamska
teorija brojeva
| |
Smjer: |
Teorijska kompjuterska nauka |
| |
Semestar: |
IX |
| |
Tip kursa: |
Obavezni |
| |
Fond sati: |
3+2+0 |
| |
Broj
ECTS kredita: |
10 |
Nastavni program:
- Teorija brojeva i
kompleksnost.
-
Najveći zajednički djelilac; Euklidov
algoritam za NZD; Analiza najkompleksnijih slučajeva;
- Binarni NZD algoritam;
Neprekidni razlomci;
-
Modularni račun; Kineski teorem o ostacima;
Kvadratni ostaci; Računanje Legendreovog i Jakobievog simbola;
- Rješavanje jednačina
nad konačnim poljima; Korijeni; Henselova lema;
- Algoritmi za
određivanje prostih brojeva; Testovi prostosti za brojeve specijalnog oblika;
Pseudoprosti i Carmichaelovi brojevi; Vjerovatnosni testovi prostosti;
Testovi prostosti pomoću sita; Konstrukcija “slučajnih” prostih brojeva;
-
Algoritmi za faktorizaciju brojeva;
Literatura:
-
Eric Bach and Jeffrey Shallit:
Algorithmic Number Theory, Volume I: Efficient Algorithms,
Press, August 1996
- Yan, Song Y.:
Number Theory for Computing, 2nd ed., 2002, Springer Verlag
-
H. Cohen: A Course in Computational
Number Theory (Corrected Third Printing), Graduate Texts in Mathematics
138, Springer 1996