Algoritmy na eliptických křivkách
Průběh přednášky
(16.2.) Motivace a struktura kurzu. 1.Křivky a funkční tělesa. Přehled terminologie, značení a základních faktů o souřadnicových okruzích a funkčních tělesech afinních křivek a jejich projektivním rozšíření [D, C.1 a C.3].
(23.2.) Pojmy hladké a singulární křivky. Normalizovaná diskrétní valuace na funkčním tělese jemu odpovídající místa, příklad popisu normalizovaných diskrétních valuací na funkčním tělese přímky K(x) [D, C.2 a C.4, C.5].
2. Eliptické křivky.
Geometrická motivace pojmu rod křivky [D, W.1].
(2.3.) Rod křivky nad obecným tělesem a ekvivalentní popis struktury grupy na eliptické křivce. Weierstrassovy polynomy (WEP) a Weierstrassovy křivky. Grupy eliptické křivky lze vyjádřit pomocí
Weierstrassovy křivky. Aplikace [D, W.2-4].
Cvičení: Afinní a projekticní ireducibilní křivky, singulární bod v nekonečnu.
(9.3.) Cvičení: Kryptografické protookoly založené na eliptických křivkách: DCDH, ElGamal, ECDSA.
3. Aritmetika Weierstrassovy křivky. Výpočet grupových operací pomocí geometrické interpretace: opačný prvek (průsečík křivky s přímkou x1 = c1), součet dvou různých prvků (průsečík křivky se sečnou), zdvojení prvku (průsečík křivky s tečnou).
Časová složitost operací zjednodušené Weierstrassovy křivky (pro a1=a2=a3=0) [D, část A].
(16.3.) Časová složitost operací grupy zavedených bez invertování v tělese s využitím homogenních souřadnic
projektivní Weierstrassovy křivky [D, část A.1].
4. Montgomeryho křivky. Afinní transformace afinní roviny a jim odpovídající substituce polynomů, K-ekvivalence polynomů a křivek.
Montgomeryho křivka je K-ekvivavalentní hladké Weierstrassově křivce, grupové operace na Montgomeryho křivce [D, začátek části M].
(23.3.) Afinní transformace afinní roviny a jim odpovídající substituce polynomů, K-ekvivalence polynomů a křivek.
Výpočet první složky výsledku grupových operací, určení druhé složky pomocí hodnoty dvou po sobě jdoucích mocnin. [D, Tvzení M.1 a Lemma M.2].
Počítání mocnin prvku pomocí Montgomeryho žebříku [D, část M.1], Weierstrassovy křivky K-ekvivalentní Montgomeryho [D, část M.2].
Cvičení: Výpočet Montgomeryho žebříku.
(30.3.) Cvičení: Konstrukce hladkých Weierstrassových křivek ekvivalentních i neekvivalentních Montgomeryho křivkám,
singularity singulárních Montgomeryho křivek.
5. Edwardsovy křivky. Ireducibilita a afinní hladkost Edwardsových křivek [D, část E.1]
(6.4.) Popis a operace afinních Edwardsových křivek, příklad nad reálnými čísly. Body v nekonečnu projektivních Edwardsových křivek, racionální zobrazení a biracionální ekvivalence [D, části E.1 a E.2].
(13.4.) Biracionální ekvivalence Edwardsovy a Montgomeryho křivky. Operace na Edwardsově křivce ve zúplněných souřadnicích [D, E.1 a E.2]. 6. Struktura grupy eliptické křivky. Torzní prvky grupy eliptické křivky nad algebraicky uzavřeným tělesem [D, Tvrzení G.1,2].
Cvičení: Výpočet opačného prvku na Edwardsově křivce. Racionální prvky řádu 2. Body v nekonečnu Edwardsovy křivky a operace s nimi.
(20.4.) Torzní část grupy eliptické křivky nad konečným tělesem, Hasseova věta, faktor a kofaktor řádu grupy eliptické křivky [D, Tvrzení G.3 a jeho důsledky].
Cvičení: Struktura grup hladké Weirestrassovy křivky nad tělesem F5 a počítání mocnin.
(27.4.) Cvičení: Nalezení zástupců všech tříd ekvivalence Montgomeryho křivek, jejich vztah k (zobecněným) Edwardsovým křivkám
7.Dělící polynomy. Idea a rekurentní výpočet polynomů, jejichž kořeny tvoří první souřadnici hladké Weirestrassovy křivky
[D, vztahy (D.1)-(D.6)].
.
(4.5.) 7.Schoofův algoritmus. Okruhy endomorfismů grupy eliptické křivky a isogenií. Vyjádření existence prvků daného řádu pomocí polynomů [D, část I.1].
Cvičení: Rozeznání přítomností involucí.
(11.5.) Formulace Schoofova algoritmu, který počítá řád grupy Fq-recionálních prvků Weirstrassovy eliptické křivky: Čínská věta o zbytcích pro malá prvočísla li, zjišťování existence prvků P řádu li splňujících podmínku
\phi^2(P)+[q mod li]P = [t mod li]\phi(P) pomocí soudělnosti polynomů [D, části I.2-3 a kapitola S].
(18.5.) Výpočet polynmů potřebných pro Schoofův algoritmus, vysvětlení procedury odhalující t dělitelné prvočíslem li
a procedury vybírající hodnotu t pomocí testování existence vlastního vektoru pro \phi chápaného jako lineární operátor na prostoru E[l] nad tělesem Fl [D, kapitola S].
8.Diskriminanty a j-invarianty. Diskriminat polynomu g je právě rezultant polynomu g a jeho derivace [D, části J.2-3].
[D] - Skripta Aleše Drápala