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 [email protected]. To post to this group, send email to [email protected]. 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.
