The Discrete Log Problem

Nikita communicates with Michael by encrypting everything using their agreed upon secret key. In order to understand the conversation, the eavesdropper needs $s$ , but it takes a long time to compute $s$ given only $p$ , $g$ , $g^n$ , and $g^m$ . One way would be to compute $n$ from knowledge of $g$ and $g^n$ ; this is possible, but appears to be ``computationally infeasible'', in the sense that it would take too long to be practical.

Let $a$ , $b$ , and $n$ be real numbers with $a,b>0$ and $n\geq 0$ . Recall that the ``log to the base $b$ '' function characterized by

$$\log_b(a) = n$$    if and only if $$a=b^n.$$

We use the $\log_b$ function in algebra to solve the following problem: Given a base $b$ and a power $a$ of $b$ , find an exponent $n$ such that

$$a=b^n.$$

That is, given $a=b^n$ and $b$ , find $n$ .

SAGE Example 3.1   The number $a = 19683$ is the $n$ th power of $b=3$ for some $n$ . With a SAGE we quickly find that

$$n = \log_3(19683) = \log(19683) / \log(3) = 9.$$

sage: log(19683.0)
9.88751059801299
sage: log(3.0)
1.09861228866811
sage: log(19683.0) / log(3.0)
9.00000000000000

SAGE can quickly compute a numerical approximation for $\log(x)$ , for any $x$ , by computing a partial sum of an appropriate rapidly-converging infinite series (at least for $x$ in a certain range).

The discrete log problem is the analogue of computing $\log_b(a)$ but where both $b$ and $a$ are elements of a finite group.

Problem 3.1 (Discrete Log Problem)   Let $G$ be a finite group, e.g., $G=(\mathbb{Z}/p\mathbb{Z}{})^*$ . Given $b\in G$ and a power $a$ of $b$ , find a positive integer $n$ such that $b^n=a$ .

As far as we know, finding discrete logarithms in $(\mathbb{Z}/p\mathbb{Z}{})^*$ when $p$ is large is ``very difficult'' in practice. Over the years, many people have been very motivated to try. For example, if Nikita's captors could efficiently solve Problem 3.1.2, then they could read the messages she exchanges with Michael. Unfortunately, we have no formal proof that computing discrete logarithms on a classical computer is difficult. Also, Peter Shor [#!shor!#] showed that if one could build a sufficiently complicated quantum computer, it could solve the discrete logarithm problem in time bounded by a polynomial function of the number of digits of $\char93 G$ .

It is easy to give an inefficient algorithm that solves the discrete log problem. Simply try $b^1$ , $b^2$ , $b^3$ , etc., until we find an exponent $n$ such that $b^n=a$ . For example, suppose $a = 18$ , $b=5$ , and $p=23$ . Working modulo $23$ we have

$$b^1 = 5, b^2 = 2, b^3 = 10, \ldots, b^{12} = 18,$$

so $n=12$ . When $p$ is large, computing the discrete log this way soon becomes impractical, because increasing the number of digits of the modulus makes the computation take vastly longer.

SAGE Example 3.1   Perhaps part of the reason that computing discrete logarithms is difficult, is that the logarithm in the real numbers is continuous, but the (minimum) logarithm of a number mod $n$ bounces around at random. We illustrate this exotic behavior in Figure 3.2.

This draws the continuous plot.

sage.: show(plot(log, 0.1,10, rgbcolor=(0,0,1)))

This draws the discrete plot.

sage: p = 53
sage: R = Integers(p)
sage: a = R.multiplicative_generator()
sage: v = [(a^n, n) for n in range(p-1)]
sage: v.sort()
sage: G = plot(point(v,pointsize=50,rgbcolor=(0,0,1)))
sage: H = plot(line(v,rgbcolor=(0.5,0.5,0.5)))
sage.: show(G + H)

Figure 3.2: Graphs of the continuous log and of the discrete log modulo $53$ .Which looks easier to compute?