The Public Key

The article 'Public Key Cryptography ' gives a detailed explanation of how the method works and gives you help in working with modulus arithmetic.

This problem simply asks you to work out $180^{59}\pmod {391}$ which has to be done in stages because calculators and computers will not handle big numbers like $180^{59}$.

David of Colyton Grammar School gave the very neat solution you see below and also wrote a program to check the answer and to calculate quickly other high powers in modulus arithmetic. Try out David's program.

In order to calculate $180^{59}\pmod {391}$ you have to find a sensible way to break down $180^{59}$ into pieces which can all be tackled individually. The easiest way of doing this I think is to first write $59$ as a sum of powers of $2$: $59 = 32+16+8+2+1$

Now you know that $180^{59} = 180 \times 180^2 \times 180^8 \times 180^{16} \times 180^{32}.$ This is very useful because in the sequence $180$, $180^2$, $180^4$, $180^8$, $180^{16}$, $180^{32}$ each term is the square of the previous term.

You also need to appreciate that in modular arithmetic: $ab\pmod{c} = [a\pmod {c}]\times [b\pmod {c}].$ This makes the numbers that you are going to have to deal with far more manageable and the problem can be written like this:

$$180 = 180 \pmod {391}$$ $$180^2 =180^2 = 338 \pmod {391}$$ $$180^4 = (180^2)^2 =338^2 = 72 \pmod {391}$$ $$180^8 = (180^4)^2 = 72^2 = 101 \pmod {391}$$ $$180^{16} = (180^8)^2 = 101^2 = 35 \pmod {391}$$ $$180^{32} = (180^{16})^2 = 35^2 = 52 \pmod {391}$$ Now we can express $180^{59} \pmod {391}$ as $52\times 35 \times 101 \times 338 \times 180 \pmod {391}$. This can be done easily using normal modular multiplication: $$180^{59} = 52 \times 35 \times 101 \times 338 \times 180 \pmod {391}$$ $$= 256 \times 101 \times 338 \times 180 \pmod {391}$$ $$= 50\times 338 \times 180 \pmod {391}$$ $$= 87 \times 180 \pmod {391}$$ $$= 20 \pmod {391}.$$ So now we have the final answer: $180^{59}= 20 \pmod {391}$. This method is good because as soon as the modular base is fixed there becomes a ceiling for how large the numbers that we have to compute can be. The largest number that will ever need to be computed is the square of one less than the modular base.

I have also written a console application to check my answer and to quickly calculate any other similar problems. It can do any number and mod with powers up to 255. As it was written in a rush it may still be slightly buggy but seems to work well every time I've tried it ;)

Andrei from Bucharest Romania gave a method which depends on expressing $180^{59}$ as a product and working out the factors separately.

$$180^{59}=180^{56}\times 180^3 = (180^{14})^4\times 180^3.$$ Working modulo 391 this becomes $$180^{59} = (110)^4 \times 235 = 50 \times 235 = 20 \pmod {391}.$$

Program to calculate powers in modulus arithmetic