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.

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

Your Answer

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

Browse other questions tagged or ask your own question.