| Meno: | Marek
|
|---|
| Priezvisko: | Košta
|
|---|
| Názov: | Algoritmus Quadratic Sieve
|
|---|
| Vedúci: | RNDr. Jaroslav Guričan, CSc.
|
|---|
| Rok: | 2009
|
|---|
| Kľúčové slová: | Quadratic Sieve, faktorizácia celých čísel, kongruencia štvorcov, prvočíslo, konečné pole, binárna matica
|
|---|
| Abstrakt: | Práca pojednáva o algoritme na hľadanie netriviálneho deliteľa k vstupnému
celému číslu n. Algoritmus je známy pod názvom Quadratic Sieve, autorom
hlavnej myšlienky je Carl Pomerance. Popisujeme základnú ideu preosievania,
ktorá prispieva k efektivite algoritmu. Pojednávame o úspešnosti algoritmu,
nakoľko algoritmus sa dá chápať ako pravdepodobnostný a heuristický.
Podávame argumenty k zložitosti algoritmu, ktoré podporujú očakávanie subexponenciálneho
času behu. Z hľadiska realizácie algoritmu spomíname metódy
na riešenie každej fázy. V závere spomíname rôzne varianty a vylepšenia
algoritmu.
|
|---|