How can I use eulers totient and the chinese remainder theorem for modular exponentiation? I'm trying to implement modular exponentiation in Java using Lagrange and the Chinese remainder theorem. 

The example we've been given is:


  Let $N = 55 = 5 · 11$ and suppose we want to compute $27^{37} \pmod N$. 


He doesn't give us the answer, but says:


  The most efficient way to do it is is using Lagrange's theorem, a few multiplications modulo 5 and 11 and CRT to combine both results.


Using Lagrange / Euler totient I get $\varphi(N) = 40$, which it seems I'm supposed to use calculate the congruences needed for putting into the Chinese remainder theorem.

I know I can calculate the congruences using the Extended Euclidean algorithm, but the answers need to be reduced or the run time will still be unfeasible (maybe not in this case, but for the 1024 bit numbers I'm working with, this is a huge problem).

I know they can be reduced, from a document I found while researching this,  which states:


  $$a^k \equiv a ^ { k \pmod{\varphi(n)}} \pmod n.$$


I've tried and tried and tried to follow how he does the reduction but I just don't get it. He also doesn't mention what $m$ is when he says $k = m · \varphi(n) + k'$.

As you can probably gather, my math is not so hot, so if possible maybe give a "for dummies" answer. 

The example given – Let $N = 55 = 5 · 11$ and suppose we want to compute $27^{37} \pmod N$ – is not homework, so if anyone could step me through it, in particular the reductions to get to the simplified Chinese remainder theorem congruences, I would be VERY grateful. 

I originally placed this question on Stack Overflow.
To step through it simply:

Step 1: we first compute compute $M^e \bmod p$ (where $p$ is one of the factors of the modulus.  By Fermat's Little Theorem, this is the same as $M^{e \mod p-1} \bmod p$ (and that's where the real savings are), and so in your example ($p=5$), we get:


$M^e \bmod p = 27^{37 \bmod 4} \bmod 5 = 2^1 \bmod 5 = 2$


Step 2: we do the same for the other prime $q$:


$M^e \bmod q = 27^{37 \bmod 10} \bmod 11 = 5^7 \bmod 11 = 3$


Step 3: using the Chinese Remainder theorem, we reconstruct $M^e \bmod pq$ from $M^e \bmod p$ and $M^e \bmod q$:


$C_p = M^e \bmod p = 2$
$C_q = M^e \bmod q = 3$
$M^e \bmod pq = C_q + q \cdot (q^{-1} (C_p - C_q) \bmod p) = 3 + 11 \cdot (1 \cdot (2-3) \bmod 5) = 3 + 11 \cdot 4 = 47$