Chinese Remainder Theorem and RSA Wikipedia has a nice section regarding the speedup of the RSA decryption using the Chinese Remainder Theorem here. I need to understand the implementation of a similar speedup for the encryption algorithm of a more complex homomorphic encryption scheme (DGK) and, for some reason, I'm unable to get my head around the way the Chinese Remainder Theorem is used to achieve this. I don't have a lot of background on modular arithmetic and I would really appreciate it if someone could explain this in more detail.

Edit: Following @mikeazo's comment, I just want to understand the way CRT is applied to speed up the RSA encryption.
Well, the idea behind the CRT optimization is that if we know the factorization of the modulus $N$ (which we may if we have the private key), then we can split up the message $M$ into two halves (one modulo $p$, and one modulo $q$), compute each modulo separately, and then recombine them.  That is, we compute:

$m_1 = (M^d \bmod N) \bmod p = ((M \bmod p)^{d \bmod p-1}) \bmod p$

$m_2 = (M^d \bmod N) \bmod q = ((M \bmod q)^{d \bmod q-1}) \bmod q$

(Note that the exponents are reduced modulo $p-1$ and $q-1$; we can do this because $p$ and $q$ are prime (and Fermat's little theorem); this is the source of a good portion of the speedup).

Then, we recombine them; that is, we find a number $m$ such that:

$m \equiv (M^d \bmod N) \mod p$

$m \equiv (M^d \bmod N) \mod q$

Because of the Chinese Remainder Theorem (and because $p$ and $q$ are relatively prime), we can immediately deduce that:

$m \equiv (M^d \bmod N) \mod pq$

which is exactly what we were trying to compute.

Now, the questions in your comments appear to be asking about the details of this recombination step.

Now, it is actually fairly easy to see the correctness of the algorithm.  To make the last step work, we need to show that we have come up with a value $m$ such that:

$0 \le m &lt; pq$

$m \equiv m_1 \mod p$

$m \equiv m_2 \mod q$

As for the the first criteria $0 \le m &lt; pq$, well, that's straight-forward; we know that $0 \le m_2 \le q-1$, and $0 \le h \le p-1$, and so the smallest that $m$ can be is $0 + (0 * q) = 0$, and the largest it can be is $q - 1 + ((p-1)*q) = pq - 1$

As for the third criteria, that's also straight-forward; $(m_2 + (h * q)) \bmod q = m_2 \bmod q + (h*q) \bmod q = m_2 \bmod q$

The second one is a little tricker: $(m_2 + (h * q)) \bmod p = (m_2 + q * q_{inv} * ( m_1 - m_2) \bmod p) \bmod p = (m_2 + q * q_{inv} * (m_1 - m_2)) \bmod p$

Now, $q_\mathit{inv}$ is defined to be the number that, when multiplied by $q$ modulo $p$, results in 1 (that is, $q * q_\mathit{inv} \equiv 1 \mod p$).  Now, because the above equation is, in fact, computed modulo $p$, we can replace $q * q_\mathit{inv}$ with 1, which gives us:

$m \bmod p = (m_2 + 1 * (m_1 - m_2)) \bmod p = m_1 \bmod p$

QED