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?
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$.
No comments:
Post a Comment