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⁵⁹ mod 391 which has to be done in stages because calculators and computers will not handle big numbers like 180⁵⁹.

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⁵⁹ mod 391 you have to find a sensible way to break down 180⁵⁹ 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⁵⁹ = 180 ×180² ×180⁸ × 180¹⁶ ×180³². This is very useful because in the sequence 180, 180², 180⁴, 180⁸, 180¹⁶, 180³² each term is the square of the previous term.

You also need to appreciate that in modular arithmetic: ab mod c = [a mod c]×[b mod 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 mod 391 1802 =1802 = 338 mod 391 1804 = (1802)2 = 3382 = 72 mod 391 1808 = (1804)2 = 722 = 101 mod 391 18016 = (1808)2 = 1012 = 35 mod 391 18032 = (18016)2 = 352 = 52 mod 391 .

Now we can express 180⁵⁹ mod 391 as 52×35 × 101 ×338 ×180 mod 391. This can be done easily using normal modular multiplication:

18059 = 52 ×35 ×101 ×338 ×180 mod 391 = 256 ×101 ×338 ×180 mod 391 = 50×338 ×180 mod 391 = 87 ×180 mod 391 = 20 mod 391.

So now we have the final answer: 180⁵⁹ = 20 mod 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⁵⁹ as a product and working out the factors separately.

18059=18056×1803 = (18014)4×1803.

Working modulo 391 this becomes

18059 = (110)4 ×235 = 50 ×235 = 20 mod 391.

Program to calculate powers in modulus arithmetic