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: | 06.05.2022 |
| Date and time of defence: | 09.06.2022 09:00 |
| Date of electronic submission: | 05.05.2022 |
| Date of submission of printed version: | 09.05.2022 |
| Date of proceeded defence: | 09.06.2022 |
| 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. |