Problém batohu a jeho aplikace
Název práce v češtině: | Problém batohu a jeho aplikace |
---|---|
Název v anglickém jazyce: | The knapsack and its applications |
Klíčová slova: | problém batohu, NP úplné problémy, LLL algoritmus |
Klíčová slova anglicky: | knapsack problem, NP complete problems, LLL algorithm |
Akademický rok vypsání: | 2016/2017 |
Typ práce: | diplomová 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í: | 01.02.2017 |
Datum zadání: | 14.02.2017 |
Datum potvrzení stud. oddělením: | 21.03.2017 |
Datum a čas obhajoby: | 13.09.2017 00:00 |
Datum odevzdání elektronické podoby: | 19.07.2017 |
Datum odevzdání tištěné podoby: | 21.07.2017 |
Datum proběhlé obhajoby: | 13.09.2017 |
Oponenti: | doc. Mgr. et Mgr. Jan Žemlička, Ph.D. |
Zásady pro vypracování |
Práce se bude zabývat problémem batohu v následujících souvislostech.
1. Shrnutí známých výsledků o složitosti problému batohu (NP úplnost, které instance jsou snadné, souvislost se složitostí dalších problémů). 2. Klasický Merkle-Hellmanův kryptosystém, útoky na něj, různé modifikace kryptosystému a útoky na tyto modifikace. 3. Konstrukce jednosměrných funkcí, které svou bezpečnost zakládají na zobecněném knapsacku. 4. Bude-li čas, je též možno zpracovat shrnutí modernějších kryptosystémů založených na problému batohu a útoků na ně. |
Seznam odborné literatury |
V. Lyubashevsky, D. Micciano, Generalized Compact Knapsacks are Collision Resistant, Electronic Colloquium
on Computational Complexity, Report No. 142 (2005) A. Odlyzko, The Rise and Fall of Knapsack Cryptosystems, http://www.dtc.umn.edu/~odlyzko/doc/arch/knapsack.survey.pdf M.R. Garey, D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness. New York: W. H. Freeman and Company, c1979. další literatura podle toho, kam se bude práce ubírat |