Numerical Algorithms - NMMX402

• Title: Číselné algoritmy
• Guaranteed by: Student Affairs Department (32-STUD)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2022
• Semester: summer
• E-Credits: 5
• 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
• Teaching methods: full-time
• Is provided by: NMMB402
• Guarantor: doc. Mgr. Pavel Příhoda, Ph.D.
• Class: M Mgr. MMIB; M Mgr. MMIB > Povinně volitelné
• Classification: Mathematics > Algebra
• Incompatibility : NMIB014, NMMB402
• Interchangeability : NMIB014, NMMB402

Annotation

English

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: Kaplický Petr, doc. Mgr., Ph.D. (07.01.2019)

Czech

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

Last update: Kaplický Petr, doc. Mgr., Ph.D. (07.01.2019)

Course completion requirements

English

For credit, a score of 25 out of 40 points is required for solving four homeworks.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (22.05.2025)

Czech

Na zápočet je třeba zisk 25 bodů z 40 možných za řešení čtyř průběžně zadávaných domácích úkolů.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (22.05.2025)

Literature

English

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

Last update: T_KA (14.05.2013)

Requirements to the exam

English

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

Last update: Příhoda Pavel, doc. Mgr., Ph.D. (21.02.2024)

Czech

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

Last update: Příhoda Pavel, doc. Mgr., Ph.D. (21.02.2024)

Syllabus

English

1. The relationship between RSA and factorization.

2. Pollard's rho-method.

3. B-powersmooth numbers, Pollard's (p-1)-method, Lenstra's ECM algorithm.

4. Roots modulo n. Tonelli-Shanks algorithm, roots modulo composite number.

5. Dixon factorization and CFRAC.

6. Quadratic sieve.

7. Discrete logarithm, Pohlig-Hellman reduction, Baby-steps, giant-steps, oracle factorization for solving GDLP.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (22.05.2025)

Czech

1. Vztah RSA a faktorizace.

2. Pollardova rho-metoda.

3. B-mocná čísla, Pollardova (p-1)-metoda, Lenstrův algoritmus ECM.

4. Odmocňování modulo n. Tonelli-Shanksův algoritmus, odmocňování modulo složené číslo.

5. Dixonova faktorizace a CFRAC.

6. Kvadratické síto.

7. Diskrétní logaritmus, Pohlig-Hellmanova redukce, Baby-steps, giant-steps, faktorizace pomocí orákula pro řešení GDLP.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (22.05.2025)