Original title:
Pokročilé metody hledání diskrétního logaritmu
Translated title:
Advanced techniques for calculations of discrete logarithm
Authors:
Matocha, Vojtěch ; Příhoda, Pavel (advisor) ; Jedlička, Přemysl (referee) Document type: Master’s theses
Year:
2013
Language:
cze Abstract:
[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.
Keywords:
algorithm; discrete logarithm; function field sieve; algoritmus; diskréní logaritmus; funkční síto
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/60093