M025 Algoritmy teorie čísel

Fakulta informatiky
jaro 2000
Rozsah
2/1. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
prof. RNDr. Radan Kučera, DSc. (přednášející)
Garance
Ústavy – Přírodovědecká fakulta
Kontaktní osoba: prof. RNDr. Radan Kučera, DSc.
Předpoklady
M003 Lineární algebra a geometrie I && M004 Lineární algebra II && M008 Algebra I && M009 Algebra II
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Osnova
  • Testy, zda je přirozené číslo $N$ složené: Fermatův test a Carmichaelova čísla, Rabinův-Millerův test.
  • Testy, zda je přirozené číslo $N$ prvočíslo: $N-1$ test Poclingtona-Lehmera, metoda eliptických křivek.
  • Hledání netriviálního dělitele přirozeného čísla $N$: Lehmannova metoda, Pollardova rho metoda, Pollardova $p-1$ metoda, metoda řetězových zlomků, metoda eliptických křivek, metoda kvadratického síta.
Literatura
  • COHEN, Henri. A Course in Computational Algebraic Number Theory. Springer-Verlag, 1993, 534 s. Graduate Texts in Mathematics 138. ISBN 3-540-55640-0. info
Informace učitele
http://www.math.muni.cz/ftp/ftp/pub/math/people/Kucera/lectures/
Další komentáře
Předmět je vyučován jednou za dva roky.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích léto 1996, léto 1998, jaro 2002.