<p>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.</p>

CC BY-SA 3.0
2016-03-11T23:02:55.497Z
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
CC BY-SA 3.0
2016-03-11T23:08:34.730Z
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
CC BY-SA 3.0
2016-03-12T17:29:54.943Z
Oops. Good point, I changed the first $n$ to $m$.
Bryce Sandlund
<cc.complexity-theory><ds.algorithms><time-complexity><algebra>
Computing $a^e \mod p^n$ Efficiently
Bryce Sandlund
# Computing $a^e \mod p^n$ Efficiently

(Asked by: username_0 on 2016-03-11)

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.

**Tags:** cc.complexity-theory, ds.algorithms, time-complexity, algebra

> **Comments:**
> **username_1**: 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.  
> **username_1**: And yes, denoting two main parameters in the question by the same letter, which moreover conventionally denotes something else entirely, is a terrible idea.  
> **username_0**: Oops. Good point, I changed the first $n$ to $m$.  

---

## 0 answers

