# Compute Modulo exponentiation with prime powers

The problem is to find x such that

$$x = M^d \mod p^2$$, where M and d are large numbers, and p is a large prime. Ideally we only want to compute $M^d\mod p$ and then use the result to further figure out $x$.

I know how it can be done if M^d is small, e.g. using The Lifting Theorem However, in the problem mentioned, we do not want to compute M^d completely. So it is not clear that this theorem is useful.

• Just compute $M^d \bmod{p^2}$; what's the problem? – fkraiem Jun 11 '16 at 5:57
• @fkraiem Computing $M^d \mod p^2$ takes much more time than $M^d \mod p$. – redplum Jun 11 '16 at 14:29