Anotácia

Slovenská technická univerzita v Bratislave
Fakulta elektrotechniky a informatiky
Študijný odbor: INFORMATIKA
Autor: Bc. Marek Martinkovič
Diplomová práca: Faktorizácia veľkých čísel
Vedenie diplomovej práce: prof. RNDr. Otokar Grošek, CSc.
december 2001

Táto práca sa zaoberá návrhom a implementáciou knižnice, ktorá obsahuje funkcie pre prácu s veľkými číslami a implementáciou faktorizačných algoritmov. Na základe známych štruktúr veľkých čísel používaných v existujúcich projektoch je zvolená vhodná reprezentácia veľkého čísla. Navrhnutá štruktúra je implementovaná v programovacom prostredí jazyka C++. Knižnica ďalej pozostáva zo základných aritmetických operácií, ktoré pracujú nad implementovanou štruktúrou veľkého čísla. Veľké číslo je implementované ako trieda a aritmetické operácie sú jej metódami. Faktorizačné metódy sú implementované pomocou metód veľkého čísla. Projekt sa zaoberá tromi faktorizačnými metódami. Sú nimi ECM metóda, založená na eliptických krivkách, (P-1) metóda založená na Fermatovej teoréme a metóda kvadratického sita. Metódy sú popísané a implementované. Implementované metódy boli použité na faktorizáciu čísel, ktorých rozklad na faktory je známy. Týmto spôsobom bola overená správnosť implementácie. Charakter metódy kvadratického sita umožňuje riešiť výpočet paralelne. V práci je navrhnuté distribuované riešenie v prostredí internetu. Implementácia beží v rôznych módoch činnosti, ktoré poskytujú používateľovi informácie o stave výpočtu.