On search complexity of discrete logarithm
| Thesis title in Czech: | Vyhledávací složitost diskrétního logaritmu |
|---|---|
| Thesis title in English: | On search complexity of discrete logarithm |
| Key words: | diskrétní logaritmus|TFNP|PPP|PWPP|teorie složitosti |
| English key words: | discrete logarithm|TFNP|PPP|PWPP|complexity theory |
| Academic year of topic announcement: | 2020/2021 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | Mgr. Pavel Hubáček, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 20.01.2021 |
| Date of assignment: | 20.01.2021 |
| Confirmed by Study dept. on: | 19.05.2021 |
| Date and time of defence: | 23.06.2021 09:00 |
| Date of electronic submission: | 19.05.2021 |
| Date of submission of printed version: | 19.05.2021 |
| Date of proceeded defence: | 23.06.2021 |
| Opponents: | prof. Mgr. Michal Koucký, Ph.D. |
| Guidelines |
| 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. |
| References |
| [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) |