Find $11^{644} \mod 645$ Can someone just explain to me the basic process of what is going on here? I understand everything until we start adding 1's then after that it all goes to hell. I just need some guidance. The Problem with the solution is attached. 
Thanks in advance..
Find $11^{644} \mod 645$

 A: Note that $645=3\cdot 5\cdot 43$. Then 
$$11^{644}\equiv (-1)^{2\cdot 322}\equiv 1^{322}\equiv 1\pmod 3$$
$$11^{644}\equiv 1^{644}\equiv 1\pmod 5$$
For the last modulus, we should determine the order of $11\pmod{43}$. To this end we first try $11^q$ for $q\mid p-1$:
$$11^2\equiv 35\equiv -8, 11^3\equiv -8\cdot 11\equiv -2, 11^7\equiv (-8)^2\cdot(-2)\equiv -128\equiv 1.$$
So with this 
$$11^{644}\equiv 11^{7\cdot 46}\equiv 1^{46}\equiv 1\pmod{43} $$
and so by the Chinese Remainder Theorem also $11^{644}\equiv 1\pmod {645}$
A: The rather intimidating notation used in the textbook is effectively just finding the binary representation of 644.
$644 = 512+128+4 = 1010000100_{2}$
It does this by extracting factors of two and noting when the result is odd, corresponding to successive digits (from the right) of the binary number above.
so putting this knowledge into the require exponent,
$\begin{align} \\
x^{644} &= x^{512}\cdot x^{128} \cdot x^4 \\
&=  x^{4\times 32 \times 4}\cdot x^{32\times 4} \cdot x^4\\
&= ((x^4\cdot x)^{32}\cdot x)^4\\
\end{align}$
Once all the powers can be represented as powers of two, the bulk of the exponentiation can be undertaken by squaring, and of course taking the numbers modulo 645 can be done at each step. Your book example works by calculating the three values for $11^n \bmod 645$ on the top row, but also this process may be undertaken effectively using the decomposition on the third row to accumulate the final value:
Starting with $x$, we square twice, multiply by $x$ again, square $5$ times, multiply by $x$ again, and square twice more.
This is equivalent to stepping through the binary representation above and squaring at each step, then also multiplying by $x$ if the digit is a $1$.
Your sample problem solution looks like, 
$$\begin{array}{c|c|c|c}
\text{step} & \text{power} & 11^n \bmod 645 & \text{accumulate} \\ \hline
0 & 1 & 11 &   \\
1 & 2 & 121 &   \\
2 & 4 & \fbox{451} & \to 451  \\
3 & 8 & 226 &  \\
4 & 16 & 121 &  \\
5 & 32 & 451  &   \\
6 & 64 & 226  &   \\
7 & 128 & \fbox{121} & \to 391  \\
8 & 256 & 451 &   \\
9 & 512 & \fbox{226} & \to 1   \\
\end{array}$$
and the binary-digit-driven version looks like:
$$\begin{array}{c|c|c|c}
\text{step} & \text{binary digit} &  \text{action} & \text{value} \\ \hline
0 & 1 &               & 11    \\
1 & 0 & \text{square} & 121   \\
2 & 1 & \text{sq+mult} & 446  \\
3 & 0 & \text{square} & 256  \\
4 & 0 & \text{square} & 391  \\
5 & 0 & \text{square} & 16    \\
6 & 0 & \text{square} & 256    \\
7 & 1 & \text{sq+mult} & 431  \\
8 & 0 & \text{square} & 1    \\
9 & 0 & \text{square} & 1   \\
\end{array}$$
