Jan Václavek

On Search Complexity of Discrete Logarithm

2021 · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

In this work, we study the discrete logarithm problem in the context of TFNP - the complexity class of search problems with a syntactically guaranteed existence of solutions for all instances. Our main results establish …