Algoritmy na eliptických křivkách
Průběh přednášky
(20.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 [D, C.1 a C.3].
Cvičení: Afinní křivky v R2, ireducibilní komponenty, využití signatury reálné kvadratické formy.
(27.2.) Křivky v projektivním prostoru. Pojmy hladké a singulární křivky. Normalizovaná diskrétní valuace na funkčním tělese [D, C.2-C.5].
Cvičení: Rozšíření křivky do projektivního posotoru. Hladké a singulární křivky křivky
(5.3.) Cvičení: Normalizované diskrétní valuace na funkčním tělese přímky K(x), valuace v, korektnost definice funkční tělesa projektivní křivky.
Místa funčního tělesa a odpovídající normalizovaná diskrétní valuace [D, C.5], ekvivalentní popis struktury grupy na eliptické křivce [D, W.3].
(12.3.) 2. Weierstrassovy křivky. Geometrická motivace pojmu rod křivky a rod křivky nad obecným tělesem. Weierstrassovy polynomy (WEP) a Weierstrassovy křivky. WFunkční těleso (a proto i grupu) eliptické křivky lze vyjádřit pomocí Weierstrassovy křivky. Weierstrassův polynom tvaru y2-f(x) je hladký, právě když je f(x) separabilní [D, W.1-4].
Cvičení: Afinní a projekticní ireducibilní křivky, singulární bod v nekonečnu. Prvky prvočíselného řádu v komutativní grupě.
(19.3.) 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].
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].
Cvičení: Sečny, tečny a grupové operace eliptické křivky y2- x3+3x nad tělesem Z7.
(26.3.)
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, Afinní transformace afinní roviny a jim odpovídající substituce polynomů, K-ekvivalence polynomů a křivek. [D, sekce M]. Montgomeryho žebřík [D, Lemma M.2].
Cvičení: Výpočet Montgomeryho žebříku.
(2.4.)
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].
Algoritmus počítání mocnin prvku pomocí Montgomeryho žebříku [D, část M.1]. Weierstrassovy křivky K-ekvivalentní Montgomeryho [D, část M.2].
(9.4.) Cvičení: Konstrukce hladkých Weierstrassových křivek ekvivalentních i neekvivalentních Montgomeryho křivkám,
5. Edwardsovy křivky. Absolutní ireducibilita a hladkost afinních Edwardsových křivek [D, část E.1].
(16.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. Biracionální ekvivalence Edwardsovy a Montgomeryho křivky. [D, části E.1 a E.2].
Cvičení: Body v nekonečnu projektivní Edwardsovy křivky.
(23.4.) 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.
Operace na Edwardsově křivce ve zúplněných souřadnicích [D, E.2].
(30.4.) 6. Struktura grupy eliptické křivky. Torzní prvky grupy eliptické křivky nad algebraicky uzavřeným tělesem [D, Tvrzení G.1,2].
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.
(7.5.)
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)]. 8.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] - Skripta Aleše Drápala