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.

Answer 2

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}$

Answer 3

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$.