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

Permalink: http://www.nusl.cz/ntk/nusl-472344


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses