2
$\begingroup$

Why discrete logarithm? Is discrete logarithm is part of logarithm?

I do not understand the difference between these two concepts.

$\endgroup$

closed as too broad by otus, Gilles, e-sushi Mar 27 '16 at 2:46

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
    $\begingroup$ Reading is often a good starting point...en.m.wikipedia.org/wiki/Discrete_logarithm ...this does not help? $\endgroup$ – DrLecter Mar 24 '16 at 5:48
  • $\begingroup$ Please explain exactly what you do not understand. This is not the right place to completely describe the discrete logarithm problem. $\endgroup$ – Maarten Bodewes Mar 24 '16 at 10:03
10
$\begingroup$

I will assume you understand modulo operation and the exponentiation.


First let's consider logarithm in $\mathbb{R}$.

You know that if we have $e^x = y$ then $x = \ln y$. The Napierian logarithm return values in $\mathbb{R}$.
You can have the same thing with another base. For example : $2^3 = 8$ and $\log_2 8 = 3$.

The simplified idea of the discrete logarithm is to return only the Integers ($\mathbb{Z}$).

In $\mathbb{R}$, we have $\log_2 5 = 2.321\ldots$. This is not interesting for us. Hard to manipulate... How does this translate into a Integer ?


Lets consider consider the integers where all numbers have to be below a certain prime number $p = 11$.
Lets also consider the only allowed operation is the multiplication : $\times$.

Therefore we have :
$3 \times 4 = 12 \equiv 1 \pmod{11}$
And so on.

This kind of structure is called a group of multiplication modulo the prime p. Its notation is the following $\mathbb{Z}_p^\times$. In this case we have $\mathbb{Z}_{11}^\times$

Let's consider $g=2$ and apply the exponent ($g^n = g \times \ldots \times g$) :
$2^0 \equiv 1$
$2^1 \equiv 2$
$2^2 \equiv 4$
$2^3 \equiv 8$
$2^4 \equiv 2\times 2^3 \equiv 2 \times 8 \equiv 16 \equiv 5 \pmod{11}$
$2^5 \equiv 2\times 2^4 \equiv 10 \pmod{11}$
$2^6 \equiv 2\times 2^5 \equiv 9 \pmod{11}$
$2^7 \equiv 2\times 2^6 \equiv 7 \pmod{11}$
$2^8 \equiv 2\times 2^7 \equiv 3 \pmod{11}$
$2^9 \equiv 2\times 2^8 \equiv 6 \pmod{11}$
$2^{10} \equiv 1 \pmod{11}$

This is called a cyclic group of generator $g$ (here 2) : after a certain number of exponentiations, we have loop.

Now let's move back to our question : $\log_2 5 = ?$
In $\mathbb{Z}_{11}^\times$ as we have $2^4 \equiv 5 \pmod{11}$, therefore in $\mathbb{Z}_{11}^\times$, $\log_2 5 = 4$.

The discrete in discrete logarithm refer to the aspect that we are working in a discrete group and not any real numbers.

$\endgroup$
  • 2
    $\begingroup$ Discrete does not refer to the fact that the exponent is an integer, it refers to a discrete group. $\endgroup$ – Aleph Mar 24 '16 at 11:01
  • 2
    $\begingroup$ Yes but the discrete group implies the later, hence why I think it is easier to remember that way (even though not completely correct) if one does not have a strong mathematical background. $\endgroup$ – Biv Mar 24 '16 at 12:24
  • $\begingroup$ It is perfect Answer for me. Thanks Biv. Im Studying ECC for make ECC SW Library in Soc Company I Saw Discrete Logarithm Theory but theyre just say equation. Your Answer is very good. I think Discrete Logarithm is adapted for Digital. $\endgroup$ – pftpmlp Mar 24 '16 at 12:52
  • $\begingroup$ @Biv Sure, but I wouldn't say the converse holds. I would never refer to the logarithm of $b^k$ to base $b$ ($b \in \mathbb R, k \in \mathbb Z)$ as discrete. That said, it was a minor detail and the answer is nice overall. $\endgroup$ – Aleph Mar 24 '16 at 17:59

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