As the title says, I want to know if there's a fast way to compute $m^n (mod\,p^2)$ for some large prime $p$.
Obviously, I can compute $pp = p^2$ and then just use an exponentiation algorithm to compute $m^n (mod\,pp)$, but I'm wondering if there's a better way.
I've read up on Hensel Lifting, which says that for a solution $r$ of a polynomial $f(x) = 0 (mod\,p)$ there exists a solution $s$ of $f(x) = 0(mod\,p^2)$ and $s$ can be constructed as $s = r - f(r) * (f'(r))^{-1} (mod\,p^2)$.
I've tried applying this for $f(x) = m^n - x$. I can easily compute a solution $r$ for this ($r = m^n (mod\,p)$, but then if I try to apply Hensel lifting, I after applying the derivative and the modular inverse, I get $s = r + f(r) (mod\,p^2)$, which comes down to $s = m^n(mod\,p^2)$, which is not helpful.
Any answers would be appreciated.
Thank you in advance.
Presumably $(m,p) = 1$ and $n < p(p-1)$ (otherwise reduce $n$ mod $\varphi(p^2) = p(p-1)$). Then the standard repeated-squaring trick does is in at most $\log_2(n) < 2 \log_2(p)$ squarings and multiplications, all mod $p^2$.