What is the significance of using the term "discrete" in discrete logarithm?

Question

I'm trying to clear up my confusion in using the term "discrete" in discrete logarithm. I'm focusing on why the word "discrete" is used to differentiate it from a logarithm.

Wikipedia defines a discrete logarithm as follows:

in any group $G$, powers $b^k$ can be defined for all integers $k$, and the discrete logarithm $log_b a$ is an integer $k$ such that $b^k = a$.

Is the term discrete added simply to reflect the fact that $k$ in $log_ba=k$ is confined to integers? Or is it a combination of the discrete log being an integer as well as the powers fulfilling the properties of a group $G$?

I would guess it arose in the following manner: say $a \in {\mathbb N}$ is a generator of $({\mathbb Z}/p)^*$, and $b \in \mathbb N$ prime to $p$. If one wants to find the exponent $k$ such that $ b = a^k$, but wants the previous equality to hold $\pmod p$, one might feel inclined to say 'discrete' to distinguish the logarithm from the usual one... — peter a g, Aug 22 '19 at 16:13
@peterag Not being sarcastic here (just my mathematical naïveté), when you say ∈ℕ is a generator of (ℤ/)∗ do you mean that $a$ as a base (mod p) is capable of generating order equal to |p-1|? I'm not sure what the "prime to p" means in ∈ℕ prime to ? — JohnGalt, Aug 22 '19 at 16:24
Rereading your question in your comment to me, I think I wasn't clear - so to rephrase 1), yes : I am taking $a$ so that the set $${a^j\pmod p \mid j \in {\mathbb N}}$$ has size $p-1$. But really, I was taking your main question as a linguistic one, so take my 'I would guess' comment-answer with cups of salt. There are also, btw,discrete fourier transforms... — peter a g, Aug 22 '19 at 16:51

score 1 · Answer 1 · answered Sep 28 '19 at 12:16

From Google, the definition of discrete is:

individually separate and distinct.

In the math sense, this means only taking on a specific set of values. In modular arithmetic these are the integers. This applies to the exponents, as much as it applies to the remainders. Also though the normal log can help in some sense, it doesn't wrap around like a discrete log. About the only way in which the normal log gives us an answer to the discrete log is if we take the fractional part as a fraction defined properly in mod $\varphi(p)$ math. And even then it's not guaranteed correct.

theREALyumdub · Answer 2 · 2019-08-22T16:04:17.553

0

I'm not sure I understand your dichotomy, but because the generating set in question is discrete, the logarithm is called a discrete logarithm. Here discrete is used to distinguish the logarithm from a continuous logarithm, which would be a logarithm in the real numbers or a similarly continuous set.

This need not happen in a finite group, as long as the group is discrete itself. In a general group, one composes an element with itself a set number of times to achieve a value $k$ (usually by binary exponentiation). When this process is reversed, the values that can be taken by the powers $b^k$ in the set generated by $b$ are discretized, since you can only have integer powers of $b$ in a black box group.

The reason discrete is mentioned is to separate the problem from a similar problem in a continuous case with a continuous set. I we supposed a "continuous logarithm problem" existed it could easily be solved computationally, since one can simply compute the log of both sides of the equation, which I think boils down to Newton's method. Anyways it's fair to say a computer can estimate it quite accurately without trouble.

edited Aug 22 '19 at 16:04

answered Aug 22 '19 at 15:23

theREALyumdub

1,016

When you say, "the set in question is discrete", what properties make the elements in that set "discrete"? – JohnGalt Aug 22 '19 at 15:27
What gets more confusing is when you add the "discrete log problem" to the definition of a discrete log...this seems to imply that "discrete-ness" <--- my word is somehow related to the discrete log problem. Is it? For example, an implementation of the discrete log problem over $Z_n$ (e.g. using a modulus) removes the relationship of the "less than" operator but that's different than the "discrete-ness" of a discrete logarithm...right? – JohnGalt Aug 22 '19 at 15:31
@JohnGalt I've edited the answer to try and respond to your point, clarifying that I meant the set generated by $b$. I tried to stay informal since I couldn't tell your background. But in your example of $ \mathbb{Z}_n , the group itself is discrete (as opposed to say addition on the reals) – theREALyumdub Aug 22 '19 at 16:08

What is the significance of using the term "discrete" in discrete logarithm?

2 Answers2