The first question is do you know the factoring of $m$?

If yes than using Chinese Reminder Theorem it is enough for you to solve it only for $p^k$. For $p^k$ you can use Hensel lifting its comlexity is $O(k\log p polylog(klog p))$ i.e., up to poly-logarithmic factor it is optimal.

If no than your problem is equivalent to factoring.

The first question is do you know the factoring of $m$?

If yes than using Chinese Reminder Theorem it is enough for you to solve it only for $p^k$. For $p^k$ you can use Hensel lifting its comlexity is $O(k\log{p} \mathrm{polylog}(k\log p))$ i.e., up to poly-logarithmic factor it is optimal.

If no than your problem is equivalent to factoring.