[Math] RSA encryption without a calculator

Question

I'm doing an RSA encryption and to get part of the solution I need to solve

$$C=18^{17} \pmod{55}$$

How would I solve this problem without a calculator

Thanks in advance

Answer 1

Let's use successive squaring:

\begin{align*} 18^2 = 324 \equiv 49 &\equiv -6 \pmod{55} \\ 18^4 \equiv (-6)^2 &\equiv 36 \pmod{55} \\ 18^8 \equiv 36^2 \equiv 1296 &\equiv 31 \pmod{55} \\ 18^{16} \equiv 31^2 \equiv 961 &\equiv 26 \pmod{55} \end{align*}

Now we have

$$18^{17} = 18^{16 + 1} = 18^{16} \cdot 18 \equiv 26 \cdot 18 \equiv 28 \pmod{55}$$

This approach never necessitates using numbers larger than $55^2 = 3025$, and can be done by hand easily. In fact, by allowing negative results in our computations, we can only deal with numbers between about $-30$ and $30$, which is even easier.