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

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;

- Shank's Baby-Step Giant-Step method with $\mathcal{O}(\sqrt{n}\log n)$-time and $\mathcal{O}(\sqrt{n})$-space.
- Pollard's $\rho$ method with $\mathcal{O}(\sqrt{n})$-time is improved version of Shank's method.
- Pollard's $\lambda$ method (wild and tame kangoroos)
- Adleman's index calculus with $\mathcal{O}(\exp(c \sqrt{\log n \log\log n}))$
- Gordon's NFS algorithm with $\mathcal{O}(\exp(c(\log n)^{1/3}(\log\log(n)^{2/3})$-time

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

External links referenced by this document:

- https://crypto.stackexchange.com/q/8301/18298
- https://dmgordon.org/papers/crypto_dlog.pdf
- https://en.wikipedia.org/wiki/Baby-step_giant-step
- https://en.wikipedia.org/wiki/Discrete_logarithm#Powers_of_10
- https://en.wikipedia.org/wiki/Discrete_logarithm_records#Elliptic_curves
- https://en.wikipedia.org/wiki/Elliptic-curve_cryptography
- https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
- https://en.wikipedia.org/wiki/Index_calculus_algorithm
- https://en.wikipedia.org/wiki/Pohligâ€“Hellman_algorithm
- https://en.wikipedia.org/wiki/Pollard's_kangaroo_algorithm
- https://en.wikipedia.org/wiki/Pollard's_rho_algorithm_for_logarithms
- https://en.wikipedia.org/wiki/Smooth_integer
- https://www.shoup.net/papers/dlbounds1.pdf