|
Optimal strategy for factorizing smaller composite integers
Kadlček, Tomáš ; Kechlibar, Marian (referee) ; Drápal, Aleš (advisor)
Nazpv prace: Opt.inialni strategic faktorizaoe moiisicl) slozenych ciscl Autor: TomaM Kadlcok Katedra. (ust.av): Katcdra algebry Vedouci bakalafske prace: Doc. RNDr. Ales Drapal, CSc. (vnia.il vodouciho: Ales.DrapaH'iJmff.cuni.cz Abstrakt: Cilein prace bylo tostovat tfi algoritiny implementovane v kva.dratic.kom situ, ktereje vefojno k dispo/ici na wcbovych strankach katedry algobry MFF (/dc [3]). .Tojich ukolcm v ranici algorit.mu MPQS/SIQS jo rozkladat kladna cisla na cisla fadu nojvyse unsigned int (v C I I ). tj. do 32 l)itn delky vcctne. Tat.o chmost jo mitna pfi spnst.oni variant}- double large prime variation (DLPV), kdy rozkladainc oisla. ktora so tie zi'ela ro/lo/ila do faktori/arni Ita/e. AlgoriUny dostnpno pro tos- tovani byly: Pollard /), Pollard p - 1 a C'FHAC. Motoda oliptiokych kfivok neljyla dosud implemontovaiia. Porovna\;'nii inotod bylo provedeno na nekolika odli.snyeh pocitacich. Vysledkem i)lynonciin /, nioreni je lakt, '2v. ]>ro roxkladani ci.sel delsich no/ 70 cifor s pou/.itim varianty ULPV jo nojvhodnejsi nojdfivo spnstit /; - 1 algo- ritnms a pokud v ro/kladani nenspeje, pak joj dojilnit algoritnuun p nebo CFRAC. Zrychloni ooloho algoritniu x,|)nsobouo tiinto optiinalixovanym dilcini rozkladanini so pohybnje v facln 5-10%. Klic'ova slova: Pollard (>, Pollard p - \, CFH.AC!,...
|