Discrete logarithm has no "efficient solution" in general. For example finding `y = x**n mod m` (i.e. in the set of integers modulo `m`) is hard, but finding the discrete logarithm in the set of integers is easy.
Isuru On Thu, Jan 11, 2018 at 4:35 PM, Chris Smith <smi...@gmail.com> wrote: > I was inspired to dig a little deeper into the issue raised in PR #13844, > finding the exponent of integer `x` in `y`, More specifically, finding > whether `y` is exactly `x**n`. I read here > <https://en.wikipedia.org/wiki/Discrete_logarithm> that this problem has > "no efficient solution". But I must be missing something, because if (in > SymPy) we write `integer_log = lambda y, x: multiplicity(x, y)` that runs > as the square of the number of digits of y. Although multiplicity doesn't > exactly give what we are looking for it is not hard to modify it so it does > (and it runs in `O(d**2)` where d is the number of digits)...am I > misunderstanding something about the complexity measure or the nature of > the problem? > > /c > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sympy+unsubscr...@googlegroups.com. > To post to this group, send email to sympy@googlegroups.com. > Visit this group at https://groups.google.com/group/sympy. > To view this discussion on the web visit https://groups.google.com/d/ > msgid/sympy/21b9003c-0baf-4295-ac3a-114be0b849d4%40googlegroups.com > <https://groups.google.com/d/msgid/sympy/21b9003c-0baf-4295-ac3a-114be0b849d4%40googlegroups.com?utm_medium=email&utm_source=footer> > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscr...@googlegroups.com. To post to this group, send email to sympy@googlegroups.com. Visit this group at https://groups.google.com/group/sympy. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CA%2B01voMsS4yvEOVivQzq8kB2Qm2rD-KKP1tT9XFefuWNzOA%2BrQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
