# The Public Key

## Problem

Bob has to find the number equivalent to $180^{59}\pmod {391}$ so can you do this for him?

NOTES AND BACKGROUND

So that you can decipher the secret number using only a calculator the example given involves only small numbers like 59 and 391 whereas very big numbers are involved when the method is used in the real world. Instead of 391, the product of two very large prime numbers would be used in real world applications of this method. The reason that Bob, and nobody else, knows to use the number 59 to decode the message is that it is derived from one of the factors of 391 and in real world applications it is impossible to find the factors of the very large numbers that are used.

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

This wikipedia page might also be of interest http://en.wikipedia.org/wiki/Cobalt-59

## Getting Started

## Student Solutions

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