Název: Prosívání ve faktorizačních algoritmech
Překlad názvu: Sieving in factoring algorithms
Autoři: Staško, Samuel ; Příhoda, Pavel (vedoucí práce) ; Jedlička, Přemysl (oponent)
Typ dokumentu: Diplomové práce
Rok: 2023
Jazyk: cze
Abstrakt: [cze] [eng]
Kvadratické a číselné síto jsou dvě tradiční faktorizační metody. Uvádíme zde princip fungování obou těchto algoritmů, přičemž se zaměřujeme především na výpočet asympto- tické složitosti. Největší důraz klademe na rozbor prosívací fáze. Hlavním cílem práce je však popis různých modifikací, odhad jejich časové složitosti a porovnání praktické vyu- žitelnosti se základními verzemi. Kromě několika známých variant prezentujeme vlastní návrhy jak kvadratického, tak číselného síta a podrobně analyzujeme jejich výhody či nevýhody. 1 The quadratic sieve and the number field sieve are two traditional factoring methods. We present here a principle of operation of both these algorithms, focusing mainly on the calculation of asymptotic complexity. The greatest emphasis is placed on the analysis of the sieving phase. However, the main goal of this work is to describe various modi- fications, estimate their time complexity and compare their practical usability with the basic versions. Apart from several well-known variants, we present our own proposals of both quadratic and number field sieve and analyze their advantages and disadvantages in detail. 1
Klíčová slova: faktorizace|prosívání|složitost|kvadratické síto|číselné síto; factorization|sieving|complexity|quadratic sieve|number field sieve

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/179579

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-521272


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce