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

Question

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)

Answer 1

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 is brute-forcing the 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

  • Pohlig–Hellman 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$.