Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem

ePrint Report: Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem

Muhammad Imran, Gábor Ivanyos

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 …

algorithms end eprint report problem product quantum quantum algorithms report standard