Algoritmy na eliptických křivkách
Průběh přednášky
(19.2.) Přednáška: Motivace a struktura kurzu. 1. Křivky a funkční tělesa. Terminologie, notace a základní fakta o souřadnicových kruzích a funkčních tělesech afinních křivek [D, C.1 a C.3].
Cvičení: Afinní křivky v R2, nerozložitelné komponenty, použití signatury reálné kvadratické formy.
(26.2.) Přednáška: Křivky v projektivním prostoru, korektnost definice funkčního tělesa, nerozložitelné projektivní křivky.
Cvičení: Funkční tělesa přímek, konstrukce algebraického uzávěru konečného tělesa.
(5.3.) Přednáška: Pojmy hladké a singulární křivky a hladkého a singulárního polynomu. Normalizovaná diskrétní valuace na funkčních tělesech. [D, C.2-C.5]. Místa funkčního pole a odpovídající normalizované diskrétní valuaci [D, C.5],
Cvičení: Rozšíření afinní křivky do projektivního prostoru, hladkost afinní a projektivní křivky. Normalizované diskrétní valuace funkčního tělesa K(x).
(12.3.) 2. Weierstrassovy křivky. Geometrická motivace pojmu rod křivky a význam rodu křivky nad obecným tělesem. Popis struktury grupy na eliptické křivce pomocí divizorů a stupně. Weierstrassovy polynomy (WEP) a Weierstrassovy křivky. Funkční těleso eliptické křivky (a tedy i struktura grupa) lze vyjádřit pomocí Weierstrassovy křivky [D, W.1-4].
(19.3.) Přednáška: Afinní transformace WEP. Singularity WEP tvaru y2-f(x)
Weierstrassův polynom tvaru y2-f(x) je hladký, právě když je f(x) separabilní, popis hladkosti krátkého tvaru [D, W.1-4].
Cvičení: K-ekvivalence afinních WEP, výpočet krátkých WEP a zjišťování hladkosti WEP.
(26.3.) Projektivizace hladké afinní WEC je hladká projektivní WEC s jediným nevlastním bodem.
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í Weierstrassovy křivky (pro a1=a2=a3=0) [D, část A].
Cvičení: Projektivní křivka nul YZ2-X3 je singulání, ale všechny afinní body má hladké.
(2.4.) Operace na obecné hladké Weierstrassově křivce (pro a1=a2=a3=0) [D, část A].
Operace 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].
Cvičení: Sečny, tečny a grupové operace eliptické křivky nad konečným tělesem.
(9.4.) 4. Montgomeryho křivky.
Montgomeryho křivka je K-ekvivavalentní hladké Weierstrassově křivce, grupové operace na Montgomeryho křivce.
Charakterizace a konstrukce WEP K-ekvivalentního Montgomeryho polynomu [D, sekce M].
(16.4.) Montgomeryho žebřík, algoritmus počítání mocnin prvku pomocí Montgomeryho žebříku [D, Lemma M.1-2].
Cvičení: Výpočet Montgomeryho žebříku. Konstrukce hladkých Weierstrassových křivek ekvivalentních i neekvivalentních Montgomeryho křivkám.
(23.4.) 5. Edwardsovy křivky. Absolutní ireducibilita a hladkost afinních Edwardsových křivek. Body v nekonečnu projektivních Edwardsových křivek, racionální zobrazení a biracionální ekvivalence [D, část E.1].
Cvičení: Body v nekonečnu projektivní Edwardsovy křivky.
(30.4.) Biracionální ekvivalence Edwardsovy a Montgomeryho křivky. Operace na bodech afinních Edwardsových křivek [D, části E.1 a E.2].
Cvičení: Hledání biracionálně ekvivalentní Edwardsovy a Montgomeryho křivky. Výpočet opačného prvku na Edwardsově křivce. Body v nekonečnu Edwardsovy křivky a operace s nimi.
(7.5.) Operace na Edwardsově křivce ve zúplněných souřadnicích [D, E.2]. 6. Torzní podgrupa grupy eliptické křivky. Torzní prvky grupy eliptické křivky nad algebraicky uzavřeným tělesem [D, Tvrzení G.1,2].
Cvičení: Prvky grupy Edwardsovy křivky exponentu 4.
(14.5.) 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]. Idea a rekurentní výpočet polynomů, jejichž kořeny tvoří první souřadnici hladké Weirestrassovy křivky
[D, vztahy (D.1)-(D.6)]. 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í, endomorfismus \phi a počítání s Fq-racionálními prvky.
[D] - Lecture notes of Aleše Drápal