Cryptography
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)

## Solution

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;

and

• 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$$.