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í.
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 -
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.
Poslední úprava: doc. Mgr. Pavel Příhoda, Ph.D. (29.10.2019)
Homeworks and oral exam.
Literatura -
Poslední úprava: T_KA (14.05.2013)
Cohen: A course in computational algebraic number theory, Springer-Verlag 1993.
Poslední úprava: T_KA (14.05.2013)
Cohen: A course in computational algebraic number theory, Springer-Verlag 1993.
Požadavky ke zkoušce -
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í.
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 -
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.
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.