M8190 Algoritmy teorie čísel

Přírodovědecká fakulta
podzim 2023
Rozsah
2/2/0. 6 kr. Ukončení: zk.
Vyučující
prof. RNDr. Radan Kučera, DSc. (přednášející)
Mgr. Pavel Francírek, Ph.D. (cvičící)
Garance
prof. RNDr. Radan Kučera, DSc.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Dodavatelské pracoviště: Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Rozvrh
Út 8:00–9:50 M4,01024
  • Rozvrh seminárních/paralelních skupin:
M8190/01: Pá 10:00–11:50 M3,01023, P. Francírek
Předpoklady
M3150 Algebra II nebo M6520 Elementární teorie čísel
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 šifrování. V závěru přednášky se budeme věnovat kryptosystémům založeným na jiném principu (například na problému diskrétního logaritmu na eliptické křivce).
Výstupy z učení
Na konci tohoto kurzu bude student schopen vysvětlit základní myšlenky vyložených algoritmů.
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. Test Agarwala-Kayala-Saxeny
  • 4. 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, metoda síta v číselném tělese.
  • 5. Problém diskrétního logaritmu, některé kryptosystémy založené na tomto problému.
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
Výukové metody
Přednášky: teoretická výuka potřebného matematického základu, aplikace teorie na konstrukci konkrétních algoritmů. Cvičení: řešení konkrétních problémů s cílem porozumět základním pojmům a tvrzením, programování některých algoritmů.
Metody hodnocení
Zkouška má dvě části, písemnou a ústní. V písemné části musí studenti prokázat, že zvládli probíraný matematický základ (je nutné získat alespoň 50% bodů), a v ústní části schopnost vyložit základní myšlenky některého z probíraných algoritmů.
Informace učitele
Výuka probíhá většinou v češtině nebo dle potřeby v angličtině, příslušná terminologie je za všech okolností uváděna i s anglickými ekvivalenty. Mezi cílové dovednosti studia patří schopnost používat anglický jazyk pasivně i aktivně ve vlastní odbornosti a také v potenciálních oblastech aplikací matematiky. Hodnocení ve všech případech může probíhat v češtině i v angličtině, dle volby studenta.
Další komentáře
Studijní materiály
Předmět je vyučován jednou za dva roky.
Předmět je zařazen také v obdobích jaro 2008 - akreditace, jaro 2004, jaro 2006, jaro 2008, jaro 2010, jaro 2012, jaro 2012 - akreditace, jaro 2014, jaro 2016, jaro 2018, jaro 2020, podzim 2021.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/sci/podzim2023/M8190