11
$\begingroup$

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?

$\endgroup$
  • 13
    $\begingroup$ Traditional logarithm: answer is a real or complex number. Discrete logarithm: answer is an element of a finite set $\mathbb{Z}_n$. $\endgroup$ – Mikero Apr 15 at 20:18
  • 6
    $\begingroup$ See also discrete mathematics $\endgroup$ – BlueRaja - Danny Pflughoeft Apr 15 at 22:48
  • $\begingroup$ That's a pretty discreet information. $\endgroup$ – yo' Apr 17 at 10:26
25
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ yes, being discrete is not the "core reason" why dlp can be hard - although note that if we are to ever use the crypto we build on a computer, things better be discrete - at best, we can only approximate a continuous primitive in a discrete way. $\endgroup$ – Geoffroy Couteau Apr 15 at 20:51
  • 8
    $\begingroup$ @JohnGalt The hard part of the DLP is the modular reduction "hiding" how many times you've "wrapped around". Without modular reduction, you can do some sort of "binary search" to get accurate lower/upper bounds to the discrete log rather efficiently. $\endgroup$ – Mark Apr 15 at 20:51
  • 2
    $\begingroup$ @GeoffroyCouteau This isn't precisely true. Any computable number has a finite-length turing machine that, on input $n$, will output the $n$th digit of the number. This can be viewed as a finite-length representation of the number. As an example, there are formula for $\pi$ (such as the BBP formula) that compute the $i$th digit without computing all smaller digits. This is definitely a different notion of "representation" than simply storing the literal value in memory, but the computable numbers are notably not discrete (they contain $\mathbb{Q}$ as a sub-field). $\endgroup$ – Mark Apr 15 at 21:04
  • 3
    $\begingroup$ @Mark you are perfectly right, although for the purpose of getting a high level intuition regarding this specific question (regarding discrete log), I felt like my answer would provide one. We could perhaps work with problems over more general structures through appropriate representations, though I believe this has never been done in Cryptography. $\endgroup$ – Geoffroy Couteau Apr 15 at 21:08
  • 2
    $\begingroup$ @JohnGalt: To add a bit to Mark and GeoffroyCouteau's comments . . . in principle, if we had a computer that could store arbitrary real numbers and perform infinite-precision math on them, then we could do the equivalent of modular reduction by (for example) just dropping the integer part and taking the fractional part. (If all you knew was that n is an integer in [0, N) and the fractional part of eⁿ was 0.1254123452312..., it would be very hard to find n.) So you can see that the discreteness really isn't what makes the discrete logarithm hard to compute. $\endgroup$ – ruakh Apr 16 at 0:01
12
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ A nice feature of this example is that because S1 can readily support an operator that raises values to a fractional power, one can define log functions in terms of that. Because for most pairs of (x,z) there would generally be many exponent values such that x to the power y would yield z, there are many possible functions which use different ways to select which power y gets used. A continuous-log function might select a y in S1, while a discrete-log function would select the smallest y in Z. $\endgroup$ – supercat Apr 16 at 15:32
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is "Knowing when you are close to a solution is very useful information." related to knowing when the value of something is greater than the value of another? That is, in a binary search algorithm used to calculate a log from an exponentiated power, it is critical to know the upper and lower limits of the target power on each test. Each iteration gets you closer and closer to the solution until the solution is reached. If you can't determine whether the test is greater than (or less than) the target, the search doesn't work. $\endgroup$ – JohnGalt Apr 17 at 15:34
  • 1
    $\begingroup$ @JohnGalt They are closely related (because the standard topology on R is the order topology) but they are not the same thing. Order definitely plays a role here, but continuity can be used to solve equations even when there isn't a clear order (C does not have an order topology). Certainly the bisection method for finding a real root of a continuous function has the same basic logic as a binary search. $\endgroup$ – John Coleman Apr 17 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.