Číselné algoritmy
Průběh přednášky
(20.2.) Cíle kurzu: popis standardních algoritmů na faktorizaci čísel spolu se souvisejícími problémy.
1. Vztah RSA a faktorizace. Faktorizační algoritmus s orákulem na hledáni soukromého klíče RSA.
(27.2.) 2. Pollardova rho-metoda. Odhady složitosti zkusmého dělení. Perioda a preperioda posloupnosti vytvořených funkcí, Floydova metoda hledani cyklu. Pollardova rho-metoda a Pollardův-Floydův algoritmus.
Cvičení: Perioda a preperioda lineárních polynomiálních funkcí na Zp.
(6.3.) 3. B-mocná čísla. Nástin Pollarovy (p-1)-metody.
Cvičení: Grupa affiních zobrazení na přímce, perioda a preperioda funkce dané x2.
(13.3.) Časová složitost a pravděpodobnost úspěchu Pollardovy (p-1)-metody, dvoufázová verze.
Cvičení: Výpočet B-mocných prvků pro konkrétní malá B, určení jejich počtu a asymptotického chování. Fermatova čísla, důkaz prvočíselnost F4 a složenosti F5.
(20.3.) Kongruence na okruzích ZN[x] a nástin (p+1)-metody.
Parciální operace sčítání na množině Ea,b(ZN) pro obecné N a pro provočíslo.
(27.3.) Hledání kolize při výpočtu operace na Ea,b(ZN), Lenstrův algoritmus ECM.
Cvičení: Vztah operace na na množině Ea,b(ZN) a grupové operace na
na množině Ea,b(Zp) pro prvočíselný dělitel p čísla N. Odmocňování modulo prvočísla p=4k+3 a p=8k+5.
(3.4.) Algoritmus paralelní inverze pro ECM. 4. Odmocňování modulo n. Pohlig-Hellmanova redukce a Tonelli-Shanksův algoritmus pro počítání druhé odmocniny modulo liché prvočíslo.
(10.4.) Hledání kořenů polynomů modulo liché prvočíslo, odmocňování modulo mocnina prvočísla pomocí Henselova zdvihání. Útok na RSA pomocí deterministického algoritmu na hledání druhé odmocniny modulo součin dvou různých prvočísel.
(17.4.) 5.Dixonova faktorizace a CFRAC. Báze faktorizace a hladké relace. Schéma Dixonova algoritmu, výpočet lineární fáze.