  The discrete logarithm problem in a finite group is the basis for many
protocols in cryptography. The best general algorithms which solve this problem
have time complexity of $\mathcal{O}(\sqrt{N}\log N)$, and a space complexity
of $\mathcal{O}(\sqrt{N})$ where $N$ is the order of the group. (If $N$ is
unknown, a simple modification would achieve a time complexity of
$\mathcal{O}(\sqrt{N}(\log N)^2)$.) These algorithms require the inversion of
some group elements or rely on finding collisions and the existence of
inverses, and thus do not adapt to work in the general semigroup setting. For
semigroups, probabilistic algorithms with similar time complexity have been
proposed. The main result of this paper is a deterministic algorithm for
solving the discrete logarithm problem in a semigroup. Specifically, let $x$ be
an element in a semigroup having finite order $N_x$. The paper provides an
algorithm, which, given any element $y\in \langle x \rangle $, provides all
natural numbers $m$ with $x^m=y$, and has time complexity $O(\sqrt{N_x}(\log
N_x)^2)$ steps. The paper also gives an analysis of the success rates of the
existing probabilistic algorithms, which were so far only conjectured or stated
loosely.
