@AndyPutnam I don’t see the problem here. I only care about knots on the string, not my body.

That was one of the funniest skits I ever saw.

Thank you, this was the kind of answer I had in mind when I asked the question.

See research.utwente.nl/en/publications/…

Look up the Blum-Micali algorithm.

@LSpice The flaw is what is the output of multiplication between two integers on a reversible computer? It has to include more than just the product of the two integers in order for the computation to be reversible. For instance, the output might include one of the integers that one started with.

@JoeSilverman yes that is correct. If solving discrete log is hard, can we at least easily determine which interval $\log_g a$ is in?

Thank you. I just added a bonus question.