Čí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. Největší B-mocné prvky. 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.
Cvičení: Odmocňování modulo prvočíso pomocí Tonelli-Shanksova algoritmu. Hledání kořenů kvadratických a obecných polynomů modulo prvočíso. Odmocňování modulo složené číslo.
(17.4.) 5.Dixonova faktorizace a CFRAC. Báze faktorizace a hladké relace. Schéma Dixonova algoritmu, výpočet lineární fáze.
(24.3.) Řetězové zlomky a sblížené zlomky, algoritmus pro výpočet řetězového rozvoje druhé odmocniny. Odvození vztahu pro generování relací a formulace algoritmu CFRAC.
Cvičení: Výpočet řetězového rozvoje druhé odmocniny. Hledání hodnoty periodického řetězového zlomku. Odhad parametrů pravé strany relace v CFRAC, popis množiny špatných řešení lineární fáze Dixonovy faktorizace.