Prosívání ve faktorizačních algoritmech
Thesis title in Czech: | Prosívání ve faktorizačních algoritmech |
---|---|
Thesis title in English: | Sieving in factoring algorithms |
Key words: | faktorizace|prosívání|složitost|kvadratické síto|číselné síto |
English key words: | factorization|sieving|complexity|quadratic sieve|number field sieve |
Academic year of topic announcement: | 2021/2022 |
Thesis type: | diploma thesis |
Thesis language: | čeština |
Department: | Department of Algebra (32-KA) |
Supervisor: | doc. Mgr. Pavel Příhoda, Ph.D. |
Author: | hidden - assigned and confirmed by the Study Dept. |
Date of registration: | 25.01.2022 |
Date of assignment: | 29.04.2022 |
Confirmed by Study dept. on: | 03.01.2023 |
Date and time of defence: | 03.02.2023 09:00 |
Date of electronic submission: | 04.01.2023 |
Date of submission of printed version: | 09.01.2023 |
Date of proceeded defence: | 03.02.2023 |
Opponents: | doc. RNDr. Přemysl Jedlička, Ph.D. |
Guidelines |
Budou studovány algoritmy pro prosívání v kvadratickém a číselném sítu a jejich heuristické odhady. Pro navrženou modifikaci kvadratického nebo číselného síta by měl student navrhnout heuristický odhad složitosti algoritmu a z něj vycházející konkrétní volbu parametrů v algoritmu. Na menších vstupech pak vyzkoušet, zda zda algoritmus s lepším heuristickým odhadem dává také lepší výsledky.
V rámci práce je též možné provést rešerši článků, které se zabývají optimalizací nebo paralelizací algoritmu číselného síta. |
References |
J. P. Buhler, H. W. Lenstra, C. Pomerance: Factoring integers with number field sieve, in:
A. K. Lenstra, H. W. Lenstra: The developement of the number field sieve, LNM, Springer 1993. D. Coppersmith: Modification to the Number Field Sieve, J. Cryptology 6 (1993), 169 - 180 R. Crandall, C. Pomerance: Prime Numbers - A Computational Perspective, Springer 2005. |