SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
Numerical Algorithms - NMMB402
Title: Číselné algoritmy
Guaranteed by: Department of Algebra (32-KA)
Faculty: Faculty of Mathematics and Physics
Actual: from 2023
Semester: summer
E-Credits: 4
Hours per week, examination: summer s.:2/1, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: English, Czech
Teaching methods: full-time
Teaching methods: full-time
Additional information:
Guarantor: doc. Mgr. Pavel Příhoda, Ph.D.
Class: M Mgr. MMIB
M Mgr. MMIB > Povinně volitelné
Classification: Mathematics > Algebra
Incompatibility : NMIB014
Interchangeability : NMIB014
Is incompatible with: NMMX402
Is interchangeable with: NMMX402, NMIB014
Annotation -
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.
Course completion requirements -
Last update: doc. Mgr. Pavel Příhoda, Ph.D. (29.10.2019)

Homeworks and oral exam.

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

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.

Charles University | Information system of Charles University |