Domácí úkol z 16. března 2017
Předpokládejme, že (na nějaké dané eliptické křivce) bod P generuje cyklickou grupu řádu ./V a že je dán bod Q £ (P). Naším úkolem je najít celé číslo k splňující kP = Q. Pro jednoduchost předpokládejme, že ./V je liché prvočíslo.
Při Pollardově p-metodě jsme používali funkci / : (P) —> (P), která byla definovaná jako přičítání některého z několika konstantních bodů v závislosti na tom, ve které části definičního oboru jsme právě byli. Pro každou z následujících dvou variant vysvětlete, co by způsobilo „zjednodušení" této definice takto: zvolíme pevně libovolná celá čísla u, v, spočítáme bod
R = uP + vQ
a pro každý bod X £ (P) definujeme funkci / : (P) —> (P) tímto předpisem:
1. položíme f(X) = X + R;
2. položíme f(X) =2X + R.
Jeden efekt je jasný: ve druhé variantě musíme při každé iteraci provést dvě sčítání bodů místo jednoho, což výpočet zpomalí. Ale důležitější je promyslet funkčnost metody: připomeňme, že jsme zvolili startovní bod
P0 = a0P + b0Q
a počítali iterace Pj+i = f(Pj), pro každé j = 0,1,2,..., dokud jsme neobjevili j < i splňující Pj = Pí. Protože jsme si průběžně počítali pro každý získaný bod také jeho vyjádření lineární kombinací bodů P a Q, ze shody P j = Pí jsme odvodili nějakou informaci o hledaném k.
Jak to dopadne v našich dvou variantách definice funkce /?