#### You may also like ### Purr-fection

What is the smallest perfect square that ends with the four digits 9009? ### Old Nuts

In turn 4 people throw away three nuts from a pile and hide a quarter of the remainder finally leaving a multiple of 4 nuts. How many nuts were at the start? ### Mod 7

Find the remainder when 3^{2001} is divided by 7.

# The Public Key

##### Age 16 to 18 Challenge Level:
The idea of Public Key Cryptography is to send messages in such a way that only the person who receives the messages can understand them. Even if everyone knows the method of encryption nobody except the receiver has all the information needed in order to decypher the message. To solve this problem you are in the position of Bob receiving a secret number from Alice who has sent him the coded message 180. Bob is the only person in the world who knows that he has to use 59 in order to find the secret number $M$ which Alice has sent to him, and which he knows to be between 0 and 390.

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.