How to solve RSA without calculator?

Question

I'm trying to create a ciphertext, and I need to solve this congruence: $$ C = 20^{23} \bmod 377. $$ How would I be able to simplify this so that I can do it without a calculator? Since there won't be any calculators allowed in the exam. Thanks!

Answer 1

I'm not sure that you necessarily can (nor should you expect to be able to) do something like this without machinery, even in your relatively very small modulus. You could try standard tricks like Euler's theorem to speed up the work, but that doesn't really help here as far as I can see. (Euler would say that $20^{336} \equiv 1 \bmod 377$ but that doesn't help here.)

I really don't think this is realistic without a machine. If you're desperate, a better tactic would be the method of successive squares. Write the exponent as a sum of powers of $2$, as $$ 23 = 16 + 4 + 2 + 1 = 2^0 + 2^1 + 2^2 + 2^4. $$ At this point I like the commented hint from @TrostAft, which is to break it up as $10^{23} \cdot 2^{23} \bmod 377$. I'll show how to handle the $2^{23}$ term by successive squares: the $10^{23}$ bit is even easier.

First compute all terms $2^{2^k}$ for $k=0, 1, 2, 3, 4$. The trick is to note that the next term is simply the square of the previous, so this generates the list of successive squares quickly. This is clear since $$ \left(b^{2^k} \right)^2=b^{2^{k+1}} $$ for any base $b$. Doing this, we get \begin{array}{|c|c|c|c|c|c|}\hline k & 0 & 1 & 2 & 3 & 4\\\hline 2^{2^k} & 2 & 4 & 16 & 256 & 315\\\hline \end{array}

Here, only the last entry takes any work, and it's made easier by writing $256=-121$ and then squaring.

Finally, the result of $2^{23} \bmod 377$ is given by the product of the terms corresponding to $k=0, 1, 2, 4$, exactly the $k$s needed to express $23$: $$ 2^{23} = 2 \cdot 4 \cdot 16 \cdot 315 = 358. $$

You can do the same thing base $10$ and get $10^{23} = 69$. Hence the final verdict is $$ 20^{23} = 358 \cdot 69 = 197 \bmod 377. $$ You could make the last bit easier by instead doing $$ 20^{23} = 358 \cdot 69 = -19 \cdot 69 = 197 \bmod 377 $$ just to keep the numbers smaller.

But again, notice what a headache this is without a machine. For exponents below $16$, this isn't a horrible way to go. The more powers of $2$ involved in your exponent, the worse this gets (by hand). This is a very nice trick for programming a machine to compute large powers, though.