What is discrete logarithm?

Solution 1:

It's hard to know, judging by the question alone, how much knowledge you already have on the standard Logarithm over the real numbers. To give you a very quick overview, consider a couple of examples:

$${2^2 = 4}$$

$${3^2=9}$$

$${4^3 = 64}$$

All of these are very simple statements. Two multiplied with itself gives four, three multiplied with itself gives nine, four multiplied by four multiplied by four gives sixty four... etc. We can reverse this question, however. The equivalent "reverse" questions would be

$${\log_{2}(4)= ?}$$

$${\log_{3}(9)= ?}$$

$${\log_{4}(64)= ?}$$

The first one, for example, says "what number do I raise $2$ to to get the number $4$? Of course we know the number is ${2}$, and so ${\log_{2}(4)=2}$.

But Mathematicians don't always raise things to integer numbers! Oh no. Why stop there? For example we have

$${2^{0.5}=\sqrt{2}\approx 1.41....}$$

I won't go into exactly how this is done, but we extend the notion of exponents in a special way that preserves properties. I actually made a large post on how we do this extension - see: Generalization of the root of a number .

Now, we call this Logarithm over standard real numbers like this continuous - without getting into the proper definition of continuity, the way you can think of it is that if we were to plot a graph of the Logarithm as a function - it has no horrible jumps and gaps. Another way you can think of it, is that if you take a small step to the left or right in the input space - the output of the Logarithm will also exhibit a very small change. For example, ${\log_{2}(2 + 0.0001) \approx \log_{2}(2)}$ (you can verify this with a calculator).

Okay, now this is where the discrete comes in: the discrete Logarithm is essentially just the Logarithm over a finite group. I'll explain what that means below;

A group in Mathematics is just a set of objects that have a sort of "multiplication operation" associated with them - for example, the real numbers (technically without $0$) form a group under standard multiplication. And since there are infinitely many real numbers - we call this an infinite group.

With a finite group, since multiplication is still defined - so is exponentiation. We can still say for example

$${a\cdot a = a^2}$$

Or

$${a\cdot a\cdot a = a^3}$$

Where ${\cdot}$ represents some group multiplication operation (not the same multiplication you are used to with real numbers necessarily!) and ${a}$ is just some object out of this group. The discrete Logarithm is just reversing this question, just like we did with real numbers - but this time, with objects that aren't necessarily numbers. For example, if ${a\cdot a = a^2 = b}$, then we can say for example ${\log_{a}(b)=2}$.

The "discrete" simply refers to the fact we have finite objects, that can only take on certain fixed values. I described continuity earlier as having no "jumps or gaps" - clearly, if you have a finite number of objects - in some sense, there will be jumps and gaps. It is constrained and confined to a certain number of finite values from our group.