  Generalized Discrete Logarithm Problem (GDLP) is an extension of the Discrete
Logarithm Problem where the goal is to find $x\in\mathbb{Z}_s$ such $g^x\mod
s=y$ for a given $g,y\in\mathbb{Z}_s$. Generalized discrete logarithm is
similar but instead of a single base element, uses a number of base elements
which does not necessarily commute with each other. In this paper, we prove
that GDLP is NP-hard for symmetric groups. Furthermore, we prove that GDLP
remains NP-hard even when the base elements are permutations of at most 3
elements. Lastly, we discuss the implications and possible implications of our
proofs in classical and quantum complexity theory.

Computational Complexity