1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – fretty Oct 21 '13 at 7:12
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ have you used any special method to calculate $7^7\pmod{11}?$ $\endgroup$ – lab bhattacharjee Oct 22 '13 at 18:41
  • $\begingroup$ 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$... $\endgroup$ – fretty Oct 23 '13 at 7:55
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @user2101517, how about this? $\endgroup$ – lab bhattacharjee Oct 21 '13 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.