Algorithms on Elliptic Curves - NMMB430

• Title: Algoritmy na eliptických křivkách
• Guaranteed by: Department of Algebra (32-KA)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2024
• Semester: summer
• E-Credits: 4
• Hours per week, examination: summer s.:2/1, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech, English
• Teaching methods: full-time
• Guarantor: doc. Mgr. et Mgr. Jan Žemlička, Ph.D.
• Teacher(s): doc. Mgr. et Mgr. Jan Žemlička, Ph.D.
• Class: M Mgr. MMIB; M Mgr. MMIB > Povinně volitelné; M Mgr. MSTR; M Mgr. MSTR > Povinně volitelné
• Classification: Mathematics > Algebra, Geometry

Annotation

English

The course describes basic properties of elliptic curves over finite fields with regard to their use in cryptography.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (05.09.2024)

Czech

Přednáška popisuje základní vlastnosti eliptických křivek nad konečnými tělesy s ohledem na jejich využití v kryptografii.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (18.12.2018)

Course completion requirements

Zápočet bude udělen na základě vypracování domácích úkolů.

Konání zkoušky je nezávislé na udělení zápočtu.

Last update: Drápal Aleš, prof. RNDr., CSc., DSc. (03.02.2022)

Literature

English

I. Blake, G. Seroussi a N. Smart: Elliptic Curves in Cryptography, London Mathematical Society 265, Cambridge University Press, 2005

L. Washington: Elliptic Curves. Number Theory and Cryptography, Chapman & Hall/ CRC, 2003

hyperelliptic.org

A. Enge: Elliptic Curves and their Applications in Cryptography: An Introduction, Kluwer, Dordrecht 1999

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (18.12.2018)

Czech

Přednáška je pokryta (odladěnými) skripty (v angličtině), jejichž kapitoly jsou postupně během přednášky zveřejňována.

Klasické základní texty k tématu jsou:

I. Blake, G. Seroussi a N. Smart: Elliptic Curves in Cryptography, London Mathematical Society 265, Cambridge University Press, 2005

L. Washington: Elliptic Curves. Number Theory and Cryptography, Chapman & Hall/ CRC, 2003 hyperelliptic.org

A. Enge: Elliptic Curves and their Applications in Cryptography: An Introduction, Kluwer, Dordrecht 1999

Last update: Drápal Aleš, prof. RNDr., CSc., DSc. (03.02.2022)

Requirements to the exam

English

The exam consists of three parts: implementation of Schoof's algorithm, a short written test (10 questions on basic terminology and its application to easy examples), and an oral exam (discussion on one randomly choosen theoretical topic).

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (23.05.2025)

Czech

Zkouška se skládá ze tří částí: implementace Schoofova algoritmu, krátký písemný test (10 otázek ze základní terminologie a její aplikace na jednoduchých příkladech) a ústní zkouška (diskuse na jedno náhodně vybrané teoretické téma).

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (23.05.2025)

Syllabus

English

Weierstrass's normal form.

Montgomery curves.

Edwards curves.

Representation by homogeneous coordinates.

Birational equivalence.

Addition on a curve.

Number of points on the curve.

Schoof algorithm.

Choies of a suitable curve.

Curve factoring.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (23.05.2025)

Czech

Přednáška se víceméně kryje s požadavky ke zkoušce, které jsou níže specifikovány.

Cvičení je věnováno dílem procvičování látky z přednášky, dílem rozšiřující látce věnované kryptografickým aplikacím.

Znalosti potřebné ke zkoušce (text obsahuje odkazy na formule ze skript):

1. Co je to souřadnicový okruh. Popis algebraický i funkcionální. Ireducibilní afinní křivka. Její funkční těleso. Popis algebraický i funkční.

2. Planární projektivní křivka. Jak se definuje, jak ji lze získat z afinní homogenizací polynomů. Funkční těleso ireducibilní projektivní křivky. Jeho definice.

3. Význam pojmu místo. Stačí rámcový popis a znalost souvislosti s K-racionálními hladkými body křivky. Ilustrace na bodech v nekonečnu Edwardsových a Weierstrassových křivek.

4. Weierstrassova křivka. Obecná definice. Podmínka hladkosti v případě jejího zkráceného tvaru v charakteristice různé od dvou (s důkazem). Projektivní forma Weierstrassovy křivky a body v nekonečnu.

5. Montgomeryho redukce. Její idea – přesný výklad (Lemma B.1 nebo jemu předcházející úvaha). Využití pro násobení v Montgomeryho aritmetice.

6. Co je to Montgomeryho křivka. Znalost vztahu (M.5) a způsob využití tohoto vztahu pomocí Montgomeryho žebříku. Výklad, proč se lze leckdy omezit ve výpočtech na x-ovou souřadnici.

7. Definice Edwardsovy křivky a zobecněné (twisted) Edwardsovy křivky. Vzorec pro sčítání (E.3)a výklad, kdy je tento vzorec plně dostačující pro sčítání na křivce. Zúplněné souřadnice a jejich použití pro reprezentaci prvků grupy sčítání na křivce.

8. Pojem biracionální ekvivalence. Souvislost s funkčními tělesy křivek. Přechod mezi Weiestrassovými křivkami a Montgomeryho křivkami (v přesné podobě) a mezi Montgomeryho křivkami a zobecněnými Edwardsovými křivkami (není nutná přesná znalost přechodových vzorců). Souvislost s prvky grupy řádu 2 a 4.

9. Hasseova věta. Struktura E[m]. Struktura grupy eliptické křivky nad konečným tělesem. Kvadratické přechýlení a vztah (G.3), včetně důkazu.

10. Anulování charakteristického polynomu Frobeniova endomorfismu.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (23.05.2025)

Entry requirements

English

Basics of commutative algebra on level of the course Commutative rings.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (17.05.2019)

Czech

Základy komutativní algebry na úrovni kurzu Komutativní okruhy.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (17.05.2019)