Název:
Vyhledávací problémy a hledání kolizí pro hašovací funkce
Překlad názvu:
Vyhledávací problémy a hledání kolizí pro hašovací funkce
Autoři:
Čarnoký, Samuel ; Krajíček, Jan (vedoucí práce) ; Pudlák, Pavel (oponent) Typ dokumentu: Diplomové práce
Rok:
2011
Jazyk:
eng
Abstrakt: [eng][cze] Title: Search problems and search for collisions in hash functions Author: Samuel Čarnoký Department: The Department of Algebra Supervisor: prof. RNDr. Jan Krajíček, DrSc. Supervisor's e-mail address: krajicek@karlin.mff.cuni.cz Abstract: Central points of this work are NP search problems and the existence of reductions amog them in the relativised world. Absolute separation would separate N from NP. In particular, we talk about the problem of finding collisions in hash functions that must exist due to the famous pigeonhole principle. We present a brief introduction into the topic, we define various NP search problems and recall reductions and separations. Reduction of weak version of PHP to a problem of finding a homogeneous subgraph is described and our own results are presented in the form of reduction of another variant of PHP to a problem related to finding paths in a graph. We talk about reducing the task of finding collisions in multiple functions into finding a collision in one function. Keywords: NP search, reductions, pigeonhole principle, oraclesNázev práce: Vyhledávací problémy a hledání kolizí pro hašovací funkce Autor: Samuel Čarnoký Katedra : Katedra algebry Vedoucí diplomové práce: prof. RNDr. Jan Krajíček, DrSc. e-mail vedoucího: krajicek@karlin.mff.cuni.cz Abstrakt: Centrálnymi bodmi tejto práce sú NP vyhľadávacie problémy a existencia redukcie medzi nimi v relativizovanom zmysle. Absolútna separácia by separovala P od NP. Venujeme sa špeciálne problému hľadania kolízii v hešovacích funkciách, ktorých existencia je garantovaná známym holubníkovým princípom (PHP). Podávame stručný úvod do problematiky, definujeme rôzne NP vyhľadávacie problémy a pripomíname redukcie a separácie. Referujeme o redukcii slabej verzie PHP na hľadanie homogénneho podgrafu a prinášame vlastnú redukciu varianty PHP na problematiku súvisiacu s hľadaním ciest v grafe. Pojednávame o redukovaní hladania kolízií vo viacerých funkciach na hľadanie kolízie v jednej. Klíčová slova: NP vyhľadávanie, redukcie, pigeonhole principle, orákula
Klíčová slova:
NP vyhľadávanie; orákula; pigeonhole principle; redukcie; NP search; oracles; pigeonhole principle; reductions