# How to simpify the way of calculating $(a^b \bmod c) \bmod d$?

Right now I know the way to calculate $a^b \bmod c$ which is in the answer of the following question.

Consider the case where $c$ is much larger than $d$. So, the result of $a^b \bmod c$ will be large compared with the final result.

Is there any way to get the final result without getting directly the result of $a^b \bmod c$ which is large?

• I don't think so. By definition $(a^b \mod c) = a^b - k \cdot c$ for some $k \in \mathbb{Z}$, and in general $(a^b - k_1 \cdot c) \not\equiv (a^b - k_2 \cdot c) \mod d$ for $k_1 \neq k_2$ (unless there is some hidden relation between $c$ and $d$). So before you continue with the $\mod d$-step, you need to find the right $k$ (or the right value $a^b - k \cdot c$). – TMM Apr 7 '12 at 21:34

## 1 Answer

There is no known solution to this problem. If there were, it would be in use all over the world in implementations of the RSA algorithm for smart cards.

If $d$ and $c$ have a factor in common, then you can use this to speed up the computation -- and in fact this is routinely done in smart cards when the RSA private key is known. But otherwise, you just have to compute $a^b \mod c$ and reduce the result modulo $d$.