Anotácia

Slovenská technická univerzita v Bratislave
Fakulta elektrotechniky a informatiky
Študijný odbor: INFORMATIKA
Autor: Bc. Martin Pilka
Diplomová práca: Lineárne aspekty faktorizácie
Vedenie diplomovej práce: doc. RNDr. Ladislav Satko, PhD.
Máj 2003

Faktorizačné algoritmy založené na kongruentných štvorcoch vyžadujú nájdenie lineárne závislých množín vektorov nad GF(2) v riedkej MxN matici (lineárny krok faktorizácie). Vysvetlíme ako získať tieto lineárne závislé množiny pomocou Gaussovej eliminácie. Budeme skúmať ako sa mení hustota matice počas riešenia lineárneho kroku a túto znalosť využijeme na redukciu pamäťových nárokov. Opíšeme niekoľko modifikácií základného algoritmu a porovnáme ich výkonnosť. Budeme tiež skúmať niekoľko prístupov ako skladať semiplné relácie z parciálnych relácií (veľké prvočíselné variácie). Súčasťou práce je aj C++ implementácia faktorizačného algoritmu MPQS (Multiple Polynomial Quadratic Sieve) s distribuovanou fázou preosievania, vrátane zdrojového kódu. Navrhnuté algoritmy demonštrujeme na faktorizácii RSA čísel v rozsahu 50 až 110 cifier.