# 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

• Don't be scared to get your hands dirty, sometimes you simply have to work stuff out by hand! There isn't always a nice theorem that tells you the answer... – fretty Oct 21 '13 at 7:12

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.

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

• have you used any special method to calculate $7^7\pmod{11}?$ – lab bhattacharjee Oct 22 '13 at 18:41
• Should I have? There are many ways to do it. You can either work it out and then reduce or reduce in steps. For example it is $7\times (7^2)^3 \equiv 7\times 5^3 \equiv 35\times 25 \equiv 2\times 3 \equiv 6 \bmod 11$. Alternatively $7$ is not a QR mod $11$ and so we know by Euler's criterion that $7^5 \equiv -1 \bmod 11$ hence $7^7 \equiv -7^2 \equiv -49 \equiv 6 \bmod 11$... – fretty Oct 23 '13 at 7:55

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