On search complexity of discrete logarithm

• Název práce v češtině: Vyhledávací složitost diskrétního logaritmu
• Název v anglickém jazyce: On search complexity of discrete logarithm
• Klíčová slova: diskrétní logaritmus|TFNP|PPP|PWPP|teorie složitosti
• Klíčová slova anglicky: discrete logarithm|TFNP|PPP|PWPP|complexity theory
• Akademický rok vypsání: 2020/2021
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: Mgr. Pavel Hubáček, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 20.01.2021
• Datum zadání: 20.01.2021
• Datum potvrzení stud. oddělením: 19.05.2021
• Datum a čas obhajoby: 23.06.2021 09:00
• Datum odevzdání elektronické podoby: 19.05.2021
• Datum odevzdání tištěné podoby: 19.05.2021
• Datum proběhlé obhajoby: 23.06.2021
• Oponenti: prof. Mgr. Michal Koucký, Ph.D.

Zásady pro vypracování

Student nastuduje výsledky o výpočetní složitosti totálních problémů [1] v teorii čísel jako faktorizace [2] a problémů na mřížích [3] a pokusí se ukázat úplnost některých problémů, jako například diskrétního logaritmu, pro vhodné podtřídy TFNP.

Seznam odborné literatury

[1] Christos H. Papadimitriou: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 48(3): 498-532 (1994)
[2] Katerina Sotiraki, Manolis Zampetakis, Giorgos Zirdelis: PPP-Completeness with Connections to Cryptography. FOCS 2018: 148-158
[3] Emil Jeřábek: Integer factoring and modular square roots. J. Comput. Syst. Sci. 82(2): 380-394 (2016)