# A Deterministic Algorithm for
the Discrete Logarithm Problem in a Semigroup

Simran Tinani  Institute of Mathematics, University of Zurich, Switzerland
Joachim Rosenthal  Institute of Mathematics, University of Zurich, Switzerland

###### Abstract

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.

##  1 Introduction

Let $G$ be a group and assume $x,y\in G$ are two elements of the group. We
refer to $x$ as the base element. The discrete logarithm problem (referred to
henceforth as DLP) asks for the computation of an integer $m\in\mathbb{Z}$
(assuming such integers exist) such that $x^{m}=y$. The DLP plays an important
role in a multitude of algebraic and number theoretic cryptographic systems.
Its use was introduced in the Diffie-Hellman protocol for public key exchange
[7] and has since seen a tremendous amount of development, generalisations and
extensions [12]. Many modern-day systems for public key exchange use the
discrete logarithm problem in a suitable group. The most commonly used groups
have been the multiplicative group of finite fields and the group of points on
an elliptic curve. The DLP in Jacobians of hyperelliptic curves and more
general abelian varieties has also been studied extensively [5].

In this paper, we compute complexities using group multiplications as one
fundamental step. Thus, an exponentiation $x^{e}$ is performed in
$\mathcal{O}(\log e)$ steps. We will use the fact that for two lists of length
$n$ in which a match exists, a match can be found in $\mathcal{O}(n\log n)$
steps using standard sorting and searching algorithms (for details, the
interested reader may refer to [6]). For a general finite group of order $N$,
there exist algorithms that solve the DLP in $\mathcal{O}(\sqrt{N}\log N)$
steps. Such algorithms are said to produce a square root attack. The most
well-known examples are Shank’s Baby Step-Giant Step algorithm [18] and the
Pollard-Rho algorithm [16]. Note that Shank’s algorithm is a deterministic
algorithm having time complexity $\mathcal{O}(\sqrt{N}\log N)$ space
complexity $\mathcal{O}(\sqrt{N})$. In contrast, Pollard’s algorithm is a
probabilistic algorithm having time complexity $\mathcal{O}(\sqrt{N}\log N)$
group multiplications and space complexity $\mathcal{O}(1)$. If $N$ is
unknown, a simple modification of these algorithms would achieve a time
complexity of $\mathcal{O}(\sqrt{N}(\log N)^{2})$.

Elliptic curve groups have been widely implemented in practice since for a
carefully selected elliptic curve group the best known classical algorithm for
solving DLP has running time $\mathcal{O}(\sqrt{N}\log N)$, where $N$ is the
group order. This is in contrast to many other finite groups such as the
multiplicative group of a finite field and the group of invertible matrices
over a finite field where algorithms with subexponential running time are
known [1].

In cryptography the Diffie-Hellman protocol using a finite group has been
generalized to situations where the underlying problem is a discrete logarithm
problem in a semigroup or even to situations where a semigroup acts on a set
[10, 11]. The interested reader will find more material in a recent survey by
Goel et al. [8].

It is naturally interesting to ask whether the DLP also has a square root
attack in more generalized structures such as semigroups. Here, we define a
semigroup as any set of elements with an associative binary operation. Since
the best algorithms for the DLP all make use of the existence of inverses, it
is unclear whether they can be generalized to a semigroup. However, when a
special type of semigroup element, called a torsion element, is used as the
base, it turns out that the DLP is reducible in polynomial time to the DLP in
a finite group. A torsion element is one whose powers eventually repeat to
form a cycle, and will be defined more precisely in Section 2. This section
also elaborates more on why the standard collision-based algorithms are not
directly adaptable to the semigroup case. A semigroup in which every element
is torsion is called a torsion semigroup.

The DLP in semigroups with a torsion base element, in a classical setting, was
first discussed by Chris Monico [14] in 2002, and later in a paper by Banin
and Tsaban [3] in 2016. While the discussion in the present paper is entirely
on classical algorithms, it is also worth mentioning the paper [4], where the
authors independently provide a quantum algorithm that solves the DLP in a
torsion semigroup.

Both the algorithm of Monico and the one of Banin and Tsaban are probabilistic
and might fail with low probability. Further, some of their methods are
heuristic, dependent on an oracle or some additional assumption, and their
success rates and expected number of steps are either conjectured or stated
loosely. It is therefore of interest to come up with an algorithm which
deterministically computes the discrete logarithm in a semigroup. In this
regard we like to make some analogy to the problem of determining if an
integer is a prime number, a problem of great importance in cryptography.
Nowadays in practice the algorithm of Miller and Rabin [13, 17] has been
implemented for many years. Still it was a great result when Agrawal, Kayal
and Saxena [2] came up with a deterministic polynomial time algorithm to
achieve this goal.

A key step in finding the discrete logarithm in a semigroup is computing the
cycle length of an element. Both the algorithms of [3] and [14] rely on
computing some multiple of the cycle length, and then removing “extra” factors
by taking gcd’s until the cycle length is obtained. Once the cycle length
value is obtained, the discrete logarithm may easily be computed with a few
more simple steps. While Monico does not provide further elaboration on how
this is done, the paper by Banin and Tsaban bridges this knowledge gap by
showing how the problem is reduced to a DLP in a group once the cycle length
and start values are known. Denote by $N_{x}$ the order of $x$ (formally
defined in Definition 4). The complexity of the algorithm in [3] is
$\mathcal{O}(\sqrt{N_{x}}(\log N_{x})^{2}\log\log N_{x})$, and the of the one
in [14] is $\mathcal{O}(\sqrt{N_{x}}(\log N_{x})^{2})$. While both of the
existing methods seem to succeed with high probability for practical values,
we show that the process of taking successive gcd’s/factors is unnecessary,
and that one can deterministically find the cycle length. The main
contribution of this paper will be a deterministic algorithm for computing the
discrete logarithm of an element $y$ in some semigroup $S$ with respect to
some torsion base element $x\in S$. The time complexity of our algorithm is
$\mathcal{O}(\sqrt{N_{x}}(\log N_{x})^{2})$.

The paper is structured as follows: After providing preliminaries and basic
definitions in Section 2, we will analyse in Section 3 the success rates and
expected number of steps involved in the probabilistic algorithms for cycle
length by Banin and Tsaban (Algorithm 1) and Monico (Algorithm 3).

In Section 4, which is the main section of this paper, we provide a
deterministic algorithm to calculate the cycle length $L_{x}$ of a torsion
element $x$ of a semigroup and thus to also solve the DLP, without the use of
an oracle. This algorithm has complexity
$\mathcal{O}\left(\sqrt{N_{x}}\cdot(\log N_{x})^{2}\ \right).$ For
completeness, we will also demonstrate the use of Pohlig–Hellman algorithm
[15] for a semigroup.

##  2 Preliminaries

A semigroup $S$ is a set together with an associative binary operation. Like
in group theory where a torsion group consists of elements of finite order
only we define:

######  Definition 1 (Torsion Element).

Let $S$ be a semigroup. An element $x\in S$ is called a torsion element if the
sub-semigroup $\langle x\rangle:=\\{x^{k}\mid k\in\mathbb{N}\\}$ generated by
$x$, is finite. $S$ is called a torsion semigroup if every $x\in S$ is a
torsion element.

Throughout the paper the following definitions will be assumed:

######  Definition 2 (Cycle Start).

Let $x\in S$. The cycle start $s_{x}$ of $x$ is defined as the smallest
positive integer such that $x^{s_{x}}=x^{b}$ for some $b\in\mathbb{N}$,
$b>s_{x}$.

######  Definition 3 (Cycle Length).

Let $x\in S$. The cycle length $L_{x}$ of $x$ is defined as the smallest
positive integer such that $x^{s_{x}+L_{x}}=x^{s_{x}}$.

######  Definition 4 (Element order).

Let $x\in S$. With notation as above, we define the order $N_{x}$ of $x$ as
the cardinality of the sub-semigroup $\langle x\rangle$. Note that
$N_{x}=s_{x}+L_{x}-1.$

######  Definition 5 (Semigroup DLP).

Let $S$ be a semigroup and $x\in S$. The semigroup DLP is defined as follows.
Given $y\in\langle x\rangle:=\\{x^{k}\mid k\in\mathbb{N}\\}$, find all $m\in
N$ such that $x^{m}=y$.

We state below a key result first proved in [3].

######  Lemma 1 ([3]).

Let $S$ be a semigroup and $x\in S$ be an element with cycle start $s_{x}$.
The set of powers $G_{x}=\\{x^{s_{x}+k}\mid k\geq 0\\}$ of $x$ forms a finite
cyclic group. The identity element of $G_{x}$ is given by $x^{tL_{x}}$, where
$t$ is the minimum positive integer such that $x^{tL_{x}}\in G_{x}$.

The following result is stated in [14] in a slightly different formulation. We
provide an equivalent proof based on the group structure of $G_{x}$.

######  Lemma 2 ([14]).

Let $x\in S$ have cycle start $s_{x}$ and cycle length $L_{x}$. For all
integers $n,m\geq s_{x}$, we have $x^{m}=x^{n}\iff n\equiv m\mod L_{x}$.

###### Proof.

We can assume without loss of generality that $n\geq m$, and so we can write
$n=m+kL_{x}+u$, with $k\geq 0$ and $0\leq u<L_{x}$. First suppose that
$n\equiv m\mod L_{x}$, i.e. $u=0$. Since $m,n\geq s_{x}$, we have
$x^{n}=x^{m+kL_{x}}=x^{m}$.

Conversely, if $x^{n}=x^{m}$, write $n_{1}=n-s_{x}\geq 0$, and
$m_{1}=m-s_{x}\geq 0$. We have

$x^{s_{x}+m_{1}}=x^{s_{x}+n_{1}}=x^{s_{x}+m_{1}+kL_{x}+u}=x^{s_{x}+m_{1}+u}.$

Now, without loss of generality, $m_{1}\geq s_{x}$, because if not, one can
always increment $m_{1}$ and $n_{1}$ by multiples of $L_{x}$ until this
happens. So, we can assume that $x^{m_{1}}$ lies in $G_{x}$ and is thus
invertible. We multiply by the inverse on both sides to finally get

$x^{s_{x}}=x^{s_{x}+u}.$

Thus, we must have $u=0$ or $n\equiv m\mod L_{x}$, as required.

∎

######  Remark 1.

It becomes clear from the above discussion that the standard collision-based
algorithms for order and discrete log computations in a group do not adapt
directly to a general semigroup. Collision-based algorithms for the
computation of the order $N$ of a group element $x$ (for instance, see [19])
are based on the principle that whenever $N$ can be expressed in the form
$N=A-B$ for non-negative integers $A$ and $B$, the collision $x^{A}=x^{B}$
always occurs. However, this principle does not work in a semigroup, where
there are two independent components of the order. More specifically, for a
semigroup element $x$ with cycle length $L_{x}$ and cycle start $s_{x}$,
whenever $L_{x}$ may be expressed in the form $A-B$ for non-negative integers
$A$ and $B$, the equality $x^{A}=x^{B}$ holds if and only if $A,B\geq s_{x}$.
As an example, consider a semigroup element $x$ with cycle length $L_{x}=12$
and cycle start $s_{x}=5$. Then, $L_{x}=15-3$, but $x^{15}\neq x^{3}$. Thus
without prior knowledge of the cycle start, the semigroup order $N_{x}$ or
cycle length $L_{x}$ cannot directly be found using the same collision-based
algorithms for groups.

Similarly, collision-based algorithms fail for discrete log computations in a
semigroup. As an example, consider a semigroup element $x$ with cycle length
$L_{x}=15$ and cycle start $s_{x}=10$, and suppose that the discrete log of
$y=x^{5}$ is to be found. Then $y\cdot x^{6}=x^{11}=x^{26}$ is obtained as a
collision. However, unlike in the group case, the conclusion
$y=x^{26-6}=x^{20}$ is wrong since $x^{5}\neq x^{20}$. This happens because
even though $x$ is torsion and forms a cycle of powers, it is not invertible.

This concludes the prerequisite knowledge on torsion elements in semigroups.
In the next section, we study the existing probabalistic algorithms for cycle
lengths, and analyse their assumptions, working and complexities.

##  3 Existing Probabalistic Agorithms

###  3.1 Banin and Tsaban’s Algorithm

In this section, we study the probabalistic algorithm described in [3] for
computing the cycle length of a torsion element in a semigroup. While the
authors of the original paper describe their theory only for torsion
semigroups, it will become clear that the same discussion holds true for any
semigroup when the base element chosen is torsion.

Let $S$ be a semigroup and $x$ be a torsion element of $S$. Let $s_{x}$ denote
the cycle start of $x$ and $L_{x}$ its cycle length. Then, recall from Lemma 1
that $G_{x}:=\\{x^{s_{x}},x^{s_{x}+1},\ldots,x^{s_{x}+L_{x}-1}\\}$ is a cyclic
group, and that it has order $L_{x}$. The authors of [3] assume the
availability of a ‘Discrete Logarithm Oracle’ for the group $G_{x}$, which
returns values $\log_{x}h$ for $h\in G_{x}$. They state that these values need
not be smaller than the group order but are polynomial in the size of $G_{x}$
and the element $x$. The representation of the identity in $G_{x}$ is unknown,
and a method to compute inverses is not available.

The authors claim that the well-known algorithms for discrete logarithm
computations in groups do not explicitly require inverses, or can easily be
modified to work without the use of inverses. While it is true that these
algorithms make use of mainly the existence of inverses rather than their
explicit computation, we believe that the fact that easy modification is
possible is not immediate without some justification. In fact, it will become
clear in the later sections that the modified Baby-Step-Giant-Step algorithm
devised by Monico [14] (and also the deterministic algorithm presented in
Section 4) is a crucial and non-trivial part of any such modification.

We make the following observation from the proof of Lemma 1 found in [3]. For
any $k\geq 0$, denote by $v_{k}$ the smallest positive integer such that

$v_{k}L_{x}\geq 2s_{x}+k.$

We then have $x^{v_{k}L_{x}-s_{x}-k}\in G_{x}$ and

$x^{s_{x}+k}x^{v_{k}L_{x}-s_{x}-k}=x^{v_{k}L_{x}}=x^{tL_{x}},$ (1)

so the inverse of the element $x^{s_{x}+k}$ of $G_{x}$ is given by
$x^{v_{k}(L_{x})-s_{x}-k}$. In particular, the computation of inverses
requires prior knowledge of the cycle start. As will be explained below, the
cycle start may be computed only once the value of the cycle length is known,
using a binary search. This explains why the authors insist that their
Discrete Logarithm Oracle does not need to use the computation of inverses.

Below, we describe Algorithm 1, which is the algorithm suggested in [3] to
compute the order of the group $G_{x}$, i.e. the cycle length $L_{x}$ of $x$.

Input A semigroup $S$ and a torsion element $x\in S$; a DLP oracle for groups

Output The cycle length $L_{x}$ of $x$

1: Initialize $i,j,g,L_{x}\leftarrow 1$, $N>>s_{x}+L_{x}$. Fix bounds
$r>1,s>1$.

2: while $j<s$

  1. 1.

Fix a random $z\in\\{\lfloor M/2\rfloor,\ldots,M\\}$ and set $h=x^{z}$.

  2. 2.

while $i<r$

    1. (a)

Choose a random number $k_{i}>0$.

    2. (b)

Use the DLP oracle to compute $k_{i}^{\prime}=\log_{h}(h^{k_{i}})$.

    3. (c)

Set $g\leftarrow\gcd\limits_{j\leq
i}(k_{j}-k_{j}^{\prime})=\gcd\left(\gcd\limits_{j<i}(k_{j}-k_{j}^{\prime}),\
k_{i}-{k_{i}}^{\prime}\right)$.

    4. (d)

Set $i\leftarrow i+1$.

  3. 3.

end while

  4. 4.

Set $L_{x}\leftarrow lcm(L_{x},g)$, $j\leftarrow j+1$.

6: Return $L_{x}$.

Algorithm 1 Banin-Tsaban Algorithm for Cycle Length

We first note that the authors state complexities in terms of $L_{x}$, which
are valid when the bound $N$ for $N_{x}$ is known. If the algorithm fails for
a value of $N$, the authors suggest to double $N$ and try again. In this case,
which we will assume from now on, we assert that the complexities need to be
taken in terms of $N_{x}$ instead of $L_{x}$. The oracle may be assumed to
have the standard complexity of $O(\sqrt{N_{x}}\log N_{x})$ steps for discrete
logarithm calculations. Step 2.2(c) takes $\mathcal{O}(\log(\max_{j\leq
i}(k_{j}-k_{i}))=\mathcal{O}(\log N_{x})$ integer operations by the assumption
on the oracle, which does not contribute to the total complexity. Thus, the
total complexity of step (2.2) comes from the oracle alone, and is
$\mathcal{O}(\sqrt{N_{x}}\log N_{x})$. Now, the authors of [3] remark that $r$
and $s$ can be taken to satisfy $r=\mathcal{O}(1)$ and $s=\mathcal{O}(\log\log
N_{x})$. Thus, the total complexity is $\mathcal{O}(\log N_{x})$ times the
complexity of Algorithm 1, and thus $\mathcal{O}(\log\log(N_{x})\log N_{x})$
times the complexity of step (2.2). Therefore, we get the total complexity of
$\mathcal{O}(\log\log N_{x}(\log N_{x})^{2}\sqrt{N_{x}})$.

Finally, in Algorithm 2, we present the application of the binary search
method to find the cycle start once $L_{x}$ is known. This algorithm is
formulated as below for this purpose in [3], though the idea to use a binary
search is also originally mentioned in [14].

Input A semigroup element $x$ with cycle length $L_{x}$

Output Cycle start $s_{x}$ of $x$

1: Initialize $s_{x}\leftarrow 1$

2: while $x^{s_{x}+L_{x}}\neq x^{s_{x}}$ do

$s_{x}\leftarrow 2s_{x}$

3: end while

4: Set $a\leftarrow s_{x}/2$

5: while $|a-s_{x}|\geq 2$

$c\leftarrow(a+s_{x})/2$

if $x^{c+L_{x}}\neq x^{c}$ then

$a\leftarrow c$

else

$s_{x}\leftarrow c$

6: end while

Algorithm 2 Calculating Cycle Start (Binary Search)

######  Lemma 3.

Let $N_{x}$ be the order of the element $x$. Then Algorithm 2 requires

$\mathcal{O}\left((\log N_{x})^{2}\right).$

steps.

###### Proof.

Each of Steps (2) and (5) involves $\mathcal{O}(\log N_{x})$ rounds, each of
which computes requires $\mathcal{O}(\log N_{x})$ semigroup multiplications
and one comparison. The total complexity is thus $\mathcal{O}\left((\log
N_{x})^{2}\right)$. ∎

###  3.2 Monico’s Algorithm

In his PhD thesis [14], Chris Monico provides a probabilistic algorithm
(described below as Algorithm 3) that calculates the cycle length of an
element in a finite ring of order $N$. This algorithm makes use of the
multiplicative semigroup structure of the finite ring, and of the availability
of the explicit bound $N$ for every cycle length, and is in fact applicable to
any semigroup where such a bound $N$ is available. In this subsection, we
analyse this algorithm, provide a more concrete bound on its success rate, and
compute its complexity in terms of $N$. We will discuss this algorithm in
terms of torsion semigroups, as opposed to finite rings.

Input A finite semigroup $S$ with $\lvert S\rvert=N$ and an element $x\in S$

Output The cycle length $L_{x}$ of $x$

1: Set $m=\lceil\sqrt{N}\rceil$. Choose a prime $q>N$.

2: For $0\leq i\leq m$, compute and store in a table the pairs $(i;x^{q+im})$.

Sort the table by the second component.

3: Find the least positive integer $b_{1}$ such that $x^{q+b_{1}}$ is in the
table: $x^{q+b_{1}}=x^{q+a_{1}m}$. (Note: $0<b_{1}<m$).

4: Find the least positive integer $b_{2}$ such that $x^{2q+b_{2}}$ is in the
table: $x^{2q+b_{2}}=x^{q+a_{2}m}$. (Again, $0<b_{2}<m$).

5: Compute $g=\gcd(a_{1}m-b_{1},a_{2}m-b_{2}-q)$.

6: For each divisor $d$ of $g$ below some bound $B$, do the following.

If $x^{N+g/d}=x^{N}$:

set $g\leftarrow g/d$;

7: Output $L_{x}=g$ and stop.

Algorithm 3 Monico’s Baby-Step Giant-Step for Cycle Length

We first note that if $L_{x}>m$ and the table in Step (2) has repeated entries
$x^{q+i_{1}m}=x^{q+i_{2}m}$, then numbers $b_{1}$ and $b_{2}$ may not exist
below $m$. In this case the algorithm needs to be modified to take
$g\leftarrow(i_{1}-i_{2})m$. However, whenever this case does not arise, it
can be shown that steps 3 and 4 are always successful in finding a collision.

We further remark that in step 6, the list of divisors of $g$ is kept fixed,
while $g$ is updated to $g/d$ whenever the condition is satisfied. In the
subsequent steps, non-divisors of $g/d$ can be immediately discarded. However,
the end result depends on the order in which divisors are tested, which the
algorithm does not mention explicitly. However, we note that it is, in fact,
possible to restrict the testing to only the prime power divisors of $g$ below
$B$, and with this setting, the optimal performance is obtained by taking
divisors in decreasing order. We will assume this set-up for the rest of the
analysis.

Step (2) involves $\mathcal{O}(\log N)$ steps compute $x^{q}$ and $x^{m}$ and
another $\mathcal{O}(\sqrt{N})$ multiplications to compute $x^{q},x^{q}\cdot
x^{m},x^{q}\cdot x^{2}m,\ldots,x^{q}\cdot x^{m^{2}}$. Step 3 involves at most
$m$ multiplications $x^{q+1}=x^{q}\cdot x,x^{q+1}\cdot x,\ldots,x^{q+m-1}$,
with complexity $\mathcal{O}(\sqrt{N})$, and match-finding with the first
list, with complexity $\mathcal{O}(\sqrt{N}\log N)$ with standard sorting and
search algorithms. The same is true for step (4). Step (5) has complexity
$\mathcal{O}(\log\max(a_{1}m-b_{1},a_{2}m-b_{2}-q))=\mathcal{O}(\log N)$ and
so does not contribute to the overall complexity. Step 6 involves $B$
iterations of a multiplication and an exponentiation $x^{g/d}$, and thus has a
time complexity of $\mathcal{O}(B(\log g+1))=\mathcal{O}(B\log N)$
multiplications.

In the original work, Monico states that the bound $B$ of Algorithm 3 can
always be chosen so that $B<\sqrt{a_{1}m-b_{1}}$. We remark that this claim
does not hold in the current setting of the algorithm. For example, with a
cycle length value of 4, and $a_{1}m-b_{1}=104$, $a_{2}m-b_{2}-q=52$, we get
$g=52$. If $B<\sqrt{a_{1}m-b_{1}}=\sqrt{104}<11$, then we would only test
divisors $d$ below 11, and would never factor out 13 to obtain the true cycle
length. For such a bound to work, one needs to modify the algorithm to test
both divisors $g$ and $g/d$ in step 6. However, we will show in Lemma 4 that
it is almost always sufficient to take $B$ to be a reasonably large fixed
constant, thus the complexity of step 6 can be counted as $\mathcal{O}(\log
N)$, and does not contribute to the overall complexity. Thus, the overall time
complexity is $\mathcal{O}(\sqrt{N}\log N)$. If $N$ is unavailable, the
algorithm can also be modified to update the value of $N$ step-by-step until a
large enough value is found. In this case, Algorithm 3 has a total complexity
of $\mathcal{O}(\sqrt{N_{x}}(\log N_{x})^{2})$.

Further, Monico suggests a modification to the above algorithm, viz. to find
several such $a_{i}$ and $b_{i}$ and compute all the gcd’s. It is clear that
this suggestion is exactly the method used in Banin and Tsaban’s algorithm as
discussed in Section 3.1.

We now analyze the probability of success. The algorithm first looks for a
collisions of the form $x^{q+{a_{1}}m}=x^{q+b_{1}}$. The working principle is
that in this case, the cycle length $L_{x}$ divides $a_{1}m-b_{1}$. Similarly,
if also $x^{q+{a_{2}}m}=x^{2q+b_{2}}$ then
$g=\gcd(a_{1}m-b_{1},a_{2}m-b_{2}-q)$ is a multiple of $L_{x}$.

So far, the process is essentially the same in both Algorithms 1 and 3: while
the former uses a discrete logarithm oracle to obtain multiples of the cycle
length, the latter directly finds these multiples by finding collisions.
However, in Algorithm 3, we do not proceed with computing multiple factors of
$L_{x}$, but work with the fixed multiple $g$ of $L_{x}$, whereas in Algorithm
1 this multiple shrinks several times.

Algorithm 3 then proceeds by fixing a bound $B$ and iterating over every
number $d$ below $B$ to check if $d\mid g$. If yes, it executes the next part,
i.e. checks if $x^{N+D/d}=x^{N}$, and if this holds, it sets $D\leftarrow
D/d$. Note that if the factorization of the number $g$ is known (or if $g$ can
be factored in time negligible compared to $O(\sqrt{N})$, then we do not need
this fixed bound $B$, and can instead iterate over every prime factor $d$ of
$g$. It is well-known that the number of prime factors of $g$ counted with
multiplicity is $\mathcal{O}(\log g)$, so Step (5) of the algorithm can find
$L_{x}$ in $\mathcal{O}(\log N)$ steps. However, in general, factoring $g$ may
be difficult, so we assume from here on that the algorithm proceeds by fixing
a bound $B$ for the divisors of $g$. Below we analyse the probability of the
algorithm succeeding in terms of $B$ and $g$.

######  Lemma 4.

The probability that Algorithm 3 succeeds is bounded below by
$\left(1-\frac{1}{B}\right)^{\log g}$.

###### Proof.

We write $g=L_{x}\cdot F$ for some number $F$ and suppose that the algorithm
fails. This means that there is a divisor, and hence also a prime power
divisor of $F$, which the algorithm fails to factor out. Let $p$ be a prime
dividing $F$, $\alpha_{p}$ denote its largest power dividing $F$, and
$\beta_{p}$ be its largest power below the fixed bound $B$. So, we have
$p^{\alpha_{p}}\mid F$, $p^{\alpha_{p}+1}\nmid F$, $p^{\beta_{p}}<B$,
$p^{\beta_{p}+1}>B$.

Since the number of times the algorithm divides $g$ by $p$ is

$\sum\limits_{i=1}^{\beta_{p}}i=\beta_{p}\cdot(\beta_{p}+1)/2,$

we must have $\beta_{p}\cdot(\beta_{p}+1)/2<\alpha_{p}$ if the algorithm
fails. So, the algorithm succeeds as long as
$\beta_{p}\cdot(\beta_{p}+1)/2\geq\alpha_{p}$ for every prime divisor $p$ of
$F$. Thus, the probability of success for the algorithm can be bounded below
by

$\displaystyle\prod_{p\mid
g}\mathrm{Prob}\left(\frac{\beta_{p}\cdot(\beta_{p}+1)}{2}\geq\alpha_{p}\right).$

Write $v_{p}=\frac{\beta_{p}(\beta_{p}+1)}{2}$ for simplicity. We may assume
that $g$ is a random multiple of $L_{x}$ below the bound $B$, so $F$ is a
random number in $\\{1,\ldots,\frac{B}{L_{x}}\\}$. We have,

$\displaystyle\mathrm{Prob}(\alpha_{p}\leq v_{p})=$ $\displaystyle
1-\mathrm{Prob}(p^{v_{p}+1}\mid F)$ $\displaystyle=$ $\displaystyle
1-\left(\frac{B/L_{x}}{p^{v_{p}+1}(B/L_{x})}\right)$ $\displaystyle=$
$\displaystyle
1-1/p^{v_{p}+1}=1-\dfrac{1}{p^{\frac{\beta_{p}(\beta_{p}+1)}{2}+1}}.$

Hence, a lower bound for the probability of the algorithm’s success is

$\prod\limits_{p\mid
F}\left(1-\dfrac{1}{p^{\frac{\beta_{p}\cdot(\beta_{p}+1)}{2}+1}}\right).$

Now, we have,

$\displaystyle p^{\beta_{p}+1}>B\;\iff\dfrac{1}{p^{\beta_{p}+1}}<\dfrac{1}{B}$
$\displaystyle\implies$ $\displaystyle
1-\dfrac{1}{p^{\frac{\beta_{p}(\beta_{p}+1)}{2}+1}}>1-\dfrac{1}{B^{\frac{\beta_{p}}{2}+1}}>1-\dfrac{1}{B}.$

We further make the following observation. Let $\omega(n)$ denote the number
of distinct prime divisors of integer $n$ (note, however, that the same
statement also holds if counted with multiplicity). Then clearly,
$2^{\omega(n)}\leq n,$ and so, taking logarithms, $\omega(n)\leq\log_{2}n.$

Collecting all the above results, we conclude that the probability of success
Prob (success) of Algorithm 3 is bounded below as follows.

Prob (success) $\displaystyle\geq\prod_{p\mid F}\left(1-\frac{1}{B}\right)$
$\displaystyle=\left(1-\frac{1}{B}\right)^{\omega(F)}\geq\left(1-\frac{1}{B}\right)^{\log
F}$ $\displaystyle\geq\left(1-\frac{1}{B}\right)^{\log g}.$

∎

Note that this bound shows that Algorithm 3 is indeed successful with
overwhelming probability, as conjectured by the author. For example, with
$B=10^{6}$, even when $g$ is several orders of magnitude larger than $B$, say
$g=2^{4000}$, the probability of success is greater than 99.6 percent, by the
bound derived in Lemma 4.

##  4 Deterministic Solution of the DLP

The solution of the DLP in a semigroup involves two parts: the calculation of
the cycle length and start of the base element $x$, and the use of this value
to find the discrete log.

###  4.1 Deterministic Algorithm for Cycle Length Computation

We now present our deterministic algorithm for the computation of the cycle
length. It works by finding a suitable collision, and also guarantees finding
the actual cycle length rather than just a multiple of it, in a fixed number
of steps.

Input A semigroup $S$ and a torsion element $x\in S$. Assume $N_{x}$ is the
order of $x$.

Output Cycle length $L_{x}$ of $x$

1: Initialize $N\leftarrow 1$.

2: Set $q\leftarrow\lceil\sqrt{N}\rceil$.

3: Compute, one by one, $x^{N},x^{N+1},\ldots,x^{N+q}$ and check for the
equality $x^{N}=x^{N+j}$ at each step $j\geq 1$. Store these values in a table
as pairs $(N+j,x^{N+j})$, $0\leq j<q$. If $x^{N}=x^{N+j}$ for any $j<q$, then
set $L_{x}\leftarrow j$ and end the process. If not, proceed to the next step.

4: For $0\leq i\leq q$, compute, one by one, the values
$x^{N+q},x^{N+2q},\ldots,x^{N+iq}$ and at each step $i$, look for a match in
the table of values calculated in Step (3).

5: Suppose that a match $x^{N+iq}=x^{N+j}$ is found, and $i$ is the smallest
integer such that this happens. Set $L_{x}\leftarrow iq-j$ and end the
process.

6: If no match is found in steps 3 or 5, set $N\leftarrow 2\cdot N$ and go
back to Step (2).

Algorithm 4 Deterministic Algorithm for Cycle Length

######  Theorem 1.

Let $S$ be a semigroup and $x\in S$ a torsion element with order $N_{x}$. If
an upper bound on $N_{x}$ is known, Algorithm 4 returns the correct value of
the cycle length $L_{x}$ with

$\mathcal{O}\left(\sqrt{N_{x}}\cdot(\log N_{x})^{2}\ \right)$

steps. The total space complexity is $\mathcal{O}\left(\sqrt{N_{x}}\right)$
semigroup elements.

###### Proof.

We first assume $N\geq\max(L_{x},s_{x})$ and show that steps 1 to 5 succeed in
finding $L_{x}$. We have $q=\lceil\sqrt{N}\rceil$. If $L_{x}<q$, then the
equality $x^{N}=x^{N+L_{x}}$ is found in the first step and the statement of
the theorem follows. Else if $L_{x}\geq q$, we can write uniquely

$L_{x}=iq-j,$

for some positive integers $i>0$, $0\leq j<q$. Now, we must have $i\leq q$,
because otherwise if $i\geq q+1$, we would have

$L_{x}\geq(q+1)q-j>q^{2}+q-q=q^{2}\geq N,$

a contradiction.

We have

$\displaystyle L_{x}=iq-j,\;0<i\leq q,0\leq j<q$ $\displaystyle\implies$
$\displaystyle N+j+L_{x}=N+iq$ $\displaystyle\implies$ $\displaystyle
x^{N+j}=x^{N+j+L_{x}}=x^{N+iq},$

where the last step follows because $N>s_{x}$ by assumption. So, such a
collision always occurs between elements of the two lists in the algorithm.

We now claim that for the smallest such integer $i$ computed in Step (5) of
Algorithm 4, $L_{x}=iq-j$.
To see this, let $i$ be the smallest positive integer such that

$x^{N+j}=x^{N+iq}.$

Also let $L_{x}=i^{\prime}q-j^{\prime}$, $0<i^{\prime}\leq q$, $0\leq
j^{\prime}<q$. We have already shown above that such integers $i^{\prime}$ and
$j^{\prime}$ exist for our choice of $N$. By the definition of $L_{x}$, we
must have $L_{x}\mid iq-j$. Now suppose that $i^{\prime}>i$. Then,

$\displaystyle i^{\prime}q-j^{\prime}\geq$ $\displaystyle(i+1)q-j^{\prime}$
$\displaystyle=$ $\displaystyle iq+(q-j^{\prime})>iq$ $\displaystyle\geq$
$\displaystyle iq-j.$

But, $L_{x}=i^{\prime}q-j^{\prime}\mid iq-j$, so we must have
$iq-j=i^{\prime}q-j^{\prime}$. Since $i^{\prime}>i$, this means that

$q\leq(i^{\prime}-i)q=(j^{\prime}-j)<j^{\prime},$

which is a contradiction because $0\leq j^{\prime}<q$. So, we must have
$i^{\prime}=i$, $j^{\prime}=j$. This proves the claim.

We have shown above that the algorithm finds the correct cycle length when
$N>\max(s_{x},L_{x})$. Since the algorithm doubles the value of $N$ until a
match is found, it always terminates and outputs the correct cycle length. We
now look at the time complexity.

For a given $N$, step (2) involves one exponentiation, or $\mathcal{O}(\log
N)$ multiplications to find $x^{N}$ and then at most another
$q=\mathcal{O}(\sqrt{N})$ multiplications and equality checks for $x^{N}\cdot
x,x^{N}\cdot x^{2},\ldots,x^{N}\cdot x^{q}$. This step also needs a storage
space of at most $q=\mathcal{O}(\sqrt{N})$ elements. Step 5 needs one
exponentiation or $\mathcal{O}(\log N)$ multiplications to find $x^{q}$, and
then another $q=\mathcal{O}(\sqrt{N})$ multiplications to find $x^{N+q}\cdot
x^{q},x^{N+q}\cdot x^{2q}\ldots,x^{N+q^{2}}$. Finding matches in steps 3 and 5
can be done in $\mathcal{O}(q\log q)=\mathcal{O}(\sqrt{N}\log\sqrt{N})$
comparisons with the use of sorting and efficient look-up methods. Thus,
clearly, steps 1 to 5 in algorithm 4 have a total complexity of
$\mathcal{O}(\sqrt{N}\log N)$.

Moreover, the algorithm starts at $N=1$ and doubles $N$ until the cycle length
is found, i.e. until $N>\max(s_{x},L_{x})$. Thus, the number of times steps 2
to 5 are performed is

$\displaystyle\left\lceil\log\left(\max\left(L_{x},s_{x}\right)\right)\right\rceil=\mathcal{O}\left(\max\left(\log\left(L_{x}\right),\log(s_{x})\right)\right)=\mathcal{O}(\log
N_{x})$

Thus, the total number of steps involved is

$\mathcal{O}\left(\sqrt{N_{x}}\cdot(\log N_{x})^{2}\right).$

Clearly, Step (3) involves the storage of
$q=\lceil\sqrt{N}\rceil=\mathcal{O}\left(\sqrt{\max(s_{x},L_{x})}\right)=\mathcal{O}\left(\sqrt{N_{x}}\right)$
elements, so this value gives the total space complexity. This completes the
proof. ∎

######  Remark 2.

If a bound $N$ on the order $N_{x}$ is known a priori, then Algorithm 4 can
clearly be completed in a single round, with time complexity
$\mathcal{O}\left(\sqrt{N}\cdot(\log N)\right)$.

######  Remark 3.

For the case of a group, there exist better algorithms for the computation of
the order of an element even when the total group order is unbounded. For
instance, Algorithm 3.3 in [19] uses a growth function $d(t)$, which
generalizes the square root function used above, to compute the order $N$ of a
group element $x$, and achieves time and space complexities of
$\mathcal{O}\left(\sqrt{N}\right)$, thus eliminating the additional $\log N$
multiplier introduced by the method in Algorithm 4.

However, this method fails when used for a general semigroup due to the
presence of two independent unknown components of the order. To see this, note
that the algorithm would need to be modified for a semigroup as follows. At
stage $t$, one has $g(t-1)\leq N_{x}<g(t)$. On the completion of the baby
steps, one has a table with the powers
$x^{g(t)},x^{g(t)+1},\ldots,x^{g(t)+b(t)}$ (the addition of $g(t)$ is
necessary in the semigroup case to ensure that the loop is entered). The giant
steps compute $x^{g(t)+g(t-1)+\cdot b(t)},x^{g(t)+g(t-1)+2\cdot
b(t)},\ldots,x^{g(t)+g(t-1)+d(t)\cdot b(t)}=x^{2g(t)}$. Now, while $N_{x}$ is
guaranteed to have a unique expression as $g(t-1)+ib(t)-j$ with $0<i\leq d(t)$
and $0\leq j\leq b(t)$, this does not necessarily lead to a collision. In
fact, if $b(t)<L_{x}<g(t-1)$ and $2L_{x}>g(t)=g(t-1)+d(t)\cdot b(t)$, then
neither the baby steps nor the giant steps leads to a collision, and the cycle
length is never found (note that this can happen only if $L_{x}>s_{x}$).
Moreover, if a collision $x^{g(t)+g(t-1)+ib(t)}=x^{g(t)+j}$ is obtained in the
giant step phase, the only conclusion that can be drawn is that $L_{x}\mid
g(t-1)+ib(t)-j$. If instead we forced the condition $g(t-1)\leq N_{x}<g(t)$, a
collision again may never occur because there is no control on the cycle start
(For instance, in matrix semigroups over finite simple semirings, the cycle
start is often found to be much larger than the cycle length. In such cases,
adapting group-based algorithms would fail). See Remark 1 for further details.

####  4.1.1 Experimental Results for Cycle Length Computations

We used Algorithm 4 to compute cycle length values in several common
semigroups, such as matrix semigroups over finite fields, matrix semigroups
over the finite simple semiring $S_{20}$ (see [20] for a construction and [11]
for the addition and multiplication tables), and the symmetric and alternating
groups (where the cycle length is precisely the order of the element). We
further used the obtained cycle lengths to compute the cycle start values
using Algorithm 2. The working code may be found at
https://github.com/simran-tinani/semigroup-cycle-length.

###  4.2 Solving the DLP once the Cycle Length is known

In this section, we demonstrate the solution of the DLP for a torsion element
$x$ in the semigroup $S$ once the cycle length is known. As before let $N_{x}$
be the order of the sub-semigroup $\langle x\rangle$, let $L_{x}$ be the cycle
length of the torsion element $x$ (which we assume is already computed) and
let $y\in\langle x\rangle$ be an element.

In [3], the authors demonstrate the next steps in solving for $\log_{x}(y)$,
via a reduction to a DLP in the group $G_{x}$, once $L_{x}$ and $s_{x}$ are
known. The procedure is described in Algorithm 5 below, which has been adapted
from the original formulation in [3].

Input A semigroup $S$, a torsion element $x\in S$, with cycle length $L_{x}$
and cycle start $s_{x}$, and $y\in S$ with $y=x^{m}$

Output The discrete logarithm $m$ of $y$ with base $x$

1: Compute $t=\left\lceil\frac{s_{x}}{L_{x}}\right\rceil$ and define
$x^{\prime}=x^{tL_{x}+1}\in G_{x}$.

2: Find the minimum number $0\leq b\leq t$ such that $y^{\prime}=y\cdot
x^{bL_{x}}\in G_{x}$ using binary search.

3: Use Shank’s Baby-Step Giant-Step algorithm for the group $\langle
x^{\prime}\rangle\subseteq G_{x}$ to compute
$m^{\prime}\in\\{0,1,\ldots,L_{x}-1\\}$ such that
${(x^{\prime})}^{m^{\prime}}={y}^{\prime}$.

4: Find the maximum number $c\geq 0$ such that
$x^{(tL_{x}+1)m^{\prime}-cL_{x}}\in G_{x}$ using binary search.

5: Return $m=m^{\prime}(tL_{x}+1)-(b+c)L_{x}$.

Algorithm 5 Algorithm for Discrete Logarithm

Since authors of [3] do not give an explicit proof of correctness Step 5 in
Algorithm 5, we provide it in Theorem 2. Before this, we will need the
following technical result.

######  Lemma 5.

Let $L_{x}$ be the cycle length of $x\in S$, and $n$, $a$, and $a^{\prime}$ be
fixed positive integers. Suppose that $x^{bL_{x}+n}=x^{a}\in G_{x}$, where $b$
is the minimum number such that $x^{bL_{x}+n}\in G_{x}$, and
$x^{n-cL_{x}}=x^{a^{\prime}}\in G_{x}$, where $c$ the maximum number such that
$x^{n-cL_{x}}\in G_{x}$. Then

$bL_{x}+n\leq a,\ \text{and}\ n-cL_{x}\leq a^{\prime}.$

###### Proof.

First let $x^{bL_{x}+n}=x^{a}$ with $b$ minimal such that $x^{bL_{x}+n}\in
G_{x}$. Suppose, to the contrary, that $bL_{x}+n>a$. We must have, by the
minimality of $b$, $x^{(b-1)L_{x}+n}\not\in G_{x}$, so $(b-1)L_{x}+n<a$.

$\displaystyle\text{But},\;\;\;$ $\displaystyle x^{bL_{x}+n}=x^{a}\in G_{x}$
$\displaystyle\implies$ $\displaystyle bL_{x}+n-a=kL_{x},\ k\geq 1$
$\displaystyle\implies$ $\displaystyle(b-k)L_{x}+n=a$ $\displaystyle\implies$
$\displaystyle x^{(b-k)L_{x}+n}=x^{a}\in G_{x},\ k\geq 1.$

This is a contradiction to the minimality of $b$. So, $bL_{x}+n\leq a$. Now
suppose that $x^{x-cL_{x}}=x^{a}\in G_{x}$, with $c$ maximal, and suppose that
$n-cL_{x}>a^{\prime}$. We argue as above:

$\displaystyle L_{x}\mid n-cL_{x}-a^{\prime}$ $\displaystyle\implies$
$\displaystyle n-(k+c)L_{x}=a^{\prime},\ \text{for some}\ k\geq 1$
$\displaystyle\implies$ $\displaystyle x^{n-(k+c)L_{x}}=x^{a^{\prime}}\in
G_{x},$

which is a contradiction to the maximality of $c$. Thus $n-cL_{x}\leq
a^{\prime}$. ∎

######  Theorem 2.

Let $S$ be a semigroup, $x\in S$ a torsion element and $y\in\langle x\rangle$
any element. Assume the cycle length $L_{x}$ and cycle start $s_{x}$ of $x$
are known. Then Algorithm 5 returns the correct values of the discrete
logarithm $m=\log_{x}(y)$ in $\mathcal{O}\left(\sqrt{L_{x}}+(\log
N_{x})^{2}\right)$ semigroup multiplications, with a required storage of
$\mathcal{O}\left(\sqrt{L_{x}}\right)$ semigroup elements.

###### Proof.

We use the notations of Algorithm 5, and also write $n=\log_{x}y$. We will
show that the output $m$ is equal to the correct discrete logarithm value $n$.
Recall that we have a group $G_{x}$, generated by
${x}^{\prime}:=x^{tL_{x}+1}$, and with identity $x^{tL_{x}}$. The parameter
$t$ is given by the formula $t=\left\lceil\frac{s_{x}}{L_{x}}\right\rceil$.
Inverses in $G_{x}$ can be computed in polynomial time using the formula (1).
Note that membership in $G_{x}$ can be tested with one equality check: $y\in
G_{x}\iff y\cdot x^{L_{x}}=y$. There are now two cases:

  1. 1.

When $y\in G_{x}$, we have $b=0$. Here, it is possible to use Shank’s Baby
Step-Giant Step algorithm [18] which is a deterministic algorithm and which
requires $\mathcal{O}\left(\sqrt{L_{x}}\right)$ semigroup multiplications and
storage space $\mathcal{O}\left(\sqrt{L_{x}}\right)$, in order to compute
$\log_{{x}^{\prime}}(y)$. This is done in Step (3). From this value,
$n=\log_{x}(y)$ is readily computed, as shown below. Note that in this case,
$\log_{x}(y)$ is determined modulo $L_{x}$.

  2. 2.

When $y\not\in G_{x}$, Algorithm 5 first computes, using binary search, the
smallest power $b$ of $x^{L_{x}}$ such that the product $y\cdot x^{bL_{x}}$
lies in the group $G_{x}$, and then proceeds as in case 1 via the Baby Step-
Giant Step algorithm to find the discrete logarithm $m^{\prime}$ of $y\cdot
x^{bL_{x}}$ with base $x^{\prime}$ (i.e. ${(x^{\prime})}^{m^{\prime}}=y\cdot
x^{bL_{x}}$). Note that in this case, the value of $\log_{x}(y)$ is less than
$s_{x}$, and is thus determined uniquely in $\mathbb{N}$. Again, the time and
space complexity are both $\mathcal{O}\left(\sqrt{L_{x}}\right)$.

In both cases above, we have the maximal value $c$ such that
$x^{m^{\prime}(tL_{x}+1)-cL_{x}}\in G_{x}$, and so $c\leq
L_{x}+s_{x}+1=N_{x}+1$, since $m^{\prime}\leq L_{x}$ and $tL_{x}\leq
L_{x}+s_{x}$. We also clearly have $b\leq t\leq N_{x}$. Since the computations
of both $b$ and $c$ are done via binary searches, they contribute
$\mathcal{O}((\log N_{x})^{2})$ steps to the overall time complexity. Now,

$x^{m^{\prime}(tL_{x}+1)-cL_{x}}=x^{m^{\prime}(tL_{x}+1)}=(x^{\prime})^{m^{\prime}}=x^{bL_{x}+n}.$

Applying Lemma 5 to the above equation, we must have

$m^{\prime}(tL_{x}+1)-cL_{x}\leq bL_{x}+n,\ \text{and}\ bL_{x}+n\leq
m^{\prime}(tL_{x}+1)-cL_{x}.$

Therefore, $bL_{x}+n=m^{\prime}(tL_{x}+1)-cL_{x}$, or
$n=m^{\prime}(tL_{x}+1)-(b+c)L_{x},$ which is precisely equal to $m$, the
value returned by the Algorithm 5. Thus, $m=n$. This completes the proof. ∎

Combining Theorem 1, Lemma 3 and Theorem 2 we arrive at the main proposition
of the paper:

######  Proposition 1.

Let $S$ be a semigroup, $x\in S$ a torsion element and $y\in\langle x\rangle$
any element. The discrete logarithm $m=\log_{x}(y)$ can be computed
deterministically in

$\mathcal{O}\left(\sqrt{N_{x}}\cdot(\log N_{x})^{2}\ \right)$

steps, with a required storage of $\mathcal{O}\left(\sqrt{N_{x}}\right)$
semigroup elements.

###### Proof.

For the solution, one begins by finding $L_{x}$. This can be done using
Algorithm 4 and according to Theorem 1 this requires
$\mathcal{O}\left(\sqrt{N_{x}}\cdot(\log N_{x})^{2}\right)$ steps and the
storage of $\mathcal{O}\left(\sqrt{N_{x}}\right)$ elements.

By Lemma 3 the computation of the cycle start $s_{x}$ is achieved in
$\mathcal{O}((\log N_{x})^{2})$ semigroup multiplications, which does not
contribute to the overall cost of the algorithm.

By Theorem 2, the discrete logarithm $m$ can then be retrieved using Algorithm
5, in $\mathcal{O}\left((\log N_{x})^{2}+\sqrt{L_{x}}\right)$ steps, with a
required storage of $\mathcal{O}\left(\sqrt{L_{x}}\right)$ semigroup elements.

As $L_{x}\leq N_{x}$, the overall complexity is dominated by the computation
of the cycle length, and the proof of the result is now clear. ∎

###  4.3 Solving the DLP once the Factorization of the Cycle Length is known

We mentioned in the introduction that for a general group of order $N$ the
best general known algorithms for solving the discrete logarithm problem have
complexity $\mathcal{O}(\sqrt{N})$ operations.

In case the order $N$ has a prime factorization into small primes there is the
famous Pohlig–Hellman algorithm [15] for solving the DLP whose complexity is
dominated by the largest prime factor in the integer factorization of $N$.

In case that we have available the integer factorization of the cycle length
$L_{x}$ we can adapt the Pohlig–Hellman algorithm for groups to a
Pohlig–Hellman algorithm for solving the DLP in a semigroup. Algorithm 6
represents this adapted Pohlig–Hellman algorithm.

Input A semigroup $S$, a torsion element $x\in S$, with cycle length
$L_{x}=\prod_{i=1}^{r}p_{i}^{e_{i}}$ and cycle start $s_{x}$, and $y\in S$
with $y=x^{m}$

Output The discrete logarithm $m$ of $y$ with base $x$

1: Compute $t=\left\lceil\frac{s_{x}}{L_{x}}\right\rceil$ and define
$x^{\prime}=x^{tL_{x}+1}\in G_{x}$.

2: Find the minimum number $0\leq b\leq t$ such that $y^{\prime}=y\cdot
x^{bL_{x}}\in G_{x}$ using binary search.

3: for $i\in\\{1,\ldots,r\\}$

  1. 1.

Compute the values $x_{i}^{\prime}=(x^{\prime})^{L_{x}/p_{i}^{e_{i}}}$,
$y_{i}^{\prime}=(y^{\prime})^{L_{x}/p_{i}^{e_{i}}}$, and
$\gamma_{i}:=(x_{i}^{\prime})^{p^{e_{i}-1}}$.

  2. 2.

Calculate the inverse $z_{i}$ of ${x_{i}}^{\prime}$ in $G_{x}$ using (1).

  3. 3.

Set $k\leftarrow 0$ and $n_{0}\leftarrow 0$.

  4. 4.

while $k<e_{i}$ do

    1. (a)

Compute
${y_{k}^{\prime}}=(y_{i}^{\prime}z_{i}^{n_{k}})^{p^{e_{i}-1-k}}\in\langle\gamma_{i}\rangle$.

    2. (b)

Use Shank’s Baby-Step Giant-Step algorithm for the group
$\langle\gamma_{i}\rangle\subseteq G_{x}$ to compute
$d_{k}\in\\{0,1,\ldots,p_{i}-1\\}$

such that ${\gamma_{i}}^{d_{k}}={y_{k}}^{\prime}$.

    3. (c)

Set $n_{k+1}\leftarrow n_{k}+p_{i}^{k}d_{k}$, and $k\leftarrow k+1$.

  5. 5.

end while

  6. 6.

Set $m_{i}:=n_{e_{i}}$.

4: end for

5: Use the Chinese Remainder Theorem to solve the congruence equations
${\displaystyle m^{\prime}\equiv m_{i}{\pmod{p_{i}^{e_{i}}},}\quad\forall\
i\in\\{1,\dots,r\\}}$ uniquely for $m^{\prime}\mod L_{x}$. This gives the
discrete logarithm of $y^{\prime}$ with respect to the base $x^{\prime}$ in
the group $G_{x}$.

6: Find the maximum number $c\geq 0$ such that
$x^{(tL_{x}+1)m^{\prime}-cL_{x}}\in G_{x}$ using binary search.

7: Return $m=m^{\prime}(tL_{x}+1)-(b+c)L_{x}$.

Algorithm 6 Pohlig–Hellman Algorithm for solving the Discrete Logarithm
Problem in a Semigroup

######  Theorem 3.

Let $S$ be a semigroup, $x\in S$ a torsion element and $y\in\langle x\rangle$
any element. Assume the cycle start $s_{x}$ of $x$ is known and assume the
integer factorization of the cycle length $L_{x}$ is known to be
$L_{x}=\prod_{i=1}^{r}p_{i}^{e_{i}}$. Then Algorithm 6 computes the discrete
logarithm $\log_{x}y$ requiring
$\mathcal{O}\left(\sum\limits_{i=1}^{r}e_{i}\left(\log
L_{x}+\sqrt{p_{i}}\right)+\left(\log N_{x}\right)^{2}\right)$ steps. The space
complexity of the algorithm consists in
$\mathcal{O}\left(\sum\limits_{i=1}^{r}e_{i}\sqrt{p_{i}}\right)$ semigroup
elements.

###### Proof.

Steps 1 and 2 are in analogy to the corresponding steps of Algorithm 5. Steps
3 to 5 represent the Pohlig–Hellman algorithm for groups with the implied
complexity dominated by the largest prime factor $p_{i}$ of the integer
factorization of $L_{x}$ (for a reference on Pohlig–Hellman in groups, see in
[9, Theorem 2.32]). It follows that the running time of the algorithm is
$\mathcal{O}\left(\sum\limits_{i=1}^{r}e_{i}\left(\log
L_{x}+\sqrt{p_{i}}\right)\right)$ steps. The computation of $b$ and $c$
require in addition $\left(\log N_{x}\right)^{2}$ steps. The total space
complexity is $\mathcal{O}\left(\sum\limits_{i=1}^{r}e_{i}\sqrt{p_{i}}\right)$
semigroup elements and that completes the proof. ∎

##  5 Conclusion

The DLP in a finite group has noteworthy significance for cryptography, and so
an extension of existing solutions to other algebraic structures like
semigroups, where inverses may not be available, is of natural interest. In
particular, the DLP in a semigroup has been discussed before in two places,
namely [3] and [14]. Both these authors provide probabilistic generalizations
of existing collision-based methods for the case of a semigroup. The time
complexity of the algorithm in [3] is $\mathcal{O}(\sqrt{N_{x}}(\log
N_{x})^{2}\log\log N_{x})$, and the one in [14] is
$\mathcal{O}(\sqrt{N_{x}}(\log N_{x})^{2})$. Both these methods rely on
computing a multiple of the cycle length and then taking gcd’s or factors, and
could fail with a small probability that depends on the parameters chosen. In
this paper, we provided a deterministic solution of the semigroup DLP, which
computes the cycle length directly and does not rely on finding a factor of
it. The time complexity of our algorithm is $\mathcal{O}(\sqrt{N_{x}}(\log
N_{x})^{2})$. We further demonstrated the application of the Pohlig-Hellman
algorithm to semigroups. A direct consequence of our findings is that for
cryptographic purposes, generalizing the type of algebraic structure for the
DLP offers no additional advantage, at least in the torsion case, both in a
classical and a quantum setting.

##  6 Acknowledgement

This research is supported by armasuisse Science and Technology. The second
author is also supported by Swiss National Science Foundation grant n. 188430.

## References

  * [1] L. M. Adleman and J. DeMarrais.  A subexponential algorithm for discrete logarithms over all finite fields.  Math. Comp., 61(203):1–15, 1993.
  * [2] M. Agrawal, N. Kayal, and N. Saxena.  PRIMES is in P.  Ann. of Math. (2), 160(2):781–793, 2004.
  * [3] M. Banin and B. Tsaban.  A reduction of semigroup DLP to classic DLP.  Des. Codes Cryptography, 81(1):75–82, October 2016.
  * [4] A.M. Childs and G. Ivanyos.  Quantum computation of discrete logarithms in semigroups.  Journal of Mathematical Cryptology, 8(4):405 – 416, 01 Dec. 2014\.
  * [5] H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen, and F. Vercauteren, editors.  Handbook of Elliptic and Hyperelliptic Curve Cryptography.  Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2006.
  * [6] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  Introduction to algorithms.  MIT press, 2009.
  * [7] W. Diffie and M. E. Hellman.  New directions in cryptography.  IEEE Trans. Inform. Theory, IT-22(6):644–654, 1976.
  * [8] N. Goel, I. Gupta, and B. K. Dass.  Survey on SAP and its application in public-key cryptography.  J. Math. Cryptol., 14(1):144–152, 2020.
  * [9] Jeffrey Hoffstein, Jill Pipher, Joseph H Silverman, and Joseph H Silverman.  An introduction to mathematical cryptography, volume 1.  Springer, 2008.
  * [10] D. Kahrobaei, C. Koupparis, and V. Shpilrain.  Public key exchange using matrices over group rings.  Groups Complex. Cryptol., 5(1):97–115, 2013.
  * [11] G. Maze, C. Monico, and J. Rosenthal.  Public key cryptography based on semigroup actions.  Adv. in Math. of Communications, 1(4):489–507, 2007.
  * [12] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone.  Handbook of applied cryptography.  CRC Press Series on Discrete Mathematics and its Applications. CRC Press, Boca Raton, FL, 1997.
  * [13] G. L. Miller.  Riemann’s hypothesis and tests for primality.  J. Comput. System Sci., 13(3):300–317, 1976.
  * [14] C. Monico.  Semirings and semigroup actions in public-key cryptography.  PhD thesis, University of Notre Dame Notre Dame, 2002.
  * [15] S. Pohlig and M. Hellman.  An improved algorithm for computing logarithms over GF(p) and its cryptographic significance (corresp.).  IEEE Transactions on information Theory, 24(1):106–110, 1978.
  * [16] J. M. Pollard.  Monte Carlo methods for index computation.  Mathematics of computation, 32(143):918–924, 1978.
  * [17] M. O. Rabin.  Probabilistic algorithm for testing primality.  J. Number Theory, 12(1):128–138, 1980.
  * [18] D. Shanks.  Class number, a theory of factorization, and genera.  In Proc. of Symp. Math. Soc., 1971, volume 20, pages 41–440, 1971\.
  * [19] Andrew V. Sutherland.  Order computations in generic groups.  2007\.
  * [20] J. Zumbrägel.  Classification of finite congruence-simple semirings with zero.  Journal of Algebra and Its Applications, 07(03):363–377, 2008.