Číselné algoritmy - NMMB402

• Anglický název: Numerical Algorithms
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• 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í
• Další informace: https://www.karlin.mff.cuni.cz/~prihoda/algoritmy/
• Garant: doc. Mgr. et Mgr. Jan Žemlička, Ph.D.
• Vyučující: 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

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í.

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

angličtina

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.

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

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

čeština

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.

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

angličtina

Homeworks and oral exam.

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

Literatura

čeština

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

Poslední úprava: T_KA (14.05.2013)

Požadavky ke zkoušce

čeština

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

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

angličtina

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

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

Sylabus

čeština

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.

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

angličtina

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.

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