Číselné síto - NMMB531

• Anglický název: Number Field Sieve
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní s.:2/0, 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: čeština
• Způsob výuky: prezenční
• Další informace: https://www.karlin.mff.cuni.cz/~prihoda/sito/
• Garant: doc. Mgr. Pavel Příhoda, Ph.D.
• Vyučující: doc. Mgr. Pavel Příhoda, Ph.D.
• Třída: M Mgr. MMIB; M Mgr. MMIB > Povinně volitelné
• Kategorizace předmětu: Matematika > Algebra
• Neslučitelnost : NMIB030
• Záměnnost : NMIB030
• Je záměnnost pro: NMIB030

Anotace

čeština

Cílem přednášky je osvětlit matematickou podstatučíselného síta a vyložit související část algebraické teorie čísel.

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

angličtina

The aim of the lecture is to expose the mathematical principles and to present the relevant parts of algebraic number theory.

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

Podmínky zakončení předmětu

čeština

Ústní zkouška v distanční formě domácí úkol.

Poslední úprava: Příhoda Pavel, doc. Mgr., Ph.D. (21.10.2020)

angličtina

Oral exam.

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

Literatura

čeština

H. Cohen: A Course in Computational Algebraic Number Theory, Springer, 2000

The Development of the Number Field Sieve, (eds. A. K. Lenstra and H. W. Lenstra, Jr.) Lecture Notes in Mathematics 1554, Springer, 1993

M. Pohst, H. Zassenhaus: Algorithmic Algebraic Number Theory, Cambridge University Press, 1989

Poslední úprava: T_KA (14.05.2013)

Požadavky ke zkoušce

čeština

Zkouška je ústní, obsahuje 3 otázky. První je stručný popis celého algoritmu číselného síta s detailnějším popisem některé konkrétní fáze. Druhá otázka je na probranou teorii z přednášky. Poslední otázka je početního charakteru.

Distanční zkoušení bude formou domácího úkolu, konkrétní implementace kroku číselného síta, kde bude třeba zpravidla vymyslet jak

matematickou ideu z přednášky transformovat do návrhu konkrétního algoritmu.

Poslední úprava: Příhoda Pavel, doc. Mgr., Ph.D. (21.10.2020)

angličtina

Students have to pass final oral exam. The exam consists of three questions. The first one is a brief outline of the NFS,

the second one is on the theoretical background and the third one has computational character.

In distance form the students have to do a homework which is an implemenation of a part of NFS presented during the

lecture without technical details.

Poslední úprava: Příhoda Pavel, doc. Mgr., Ph.D. (21.10.2020)

Sylabus

čeština

Cílem přednášky je osvětlit matematickou podstatu speciálního a obecného číselného síta používaného při faktorizaci velkých čísel a při hledání diskrétních logaritmů. Pozornost, byť v menší míře, bude věnována též implementačním aspektům.

Poslední úprava: Příhoda Pavel, doc. Mgr., Ph.D. (27.05.2025)

angličtina

The aim of the lecture is to expose the mathematical principles of the quadratic sieve and of the number field sieve which are used when factorizing large integers and when solving the discrete logarithm problem. To this purpose the relevant parts of algebraic number theory will be presented. An attention, while in a limited scale, will be paid to implementation aspects as well.

Poslední úprava: T_KA (14.05.2013)

Vstupní požadavky

čeština

Předpokládá se znalost základů komutativní algebry v rozsahu předmětu Komutativní okruhy, základy algebraické teorie čísel zhruba v rozsahu 1. kapitoly skript přednášky Základní algebraická teorie čísel. Klíčové myšlenky jednoduchých faktorizačních založených na Fermatově faktorizaci budou stručně zopakovány v průběhu přednášky.

Poslední úprava: Příhoda Pavel, doc. Mgr., Ph.D. (27.05.2025)

angličtina

Basic knowledge of commutative algebra at the level of the corresponding undergraduate course, basics of algebraic number theory in the range of the first chapter of the lecture notes for the course Basic algebraic number theory. Also the knowledge of factoring algorithms based on Fermat's factorization could be helpful but everything necessary is briefly recalled during the course.

Poslední úprava: Příhoda Pavel, doc. Mgr., Ph.D. (27.05.2025)