Introduction

We consider the following instance of the so-called discrete logarithm problem:

Let $G$ be a finite cyclic group generated by $\alpha$ with order $N$. Let $\beta\in G$. Find $x\in\mathbb{Z}_N$ (notation: $\log_\alpha\beta$) such that $\alpha^x = \beta$.

Let us first recall that:

• $G=\{\alpha^0, \alpha^1,\dots, \alpha^{N-1}\}$
• $\alpha^m = \alpha^{m\bmod N}$ for every $m\in\mathbb{Z}$

Therefore, one naive way to compute $\log_\alpha\beta$ is to multiply $\alpha$ by itself as many times as needed to obtain $\beta$.

# The naive algorithm implemented in SageMath
def dlog_naive(a,b):
  (n,x)=(0,1)
  while not x == b:
      n+=1
      x*=a
  return a

Example. Consider the group $\mathbb{Z}_{251}^*$ whilst generated by $6$. Let us determine

$$n=\log_6 184\quad\text{i.e.}\quad\text{$n$ such that }6^n\equiv 184\pmod {251}$$

According to the naive algorithm, we test the hypothesis

$$n=0, n=1, \dots, n=249$$

sequentially until $6^n\equiv 184\pmod{251}$. Such will happen by the 229^th iteration, meaning that

$$n = \log_6 184 = 229\quad\text{i.e.}\quad 6^{229}\equiv 184\pmod{251}$$

Albeit straightforward to implement, this algorithm has the clear disadvantage of having time complexity $\mathcal{O}(N)$, which makes it inviable for sufficiently large group orders.

# Example above encoded in SageMath using the naive algorithm
Z=Zmod(251)
a=Z(6)          # or Z.multiplicative_generator()
b=Z(184)
dlog_naive(a,b) # = 229

Silver-Pohlig-Hellman

The algorithm we present next (due to. R. Silver, S. Pohlig and M. Hellman) is reminiscent of the saying divide and conquer, in that it divides the discrete logarithm problem over a group into the discrete logarithm problem of its subgroups.

Let $G$ be a finite cyclic group with order $N$ generated by $\alpha$, and let $\beta\in G$. Let $l = \log_\alpha\beta$ and recall that $l$ is determined modulo $N$. We wish to determine $l$.

Suppose that $$\begin{equation} N = \prod^{k}_{i=1} p_i^{e_i} \end{equation}$$ is the prime factorization of $N$. Then, by the Chinese Remainder Theorem (CRT) it is enough to determine $x_i$ $(1\leq i \leq k)$ in $$\begin{equation} \label{eq:congs} \begin{cases} l\equiv x_1\pmod{p_1^{e_1}}\\ l\equiv x_2\pmod{p_2^{e_2}}\\ \vdots\\ l\equiv x_k\pmod{p_k^{e_k}} \end{cases} \end{equation}$$ in order to determine $l$ modulo $N$.

We now have the concern of finding $x_i$ in $l\equiv x_1\pmod{p_i^{e_i}}$ for each $i$. Let us simplify the explanation by choosing some $i$ $(1\leq i\leq k)$ and then defining $$\begin{equation} \label{eq:xxi} p := p_i,\quad e:=e_i,\quad x:=x_i. \end{equation}$$

By definition, $l\equiv x\pmod{p^e}$ means $l = x+sp^e$ for some $s\in\mathbb{Z}$. We are going to find $x$ by finding its base-$p$ digits one at a time. The base-$p$ expansion of $x$ is $$\begin{equation} \label{eq:baseexp} x = (d_{e-1}\dots d_1d_0)_p = \sum_{i=0}^{e-1}d_ip^i \end{equation}$$ where $d_i\in\{0,\dots,p-1\}$.

Regarding $d_0$, we start by observing the following auxiliary result $$\begin{align*} &\frac{N}{p}\cdot l\\ =\qquad&\frac{N}{p}\cdot(x+sp^e)\\ =\qquad&\frac{N}{p}\cdot(d_0+d_1p+\dots+d_{e-1}p^{e-1}+sp^e)\\ =\qquad&\frac{N}{p}\cdot(d_0+Kp)\quad\text{for some $K\in\mathbb{Z}$}\\ =\qquad&\frac{N}{p}\cdot d_0+NK\quad\text{for some $K\in\mathbb{Z}$} \end{align*}$$ which implies that $$\begin{equation} \label{eq:mod0} \frac{N}{p}\cdot l\equiv \frac{N}{p}\cdot d_0\pmod{N}. \end{equation}$$

Using $\eqref{eq:mod0}$ we may conclude that $$\begin{equation} \beta^{\frac{N}{p}} = (\alpha^l)^{\frac{N}{p}} = (\alpha^\frac{N}{p})^{d_0}. \end{equation}$$

Hence, regarding the (unique) subgroup of $G$ with order $p$, say $G_p$, for which $\alpha^{\frac{N}{p}}$ is a generator, we have $$\begin{equation} d_0 = \log_{\overline{\alpha}}\overline{\beta},\quad\text{where $\overline{\alpha}=\alpha^{\frac{N}{p}}$ and $\overline{\beta}=\beta^{\frac{N}{p}}$}. \end{equation}$$

Hopefully, $p$ is now small enough for us to be able to compute $d_0$ according to the naive algorithm.

Regarding $d_1$ we similarly observe that $$\begin{align*} &\frac{N}{p^2}\cdot(l-d_0)\\ =\qquad&\frac{N}{p^2}\cdot(x-d_0+sp^e)\\ =\qquad&\frac{N}{p^2}\cdot(d_1p+\dots+d_{e-1}p^{e-1}+sp^e)\\ =\qquad&\frac{N}{p}\cdot(d_1+\dots+d_{e-1}p^{e-1}+sp^{e-1})\\ =\qquad&\frac{N}{p}\cdot(d_1+Kp)\quad\text{for some $K\in\mathbb{Z}$}\\ =\qquad&\frac{N}{p}\cdot d_1+NK\quad\text{for some $K\in\mathbb{Z}$}\\ \end{align*}$$ which implies that $$\begin{equation} \label{eq:mod1} \frac{N}{p^2}\cdot(l-d_0)\equiv\frac{N}{p}\cdot d_1\pmod{N}. \end{equation}$$

Using $\eqref{eq:mod1}$ we may conclude that $$\begin{equation} (\alpha^{\frac{N}{p}})^{d_1} = (\alpha^{l-d_0})^{\frac{N}{p^2}} = (\alpha^l\alpha^{-d_0})^{\frac{N}{p^2}} = (\beta\alpha^{-d_0})^\frac{N}{p^2} \end{equation}$$ and therefore $$\begin{equation} d_1 = \log_{\overline{\alpha}}\overline{\beta},\quad\text{where $\overline{\alpha} = \alpha^{\frac{N}{p}}$ and $\overline{\beta} = (\beta\alpha^{-d_0})^{\frac{N}{p^2}}$.} \end{equation}$$

Regarding the general case of the $j$-th digit $(0\leq j\leq e-1)$ we have $$\begin{align*} &\frac{N}{p^{j+1}}\cdot(l-(d_0+d_1p+\dots+d_{j-1}p^{j-1}))\\ =\qquad&\frac{N}{p^{j+1}}\cdot(x-(d_0+d_1p+\dots+d_{j-1}p^{j-1}) + sp^e)\\ =\qquad&\frac{N}{p^{j+1}}\cdot(d_jp^j+\dots+d_{e-1}p^{e-1}+sp^e)\\ =\qquad&\frac{N}{p^{j+1}}\cdot(d_jp^j+Kp^{j+1})\quad\text{for some $K\in\mathbb{Z}$}\\ =\qquad&\frac{N}{p^{j+1}}\cdot d_jp^j+NK\quad\text{for some $K\in\mathbb{Z}$}\\ \end{align*}$$ which implies that $$\begin{equation} \label{eq:modj} \frac{N}{p^{j+1}}\cdot(l-(d_0+d_1p+\dots+d_{j-1}p^{j-1}))\equiv\frac{N}{p}\cdot d_j\pmod{N}. \end{equation}$$

Using $\eqref{eq:modj}$ we may conclude that $$\begin{equation} (\alpha^\frac{N}{p})^{d_j} = (\alpha^{l-\sum_{i=0}^{j-1}d_ip^i})^{\frac{N}{p^{j+1}}} = (\alpha^l\alpha^{-\sum_{i=0}^{j-1}d_ip^i})^{\frac{N}{p^{j+1}}} = (\beta\alpha^{-\sum_{i=0}^{j-1}d_ip^i})^{\frac{N}{p^{j+1}}} \end{equation}$$ and, hence, $$\begin{equation} d_j = \log_{\overline{\alpha}}\overline{\beta},\quad\text{where $\overline{\alpha}=\alpha^{\frac{N}{p}}$ and $\overline{\beta}=(\beta\alpha^{-\sum_{i=0}^{j-1}d_ip^i})^\frac{N}{p^{j+1}}$} \end{equation}$$

Once we have found all $d_i$ from $\eqref{eq:baseexp}$, we have found $x$ from $\eqref{eq:xxi}$. We repeat this process until we find all $x_i$ from $\eqref{eq:congs}$. Then, all that is left is to apply the Chinese Remainder Theorem and obtain the desired result, $l$.

Implementation

For implementation purposes, it is useful to observe the following recurrence relation regarding $\overline{\beta}$. Let $\overline{\beta}_j\,(0\le j\le e-1)$ be the variable $\overline{\beta}$ when finding the $j$-th digit. Define

$$\begin{align} \beta_0 &:= \beta\\ \beta_{j+1} &:=\beta_j\alpha^{-d_jp^j} \end{align}$$

Then, $$\begin{equation} \overline{\beta}_j = (\beta_j)^{\frac{N}{p^{j+1}}}. \end{equation}$$

# The Silver-Pohlig-Hellman algorithm implemented in SageMath
def dlog_sph(a,b):
    N=a.multiplicative_order()
    P=factor(N)
    k=len(P)
    (xi,pe)=([],[])
    for i in xrange(0,k):
        (p,e)=P[i]
        d=[]
        a_=a^(N/p)
        bj=b
        for j in xrange(0,e):
            b_=(bj)^(N/(p^(j+1)))
            d.append(dlog_naive(a_,b_))
            bj=bj*a^(-d[j]*p^j)
        xi.append(ZZ(d,p))
        pe.append(p^e)
    return CRT_list(xi,pe)

Conclusion

The Silver-Pohlig-Hellman algorithm splits an instance of the discrete logarithm problem into many smaller instances which are hopefully amenable to be solved according to the naive algorithm—or any other algorithm for that matter, e.g. Shanks’ “baby-step giant-step”. This makes it a viable algorithm if the order of the group at hand is factorizable into small enough integers. With that in mind, it should be used together with a specialised factorization algorithm for finding small factors, like ρ-Pollard.

References

• Handbook of Applied Cryptography (Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone; CRC Press, 1996). Chapters 2 and 3.

• The Pohlig-Hellman Algorithm (D. R. Stinson; 2010). http://anh.cs.luc.edu/331/notes/PohligHellmanp_k2p.pdf

• An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance (S. Pohlig, M. Hellman; 1978, IEEE Transactions on Information Theory (24): 106-110)