6
$\begingroup$

I've already read this question about the difference between discrete and non discrete logarithms. But I still have problems to clarify my mind about why the Discrete Logarithm Problem is computationally hard while the NON Discrete Logarithm Problem is not, as I read in my Cryptography and Security book.

What are the computation differences? Why can I, for example, easily break a non discrete logarithm cipher but not a discrete one?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
14
$\begingroup$

The main point is that the entire apparatus of calculus applies to exponentiation over the real numbers. For instance, if $a$ and $b$ are close, then $g^a$ and $g^b$ are close as well. The exponential function and its inverse are nice, so you can use infinite series for your computation, and some partial sum will be close enough to the correct answer. Or since exponentiation is monotonic, you can use binary search.

The groups we use for cryptography are usually discrete, and the apparatus of calculus no longer applies. For example, there is no sensible distance measure that relates the distance between $a$ and $b$ and the distance between $g^a$ and $g^b$. And this means things end up being more difficult.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ "exponentiation is monotonous" -- and monotonic ;-) $\endgroup$
    – Steve Jessop
    Sep 12, 2016 at 1:43
  • 4
    $\begingroup$ FTR, continuity is very much not sufficient to guarantee that you can use finite sums as stand-ins for infinite series and get an approximate result. In fact exponentiation is an analytic function, which is a vastly stronger property. (Even so, that only guarantees that for some number of terms you get a good approximation, not that any particular partial sum will have anything to do with the correct result.) $\endgroup$
    – leftaroundabout
    Sep 12, 2016 at 9:52
4
$\begingroup$

Like I wrote in the comment, the simple answer is that the normal logarithm "problem" is not hard, because we know how to compute logarithms quickly. And discrete logarithm problem is hard in some groups because we do not know hot to compute them quickly.

One reason normal logarithms are easy to compute is that the exponentiation function is monotonic. E.g. for all $x>y$ and $b > 1$, $b^x>b^y$. This allows you to easily home in on the logarithm (e.g. using a Taylor series).

However, discrete logarithms can be computed in some groups, so that is just one reason a logarithm can be easy.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Nit-pick: "For all $x>y$ and positive $b$, $b^x>b^y$." This is wrong, consider $b=1/2$, if $x>y$ (say 2 and 1), then $(1/2)^2<(1/2)^1$. So the proper formulation would be "For all $x>y$ and $b>1$, $b^x>b^y$." $\endgroup$
    – SEJPM
    Sep 11, 2016 at 18:21
  • 1
    $\begingroup$ "discrete logarithm modulo a product of known primes is" only known to be easy when it's easy mod those primes. ​ (You might be thinking of discrete roots.) ​ ​ ​ ​ $\endgroup$
    – user991
    Sep 11, 2016 at 20:56
1
$\begingroup$

why the discrete logarithm is hard and normal isn't

Normal logarithm over the integers isn't hard because we have efficient algorithms for computing it. In this case we want to compute $X$, given $b$ and $Y$ such that $b^X=Y$ (where all values are integers). There exist polynomial time algorithms for computing that $X$ (sublinear algorithms in fact. The reals are a different story, but I don't want to muddy the waters too much.

We say that discrete logarithm is hard because a lot of really smart people have tried to come up with polynomial time algorithms for it and have failed. They have failed at least in finding a polynomial time algorithm for general discrete logarithms. For specific instances, there are in fact polynomial time algorithms.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Actually, we don't have an algorithm for computing normal logs. What we have are efficient algorithms for computing an approximation of the log (and we're working in a field $\mathbb{R}$ were "approximation" makes sense) $\endgroup$
    – poncho
    Jan 5, 2018 at 20:53
  • $\begingroup$ @poncho, good point. I didn't want to muddy the waters too much. I edited to restrict my answer on normal logs to the integers. $\endgroup$
    – mikeazo
    Jan 5, 2018 at 21:02
  • 2
    $\begingroup$ @poncho We do have an algorithm for computing normal logs on computable reals. (Computable reals are basically defined by an approximation algorithm.) $\endgroup$
    – Gilles 'SO- stop being evil'
    Jan 5, 2018 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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