# Computing $m^n (mod\,p^2)$ efficiently for a large prime $p$

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.

• Are you sure you wrote what you meant? Assuming $n$ is a positive integer, $m^n \equiv 0 \mod p^2$ iff either $n = 1$ and $m \equiv 0 \mod p^2$ or $n > 1$ and $m \equiv 0 \mod p$. – Robert Israel Apr 6 '17 at 19:56
• You're right, the $=0$ was left there by accident. I edited my question. – Nu Nunu Apr 6 '17 at 20:23
• Can you make use of pre-computation for a certain $p$ (after which many instances of $m^n \bmod p^2$ become efficient)? – orlp Apr 6 '17 at 21:03
• I am only interested in computing one instance, but one can assume I have computed $m ^ n (mod p)$ if that is relevant. – Nu Nunu Apr 6 '17 at 21:36
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$.