Prosívání ve faktorizačních algoritmech
| Název práce v češtině: | Prosívání ve faktorizačních algoritmech |
|---|---|
| Název v anglickém jazyce: | Sieving in factoring algorithms |
| Klíčová slova: | faktorizace|prosívání|složitost|kvadratické síto|číselné síto |
| Klíčová slova anglicky: | factorization|sieving|complexity|quadratic sieve|number field sieve |
| Akademický rok vypsání: | 2021/2022 |
| Typ práce: | diplomová práce |
| Jazyk práce: | čeština |
| Ústav: | Katedra algebry (32-KA) |
| Vedoucí / školitel: | doc. Mgr. Pavel Příhoda, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 25.01.2022 |
| Datum zadání: | 29.04.2022 |
| Datum potvrzení stud. oddělením: | 03.01.2023 |
| Datum a čas obhajoby: | 03.02.2023 09:00 |
| Datum odevzdání elektronické podoby: | 04.01.2023 |
| Datum odevzdání tištěné podoby: | 09.01.2023 |
| Datum proběhlé obhajoby: | 03.02.2023 |
| Oponenti: | doc. RNDr. Přemysl Jedlička, Ph.D. |
| Zásady pro vypracování |
| 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. |
| Seznam odborné literatury |
| 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. |