M8190 Algoritmy teorie čísel

Přírodovědecká fakulta
jaro 2004
Rozsah
2/0/0. 2 kr. (příf plus uk plus > 4). Ukončení: zk.
Vyučující
prof. RNDr. Radan Kučera, DSc. (přednášející)
Garance
prof. RNDr. Radan Kučera, DSc.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Kontaktní osoba: prof. RNDr. Radan Kučera, DSc.
Předpoklady
Algebra II (tj. odborná) nebo Algebra 2 (tj. učitelská)
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
Cíle předmětu
Cílem přednášky je ukázat, jak mohou výsledky teorie čísel pomoci při hledání rozkladu daného přirozeného čísla na prvočinitele, úloze, jejíž důležitost v poslední době roste kvůli aplikacím např. v teorii kódování.
Osnova
  • 1. Testy, zda je přirozené číslo N složené: Fermatův test a Carmichaelova čísla, Rabinův-Millerův test. 2. Testy, zda je přirozené číslo N prvočíslo: N-1 test Poclingtona-Lehmera, Metoda eliptických křivek. 3. 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
ftp://www.math.muni.cz/pub/math/people/Kucera/lectures/atc.ps
Další komentáře
Studijní materiály
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 jaro 2008 - akreditace, jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2012 - akreditace, jaro 2014, jaro 2016, jaro 2018, jaro 2020, podzim 2021, podzim 2023.