Název:
Pokročilé metody hledání diskrétního logaritmu
Překlad názvu:
Advanced techniques for calculations of discrete logarithm
Autoři:
Matocha, Vojtěch ; Příhoda, Pavel (vedoucí práce) ; Jedlička, Přemysl (oponent) Typ dokumentu: Diplomové práce
Rok:
2013
Jazyk:
cze
Abstrakt: [cze][eng] Mějme konečnou cyklickou grupu G generovanou prvkem g. Problém diskrétního logaritmu, tedy pro zadané y nalézt přirozené číslo x splňující g^x = y, představuje jeden ze základních pilířů moderních kryptografických transformací. Ve své práci podáváme přehled algoritmů, které se pro výpočet diskrétního logaritmu používají, včetně v současnosti nejrychlejšího známého algoritmu pro multiplikativní grupu konečného tělesa: funkčního síta. Kromě funkčního síta se podrobněji zabýváme index kalkulem a jeho optimalizacemi: Coppersmithovým algoritmem a polynomiálním sítem. Hlavním přínosem práce je implementace funkčního síta v jazyce C a její aplikace na konkrétní vstupy.Let G be a finite cyclic group. Solving the equation g^x = y for a given generator g and y is called the discrete logarithm problem. This problem is at the core of many modern cryptographic transformations. In this paper we provide a survey of algorithms to attack this problem, including the function field sieve, the fastest known algorithm applicable to the multiplicative group of a finite field. We also discuss the index calculus algorithm and some techniques improving its performance: the Coppersmith's algorithm and the polynomial sieving. The most important contribution of this paper is a C-language implementation of the function field sieve and its application to real inputs.
Klíčová slova:
algoritmus; diskréní logaritmus; funkční síto; algorithm; discrete logarithm; function field sieve