Smartův algoritmus

• Název práce v češtině: Smartův algoritmus
• Název v anglickém jazyce: Smart's algorithm
• Klíčová slova: problém diskrétního logaritmu, eliptické křivky, formální grupa, formální logaritmus, p-adická čísla
• Klíčová slova anglicky: discrete logarithm problem, elliptic curves, formal group, formal logarithm, p-adic numbers
• Akademický rok vypsání: 2014/2015
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: doc. Mgr. Pavel Příhoda, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 05.11.2014
• Datum zadání: 06.11.2014
• Datum potvrzení stud. oddělením: 25.11.2014
• Datum a čas obhajoby: 11.09.2015 00:00
• Datum odevzdání elektronické podoby: 22.07.2015
• Datum odevzdání tištěné podoby: 31.07.2015
• Datum proběhlé obhajoby: 11.09.2015
• Oponenti: doc. RNDr. Jan Šťovíček, Ph.D.

Zásady pro vypracování

Student se seznámí s algoritmem, který umožňuje na některých speciálních eliptických křivkách řešit problém diskrétního logaritmu v lineárním čase.
Původní článek N.P. Smarta doplní o příslušnou teorii a případně prozkoumá navazující práce.

Seznam odborné literatury

[1] N. P. Smart: The Discrete Logarithm Problem on Elliptic Curves of Trace One, J. Cryptology (1999) 12: 193 - 196.
[2] J. H. Silverman: The arithmetic of elliptic curves, Springer-Verlag New York, 1986.

Předběžná náplň práce

Obecně se dá říct, že grupa bodů eliptických křivek se jeví jako platforma pro diskrétní logaritmus lépe než multiplikativní grupa konečného tělesa (kde zvláště pro malé charakteristiky došlo v poslední době k velkému zrychlení výpočtu DL). Struktura takové grupy totiž není "nesena" polynomy nebo celými čísly a problém DLP se pak hůře transformuje na problém řešení (velké) soustavy lineárních rovnic. Naproti tomu existují křivky, na kterých je problém diskrétního logaritmu snadný, i přesto že grupa bodů je poměrně velká. Těmto případům by se měla práce věnovat.