Last update: 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.
Last update: 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í.
Course completion requirements -
Last update: doc. Mgr. Pavel Příhoda, Ph.D. (29.10.2019)
Homeworks and oral exam.
Last update: 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.
Literature -
Last update: T_KA (14.05.2013)
Cohen: A course in computational algebraic number theory, Springer-Verlag 1993.
Last update: T_KA (14.05.2013)
Cohen: A course in computational algebraic number theory, Springer-Verlag 1993.
Requirements to the exam -
Last update: 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.
Last update: 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í.
Syllabus -
Last update: 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.
Last update: 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.