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.

  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Mar 11 '16 at 23:02
  • 1
    $\begingroup$ And yes, denoting two main parameters in the question by the same letter, which moreover conventionally denotes something else entirely, is a terrible idea. $\endgroup$ – Emil Jeřábek Mar 11 '16 at 23:08
  • $\begingroup$ Oops. Good point, I changed the first $n$ to $m$. $\endgroup$ – Bryce Sandlund Mar 12 '16 at 17: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.