Číselné algoritmy - NMMB402

• Anglický název: Numerical Algorithms
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024 do 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/~zemlicka/24-25/vyuka.htm
• Garant: doc. Mgr. et Mgr. Jan Žemlička, Ph.D.
• Vyučující: doc. Mgr. et Mgr. Jan Žemlička, 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

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

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (22.05.2025)

angličtina

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

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (22.05.2025)

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

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.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (22.05.2025)

angličtina

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.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (22.05.2025)