# Computing $a^e \mod p^n$ Efficiently

It is well known that we can compute: $$a^e \mod m$$ in $O(\log e \log ^2 m)$ bit operations (assuming multiplication $nm$ in $O(\log n \log m)$ time) via exponentiation by squaring. I am wondering if there is a way to compute: $$a^e \mod p^n$$ for some prime $p$, in time better than $O(\log e\ n^2 \log ^2 p)$, given by the above method. Such a technique could be combined with the chinese remainder theorem to obtain an efficient algorithm to compute $a^e \mod m$ when the prime factorization of $m$ is known.

• Yes, you can just use a better multiplication algorithm to get $\tilde O(\log e\, n\log p)$ [second n] (which works for arbitrary n [first n] even without factoring). You can't realistically expect to get rid of the $n$ [second $n$] factor, as even the length of output scales that way. – Emil Jeřábek Mar 11 '16 at 23:02
• And yes, denoting two main parameters in the question by the same letter, which moreover conventionally denotes something else entirely, is a terrible idea. – Emil Jeřábek Mar 11 '16 at 23:08
• Oops. Good point, I changed the first $n$ to $m$. – Bryce Sandlund Mar 12 '16 at 17:29