PředmětyPředměty(verze: 953)
Předmět, akademický rok 2022/2023
   Přihlásit přes CAS
Algoritmy na eliptických křivkách - NMMB430
Anglický název: Algorithms on Eliptic curves
Zajišťuje: Katedra algebry (32-KA)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2022
Semestr: letní
E-Kredity: 4
Rozsah, examinace: letní s.:2/1, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Způsob výuky: prezenční
Garant: doc. Mgr. et Mgr. Jan Žemlička, Ph.D.
Třída: M Mgr. MMIB
M Mgr. MMIB > Povinně volitelné
Kategorizace předmětu: Matematika > Algebra, Geometrie
Anotace -
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.
Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (18.12.2018)
Podmínky zakončení předmětu

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.

Poslední úprava: Drápal Aleš, prof. RNDr., CSc., DSc. (03.02.2022)
Literatura -

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

Poslední úprava: Drápal Aleš, prof. RNDr., CSc., DSc. (03.02.2022)
Požadavky ke zkoušce

Zkouška se skládá ze dvou částí. První část spočívá ve vytvoření programu, který implementuje Schoofův algoritmus s tím, že student/ka implementaci prověří na konkrétním zadání. Je možné program napsat též na míru danému zadání, případně místo programu udělat ruční výpočet. Pokud student/ka dá přednost výpočtu bez programování, jsou parametry křivky zvoleny tak, aby to bylo možné.

Druhá část zkoušky se týká znalosti látky tak, jak uvedeno v sylabu. Až na výjimky není vyžadována přesná znalost vzorců. Přednáška obsahuje velmi málo důkazů, takže jde především o ilustraci toho, že student/ka pochopil/a pojmy v přednášce vyložené.

Poslední úprava: Drápal Aleš, prof. RNDr., CSc., DSc. (03.02.2022)
Sylabus -

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. Isogenie a endomorfismy. Anulování charakteristického polynomu Frobeniova endomorfismu. Vysvětlení vztahu tohoto polynomu a Cayley-Hamiltonovy věty. Elkiesova a Atkinova prvočísla.

11. Hrubý nástin odvození diskriminantu eliptické křivky. Vztah diskriminantu k lineární (tj. afinní) změně souřadnic. Definice j-invariantu (nemusí být přesná znalost formule) a jeho význam pro K-ekvivalenci. Přesná formule pro j-invariant v případě y 2 = x 3 +ax+b.

Poslední úprava: Drápal Aleš, prof. RNDr., CSc., DSc. (03.02.2022)
Vstupní požadavky -

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

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (17.05.2019)
 
Univerzita Karlova | Informační systém UK