digital logarithm

[Chris Smith]

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 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

[Isuru Fernando]

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 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+unsubscribe@googlegroups.com.
To post to this group, send email to sy...@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.
For more options, visit https://groups.google.com/d/optout.