Original title:
Prosívání ve faktorizačních algoritmech
Translated title:
Sieving in factoring algorithms
Authors:
Staško, Samuel ; Příhoda, Pavel (advisor) ; Jedlička, Přemysl (referee) Document type: Master’s theses
Year:
2022
Language:
cze Abstract:
[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ži- telnosti se základními verzemi. Kromě toho prezentujeme vlastní variantu kvadratického síta, která má v některých oblastech oproti ostatním známým návrhům poměrně velké výhody. 1The 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. In addition, we present our own variant of the quadratic sieve, which has relatively large advantages in some areas compared to other known suggestions. 1
Keywords:
factorization|sieving|complexity|quadratic sieve|number field sieve; faktorizace|prosívání|složitost|kvadratické síto|číselné síto
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/173711