diffie-hellman discrete-logarithm modular-arithmetic
Updated Fri, 20 May 2022 02:40:50 GMT

Discrete Logarithm: Given a p, what does it mean to find the discrete logarithm of x to base y?

My understanding is that $a^b \bmod p$ is the discrete logarithm problem. Given the question is worded this way, are we trying to find $ \log_y x \bmod p$.

For instance, if we are trying to compute the discrete logarithm of 3 to base 2 - given that $p=11$, what would be the output (or the equation)


Discrete Log for arbitrary Groups: Discrete Log can be defined in arbitrary groups and some groups can have an easy solution (powers of 10) and some can have a hard solution.

Let $G$ be any group and $\odot$ be the group operation. For any $k \in \mathbb{Z}_{>0}$, let $b \in G$ then we define $[k]b = \overbrace{b\odot\cdots\odot b}^{{k\hbox{ - }times}} $. Then for a given $a \in G$ the $k$ that satisfies $[k]b = a$ is called discrete log of $a$ to base $b$. It can also be written as $k = \log_b a$

  • Additive DLog : The analogous definition for $(\mathbb{Z}_p,+)$ is well-defined with given $a,b,n$ find $x>0$ such that $x a \equiv b \bmod n$. It can be solved easily if you find the inverse of $a$ by using the Ext-GCD algorithm.

  • Multiplicative DLog :, the discrete Logarithm Problem (DLP) is given $a,b,n \in \mathbb{Z}^+$ find $x \in \mathbb{Z}_{>1}$ such that $a^x \equiv b \bmod n$, if such $x$ exists.

For the small modulus we can build a table for the DLP problem, or you can stop building the table whenever you find your case.

The below is a DLog (Discrete Log) table for modulus 19 with base 2.

\begin{array}{c|rrrrrrrrrrrrrrrrr} x& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& \color{red}{13}& 14& 15& 16& 17& 18\\ \hline 2 ^x \bmod 19& 2& 4& 8& 16& 13& 7& 14& 9& 18& 17& 15& 11& \color{red}{3}& 6& 12& 5& 10& 1 \end{array}

For example, given 3 as the DLog base 2 modulo 19, we will look for 3 in the second row and corresponding $x$ in the first row that is 13. I.e. $2^{13} \equiv 3 \bmod 19$

Different bases will produce different tables; for base 5:

\begin{array}{c|rrrrrrrrrrrrrrrrr} x& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17& 18\\ \hline 5 ^x \bmod 19& 5& 6& 11& 17& 9& 7& 16& 4& 1& 5& 6& 11& 17& 9& 7& 16& 4& 1 \end{array} If you know the relation with the two bases then you don't need to calculate another base.

This approach is actually brute-forcing and has $\mathcal{O}(n)$- time complexity.

The brute-forcing approach will fail around when $n \approx 2^{80}$. There are better search algorithms for DLOG, the generic algorithms that work for any group;


  • PohligHellman algorithm that is applicable when the order of the group is smooth. It has $\mathcal O\left(\sum_i {e_i(\log n+\sqrt {p_i})}\right)$-time complexity where $\prod_i p_i^{e_i}$ is the prime factorization of group order $n$. To mitigate this attack this attack a prime order must be selected than is has same worst-case complexity as $\mathcal{O}(\sqrt{n}\log n)$-time.

  • DLog for Elliptic Curves (Additive): DLOG is also defined for Elliptic Curves, in which given a base point $G$ and another point $Q$ find $x$ such that $[x]G = Q$ where $$[x]P = \overbrace{G+\cdots+G}^{{x\hbox{ - }times}}$$

Dlog is not hard for every EC like curves with $|E(\mathbb{F}_q)|=q$. In Elliptic Curve Cryptography, we use curves where the Dlog is hard.

Some of the above generic algorithms, Pollard's $\rho$, Pollard's $\lambda$ also apply for DLog for Elliptic Curves, except index calculus-based algorithms and NFS. The records on finding DLog on EC mostly based on parallel Pollard's $\rho$.