Číselné algoritmy - NMMB402

• Anglický název: Numerical Algorithms
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• Semestr: letní
• E-Kredity: 4
• Rozsah, examinace: letní s.:2/1, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: angličtina, čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Další informace: https://www.karlin.mff.cuni.cz/~prihoda/algoritmy/
• Garant: doc. Mgr. Pavel Příhoda, Ph.D.
• Třída: M Mgr. MMIB; M Mgr. MMIB > Povinně volitelné
• Kategorizace předmětu: Matematika > Algebra
• Neslučitelnost : NMIB014
• Záměnnost : NMIB014
• Je neslučitelnost pro: NMMX402
• Je záměnnost pro: NMMX402, NMIB014

Anotace

čeština

Poslední úprava: doc. Mgr. Petr Kaplický, Ph.D. (07.01.2019)

Přednáška seznamuje s pokročilými současnými metodami faktorizace natolik podrobně, aby posluchač na jejím základě mohl popsané algoritmy implementovat. Důraz je kladen na algoritmy se subexponenciální asymptotickou složitostí.

angličtina

Poslední úprava: doc. Mgr. Petr Kaplický, Ph.D. (07.01.2019)

The course is an introduction to methods for integer factorization, in particular, factoring algorithms with subexponential time complexity are presented. The student gets enough details for basic implementation of these algorithms.

Podmínky zakončení předmětu

čeština

Poslední úprava: doc. Mgr. Pavel Příhoda, Ph.D. (12.10.2017)

V průběhu semestru zadám několik domácích úkolů (asi 8). K získání zápočtu jich bude třeba vypracovat alespoň 5.

angličtina

Poslední úprava: doc. Mgr. Pavel Příhoda, Ph.D. (29.10.2019)

Homeworks and oral exam.

Literatura

čeština

Poslední úprava: T_KA (14.05.2013)

Cohen: A course in computational algebraic number theory, Springer-Verlag 1993.

Požadavky ke zkoušce

čeština

Poslední úprava: doc. Mgr. Pavel Příhoda, Ph.D. (21.02.2024)

Zkouška je ústní, sestává se ze tří otázek. Dvě z nich jsou teoretického charakteru a jedna spíše početní.

angličtina

Poslední úprava: doc. Mgr. Pavel Příhoda, Ph.D. (21.02.2024)

The exam consists of 3 questions. Two of them are on algorithms and theoretical background one question has computational character.

Sylabus

čeština

Poslední úprava: doc. Mgr. Petr Kaplický, Ph.D. (07.01.2019)

Jednoduché faktorizační algoritmy. Subexponenciální faktorizační algoritmy, metoda CFRAC a kvadratické síto. Lenstrova faktorizační metoda využívající aritmetiku eliptických křivek. Souvislost problému faktorizace a problému diskrétního logaritmu.

angličtina

Poslední úprava: doc. Mgr. Petr Kaplický, Ph.D. (07.01.2019)

Simple algorithms for factorization of integers. Subexponential algorithms, CFRAC and Quadratic Sieve. Lenstra's method based on arithmetics of elliptic curves. Connection between factorization problem for integers and the discrete logarithm problem.