Čí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 Pollarovy (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 Pollarovy (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 prvočíslo.