Klasické i moderní faktorizační algoritmy.

Abstract

V bakalářské práci jsou popsány různě náročné faktorizační algoritmy, které jsou rozděleny do dvou kapitol, jak již název napovídá do klasických a moderních. Ke každému algoritmu je uveden alespoň jeden příklad k názornějšímu pochopení. Celková práce je rozdělena do čtyř hlavních kapitol. První kapitola je rozčleněna do pěti podkapitol. Na začátku je popsán nejdůležitější pojem této práce tedy faktorizace a co si člověk má představit pod tímto matematickým pojmem. V druhé podkapitole jsou popsány další základní matematické pojmy, které s touto problematikou souvisejí. Najde se zde vysvětlení pojmů jako je například prvočíslo, čtvercové číslo, složené číslo nebo prvočíselný rozklad. Ve třetí a čtvrté podkapitole se může čtenář seznámit s využitím faktorizace v matematice a šifrování. V poslední podkapitole jsou uvedeny pomocné algoritmy, které se využívají při samotné faktorizaci. Druhá kapitola se zabývá testováním prvočíselnosti. Tímto testováním je dobré se zabývat, aby se zbytečně faktorizace neprováděla pro čísla, pro která je to nemožné. Proto jsou v této kapitole uvedeny jednoduché a obecné algoritmy pro testování prvočíselnosti ze kterých se dozvíme, zda je zadané číslo prvočíslem nebo číslem složeným. Tedy pokud zadané číslo vyjde pomocí těchto testů jako prvočíslo, nemusí se již faktorizovat neboli nelze nalézt jeho jiné faktory nežli samotné zadané číslo. Třetí kapitola pojednává o klasických faktorizačních metodách. Jedná se o poměrně jednoduché metody, které mají snadný výpočet. Nevýhodou těchto metod je, že jsou určeny pro čísla specifického charakteru. Poslední čtvrtá kapitola uvádí moderní faktorizační metody, které jsou na rozdíl od klasickým faktorizačních metod v principu složitější, avšak ve většině případů odpadají podmínky na podobu čísla, které se má faktorizovat.