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.