  The semidirect discrete logarithm problem (SDLP) is the following analogue of
the standard discrete logarithm problem in the semidirect product semigroup
$G\rtimes \mathrm{End}(G)$ for a finite semigroup $G$. Given $g\in G, \sigma\in
\mathrm{End}(G)$, and $h=\prod_{i=0}^{t-1}\sigma^i(g)$ for some integer $t$,
the SDLP$(G,\sigma)$, for $g$ and $h$, asks to determine $t$. As Shor's
algorithm crucially depends on commutativity, it is believed not to be
applicable to the SDLP. Previously, the best known algorithm for the SDLP was
based on Kuperberg's subexponential time quantum algorithm. Still, the problem
plays a central role in the security of certain proposed cryptosystems in the
family of \textit{semidirect product key exchange}. This includes a recently
proposed signature protocol called SPDH-Sign. In this paper, we show that the
SDLP is even easier in some important special cases. Specifically, for a finite
group $G$, we describe quantum algorithms for the SDLP in $G\rtimes
\mathrm{Aut}(G)$ for the following two classes of instances: the first one is
when $G$ is solvable and the second is when $G$ is a matrix group and a power
of $\sigma$ with a polynomially small exponent is an inner automorphism of $G$.
We further extend the results to groups composed of factors from these classes.
A consequence is that SPDH-Sign and similar cryptosystems whose security
assumption is based on the presumed hardness of the SDLP in the cases described
above are insecure against quantum attacks. The quantum ingredients we rely on
are not new: these are Shor's factoring and discrete logarithm algorithms and
well-known generalizations.
