Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer 1

up vote 1 down vote accepted

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.