RSA encryption without a calculator 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
 A: 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.
A: Alternative to the other answers you could use CRT.
By Fermat's little theorem:
$18^{17} \equiv 3^{17} \equiv 3 \bmod 5$
Also:
$18^{17} \equiv 7^{17} \equiv 7^7 \equiv 6 \bmod 11$
And so the unique solution mod $55$ is $28 \bmod 55$.
A: Observe that $2^6=64\equiv9\pmod{55}$
$\displaystyle\implies 18^{17}=2^{17}\cdot 9^{17}\equiv 2^{17}\cdot(2^6)^{17}\pmod{55}\equiv2^{17+6\cdot17}=2^{119}$
Now as $\displaystyle\phi(55)=40\implies 2^{40}\equiv1\pmod{55}$ (Using Euler's Totient Theorem)
$\displaystyle\implies 2^{120}\equiv1\pmod{55}$ 
or
using Carmichael function,
as  $\displaystyle\lambda(55)=20\implies 2^{20}\equiv1\pmod{55} \implies 2^{120}\equiv1\pmod{55}$
$\displaystyle\implies 2^{119}\equiv 2^{-1} \pmod{55}$
Now as $\displaystyle2\cdot 28=56\equiv1\pmod {55}\implies 2^{-1}\equiv28\pmod{55}$
