0
$\begingroup$

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.

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

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.