Why was the term "discrete" used in discrete logarithm?

Question

Is there anything especially "discrete" about a discrete logarithm? This is not a question of what is a discrete logarithm or why the discrete logarithm problem is an "intractable problem" given certain circumstances. I'm just trying to determine if there's some additional meaning to the term "discrete" as it's used in name discrete logarithm?

The definition of "discrete" is "individually separate and distinct". Could it be that the term "discrete" is a reference to the least non-negative residues of a modulus or the order of points for a particular cyclic group on an elliptic curve?

Answer 1

The word discrete is used as an antonym of 'continuous', that is, it is the normal logarithmic problem, just over a discrete group.

The standard logarithmic problem is over the infinite group $\mathbb{R}^*$, this group is called 'continuous', because for any element $x$, there are other elements that are arbitrarily close to it.

The discrete logarithmic problem is over a finite group (for example, $\mathbb{Z}_p^*$); in contrast to $\mathbb{R}^*$, we don't have group elements arbitrarily close together; we call this type of group 'discrete'.

Answer 2

While I agree completely with poncho's answer, this other viewpoint might be useful. Specifically, I think a better comparison isn't between $\mathbb{Z}_p^*$ and $\mathbb{R}^*$, but with $\mathbb{Z}_p^*$ and $S^1$. We can view $S^1 \cong \{z\in\mathbb{C} \mid |z| = 1\}$. It's not hard to show that any $z\in S^1$ is able to be written as $z = \exp(2\pi i t)$ for $t\in\mathbb{R}$ (we don't strictly need the factor $2\pi$ here, but it's traditional). Due to $\exp(x)$ being periodic, it's in fact enough to have $t\in[0,1)$.

This has an obvious group structure, in that: $$\exp(2\pi i t_0)\exp(2\pi i t_1) = \exp(2\pi i (t_0+t_1))$$ If we're making the restriction that $t_i\in[0,1)$, then we have to take $t_0+t_1\mod 1$, but this is fairly standard.

More than just having an obvious group structure, we actually have that any $\mathbb{Z}_p^*$ injects into it. Specifically, we always have: $$ \phi_p:\mathbb{Z}_p^*\to S^1,\quad \phi_p(x) = \exp(2\pi i x/(p-1)) $$ Here, $p-1$ in the denominator is because $|\mathbb{Z}_p^*| = p-1$. We can define the discrete logarithm problem for both of these groups in the standard way (here, it's important to restrict $t_i\in[0, 1)$ if we want a unique answer). Then, we can relate these problems to each via the aforementioned injection. Through this image, we see that $S^1$ is "continuous" in the sense that it takes up the full circle, but the image of $\mathbb{Z}_p^*$ in $S^1$ will always be "discrete" --- there will always be "some space" between points (they can't get arbitrarily close).

Answer 3

Just to add to the other answers, (as mentioned in some of the comments) it is exactly the discreteness of the discrete log problem is that makes it (for some parameter choices) hard. Computing $y = \log_{a}(x)$ is the same as solving the equation $a^y = x$ for $y$. In the non-discrete case, $y \mapsto a^y$ is a monotonically increasing (if $a > 1$) continuous function. Thus, you can (in the absence of even more efficient methods) use the bisection method to solve for $y$. When you have a value $y$ for which $a^y$ is close to the target $x$ then you know that $y$ is close to the value you seek. Knowing when you are close to a solution is very useful information.

In the discrete case, there is no corresponding notion of closeness. Say if for some reason you wanted to compute the base-$19$ discrete log of $7155$ (mod $34591$) and somehow find that $19^{481} = 7156$ (mod $34591$). Does this imply that $\log_{19}(7155)$ is close to $481$? Not at all. The actual value is $\log_{19}(7155) = 28544$. It is much harder to find a solution when you can't tell when you are close.