I'm working on a problem where I have an equation such as
$y = x ^ d \pmod M$
where $M$ is a product of unique primes; each prime is denoted by $M_i$, where $i$ is less than an integer $l$.
In the above equation, I am trying to solve for $y$. I know $x$ and $M$ (and all $M_i$ values that make up $M$). I do not know $d$, but I know all values of $d_i$, where $d_i = d \pmod {M_i - 1}$. Furthermore, $d = e^{-1} \pmod {\phi(M)}$, and $e$ is an integer such that $\gcd(\phi(M), e) = 1$ and $e < \phi(M)$. The method I need to follow is:
- Calculate $(y_i) = x^{d_i} \pmod{ M_i}$, where I know all $d_i$ and $M_i$.
- Once I have all $y_i$ values for how many ever primes there are (number of $M_i$'s), I need to use the Chinese Remainder Theorem to 'combine' all $y_i$ values to achieve $y$.
I'm unsure of how to go about doing this. I can find $y_i$ values, which I have already done. What do I need to do to combine them?
Thank you for any tips.