The Maths of Codes
In this section I'll explain how to code messages using prime numbers
combined with modulo (clock-face) arithmetic and powers of numbers.
In school we all learn about prime numbers, factors and indices but are rarely shown how they can be useful in real life. The same can be said of clock-face arithmetic. I've chosen coding as an example of how these can all be relevant in the modern world.
Let's start with some simple basics. If you already understand a fair bit about these topics, you can skip the next few paragraphs and go straight to their application in coding messages.
..............................................................................................................................................
Prime Numbers:-
These are numbers which have no other factors except themselves and one. E.g. 2, 3, 5, 7, 11, 13, 17, etc.
(In contrast, a number like 12 isn't a prime number because several smaller numbers, such as 2, 3, 4, and 6 will divide into it an exact number of times.)
The prime numbers above 2 must all be odd numbers, as all even numbers can be divided by 2.
Factors:-
As stated above, 12 is not a prime number. Broken down into its prime factors it can be written as 2 x 2 x 3, or 2² x 3.
The HCF (highest common factor) of two numbers is the largest number which will divide into both of them. For example, the HCF of the numbers 24 and 30 is 6, because 6 is the largest number which goes into both 24 (exactly 4 times) and 30 (exactly 5 times.)
(Method:- 24 has prime factors 2 x 2 x 2 x 3 and 30 has prime factors 2 x 3 x 5; the factors in common are 2 x 3, which make 6.)
Note that 2 x 2 x 2 x 3 is more usually written as 2³ x 3. Powers and indices are dealt with in the next sections.
Powers of a number:-
When you multiply the same number by itself several times, such as in 2 x 2 x 2 x 2, the number 2 is said to be 'raised to power 4' because that's how many 2's are being multiplied. This can be written as 2^4
Similarly, 7 x 7 will be 7 to the power of 2, or 7^2, or7², more usually called '7 squared', and 7 x 7 x 7 would be 7 to power 3, written as 7^3, 7³, or '7 cubed'.
Rule of Indices:-
When you have the same number raised to two different powers and you then multiply them, the powers are added. E.g. 2² x 2³ = 2 to the power 5, because 2 + 3 = 5. Why is this? Well, 2² means 2 x 2 and 2³ means 2 x 2 x 2. If you multiply two 2's together and then multiply the answer by another three 2's that's like multiplying five 2's altogether, hence the power of 5.
If raising a power of a number to another power, you have to multiply the indices. Here's an example to show how it works:-
(2²)³ means 2² x 2² x 2², which is 2 x 2 x 2 x 2 x 2 x 2 if written out fully. There are six 2's being multiplied, so the power of 2 in this case will be 6.
Fractional and negative indices:-
2 ^ ½ means √2 (read as 'the square root of 2', or simply 'root 2') .
This is because 2^ ½ x 2^½ = 2^ (½ + ½), which = 2^1, or just 2.
Similarly, 2^ 1/3 means the cube root of 2, since (2^1/3)³ also = 2^1, or just 2.
Negative powers of a number stand for reciprocals of positive powers of that number i.e. 'one over'.
So a power such as 5^-2 means 1/5², or 1/25.
[You can find more about indices in a previous section, headed 'In the Beginning'.]
Change of Base; Clock-face arithmetic; Modulo arithmetic.:-
The term clock-face arithmetic is a good one to use because we're all familiar with telling the time. The difference here is that we can forget the minute hand and use just the hour hand.
A normal clock face is divided into 12 hours, so if we wanted to show something like 29 hours on it we'd have to go around twice (for 2 x 12 = 24 hours) and then see how much was left over. In this case it would be 5 hours, since 29 - 24 = 5. So 29 hours is equivalent to two complete turns of 12 hours, with 5 hours left over.
In modulo arithmetic we can write this as 29 ≡ 5(mod12). [Note that this special 'equals' sign has THREE lines in it, not two as in a normal = sign].
This is read as "29 is congruent to 5, mod 12".
Similarly, something like 115 hours would show as 7 after subtracting nine rotations of 12. ( 115 - 108 = 7).
So 115 is equivalent to 7 on the clockface, and is written as 115 ≡ 7(mod 12).
[Again, this is read as "115 is congruent to 7, mod 12".]
Multiplication in modulo arithmetic is much easier because we then only have to deal with multiplying the small numbers. E.g. for the numbers 29 and 115 used above, 29 x 115 would give the same answer in mod 12 arithmetic as multiplying their smaller equivalent numbers 5 x 7 .
Let's show this.
29 x 115 = 3335. Dividing by 12 we get 277, with remainder 11. So 29 x 115 ≡ 11 (mod12).
But this same answer could be obtained by just multiplying the 5 x 7 (the numbers equivalent to 29 and 115 in mod12 arithmetic), since 5 x 7 = 35, and this leaves a remainder of 11 when divided by 12. (i.e. 5 x 7
≡ 11, (mod 12))
All the above calculations have been based on mod 12 arithmetic, but the important thing about modulo arithmetic is that it works for any base, not just 12. In everyday life, for example, we work in weeks and days. This is a kind of mod 7 arithmetic. E.g., ignoring the number of full weeks, 38 days would be equivalent to 3 (because 35 days = 5 weeks, leaving 3 days over from the original 38.)
This can also be stated as "38 is congruent to 3, mod 7" , written as 38 ≡ 3(mod 7).
Counting to different bases:-
This is very similar to modulo arithmetic, except that the number of rotations around the clock face is written down as well, not just the number left over (the 'remainder').
E.g. we saw above that 38 is the same as (or congruent to) 3 in arithmetic, mod 7.
The equivalent statement in base 7 would be 38 = 53 in base 7. (N.B. 53 here is read as five-three, showing that 38 is equivalent to 5 sevens plus 3, or 5 complete rotations around the clock-face (which = 35) plus 3 left over).
Another example of this:-
What is 17 in base 3? To do this, we note that 3 goes into 17 five times, with 2 left over (remainder).
So 17 in base 3 will be 52 (read as five-two. not fifty-two, and standing for 5 threes plus 2 left over.).
In our normal base 10 arithmetic (also known as denary), 17 (seventeen) really means 'one ten plus 7 units'.
Similarly, 38 (thirty-eight) in denary stands for 3 tens and 8 units, whereas 38 (three-eight) in, say, base 9 would stand for 3 nines and 8 units, equivalent to 27 + 8 = 35 in denary.
Computers often use the hexadecimal system, which entails counting to base 16. (Why 16? Because its a power of 2. 2 to the power 4, in fact, and computers rely on binary, or two-state, systems because they utilise two-state switches, which can be either on or off.) In the hexadecimal system, a problem arises when we come to numbers between 9 and 16. E.g. ten can't be written 10, as this would mean one sixteen and no units, or just 16. So what we do is use the letter A to represent ten, then B for eleven, C for twelve, etc.
A typical number in hexadecimal (or 'hex') would be 2D7F. What is this in decimal? Well, F means fifteen, the 7 means 7 sixteens, the D means thirteen times two hundred and fifty six (256 being 16 x 16, or 16²), and the 2 in third position to the left stands for 2 x 16³. So we have a grand total of 15 + 112 + 3328 + 8192, or 11,647.
Note - the sections above give only a brief outline of the topics dealt with, as the main purpose of this article is to explain how messages may be encoded. If you need more practice in the basic maths, please refer to a good textbook or online lessons.
............................................................................................................................................................
APPLICATION.
Codes in practice:-
One of the procedures used for encoding messages between governments or military establishments is now explained. Although the prime numbers used in real life are very large, I've added calculations at each stage below which are based on smaller, more manageable, numbers.
The method which follows makes use of something known as Fermat's Little Theorem. This states that if you take any prime number p, any other number such as a, when raised to the power (p-1) in arithmetic mod p, will always end up as 1. (N.B. the power must be one less than the modulus value).
So if we take 4 as the number and 7 as the modulus, when you work out 4 ^ 6 in mod 7 you'll get the answer 1.
To show this, 4 ^ 6 = 4096, Divide this by 7 (the modulus) and you get 585 times, with remainder 1.
i.e. 4 ^ 6 is congruent to 1 (mod7).
Similar results will be obtained for any other values for p and a, provided that p is a prime number.
Now to the method of encoding a message. This method is an example of what is known as public key encryption.
1. Choose 2 very large prime numbers, p and q. (In practice, these can be over 100 digits long, but for the purposesof illustration I'll use 19 and 23)
2. Multiply them to give a new number. Call it N. (19 x 23 = 437)
3. Subtract 1 from each prime number to give two non-prime numbers p-1 and q-1. Multiply these numbers. This gives a new, very large number which will have factors. Call it M. (Here, 18 x 22 = 396)
4. Choose another number, B, which when divided into M or a multiple of M leaves a remainder of exactly 1.[This step needs a bit more explanation. We are really looking for 2 numbers, B and C, such that their product B x C = 1 (mod M).
In our case, we can use 13 for B and 61 for C, because M = 396, and 13 x 61 = 793, which is twice 396, plus 1. So 13 x 61 = 1 in mod396 arithmetic.]
This is the key to the method being used. Any number raised to the power 13(mod437) and sent to someone who then raises this larger number to the power 61(in mod 437) will end up as the original number.
E.g. a number such as 7 can be raised to power 13, and if this larger number is raised to the power 61 that's equivalent to raising 7 to the power of 13 x 61. But 13 x 61 = 1(mod396), by Fermat's Little Theorem.. So 7 to the power of 13 x 61 is equivalent to 7 to the power of 1, which is just 7.
To encode a message, begin by converting the letters to numbers (A = 1, B = 2, etc. would be the simplest, but in practice a much less obvious system would be used), then raise these numbers, or groups of numbers, to the power B (mod N), transmit the encrypted message to the receiver, who then raises the numbers to the power C (mod N) to decipher the original message.
So, coming back to our numerical example, we chose two primes whose product was 437 (= N).
We also found two numbers, 61 and 13, which had a product of exactly 1 when multiplied in mod 396.
Suppose we want to encrypt the number 2 (which could represent the letter B in the message.)
The sender raises 2 to the power 61 ( = 2305843009213693952) and divides by 437. The remainder will be 14. So 2 has been changed into 14 in mod 437 arithmetic. (14 is called the 'cybertext')
14 is sent to the receiver, who then raises it to the power 13 in mod 437 arithmetic, resulting in the number 2 reappearing, so the 'message' has been successfully decoded.
Incidentally, although I've given the full expansion of 2^61 in the working above, it isn't necessary to deal with such huge numbers when doing the calculations as the intermediate stages can be reduced by using mod 437 arithmetic as we proceed. E.g. 2^10 = 1024, which is just 150 in mod 437.
Then 2^20 would be (150)², or 22500, which again can be reduced to 313 ( mod 437), etc.
The numbers 437 and 61 are known as the 'public keys' and can be revealed to anyone, but 396 and 13 are 'private keys'. Without knowing them even the most powerful computers would never be able to break the code. (Remember that the prime numbers used in actual practice are extremely large. Once multiplied together its virtually impossible for any computer to 'undo' the multiplying and find what two numbers were used to begin with.) The method of encryption shown above is referred to as 'asymmetric public-key encryption' using the RSA method, RSA being the initial letters of the names of the three people who invented this method in 1977 and 'asymmetric' referring to the different values, 61 and 13, used by sender and receiver.
Of course, there are many other ways to encode messages. The simplest one is called a 'Caesar' code, in which the letters used in the words of the message are changed by moving them along a few places. For example, if all the letters of the alphabet are moved forwards 3 places, A becomes D, B becomes E, and so on. A word like 'BIKE' would then be encoded as 'ELNH'. (So what happens about letters from the end of the alphabet in this method? Well, think of the letters as being arranged in a circle. Then, after moving letters forward 3 places, W would change into Z, X into A, Y into B and Z into C, so a word like 'YAWN' would become 'BDZQ'.)
As a variation of this method the letters of the alphabet can be given numbers. The most obvious way to do this is to replace A by 1 (or 01), B by 2 (or 02) , C by 3(or 03), etc., (i.e. replacing each letter by its position in the alphabet), so that a word like 'BOOK' would be replaced by 02 15 15 11. But once again this can be improved upon by moving the letters along a few places. If this number of places is 4, so that A is now represented by 05, B by 06, etc., the same word 'BOOK' would be encoded as 06 19 19 15.
A more detailed discussion of codes will be done in a different blog, but for now why not try encoding these rather lengthy, but real, 'fun' words - 'antidisestablishmentarianism' and 'honorificabilitudinarianism', or the name of that place in Anglesey called 'Llanfairpwllgwyngyllgogerychwyrndrobwllllantisiliogogogoch'?!!
Euler's Totient function;-
For any number n, the totient function is defined as the number of integers, starting from 1 and going up to (n-1), which have no factors in common with n. (i.e. are co-prime to n). It is denoted by ø(n) [read as phi(n)]. By convention, the number 1 itself is always included.
Here are a few examples:-
If n = 4, there are just 2 numbers in ø(n), 1 and 3;
If n = 8, .. .. 4 .. .. , 1,3,5, and 7.
If n = 10, .. .. 4 .. .. .. 1,3,7, and 9
If n = 12, .. .. 4 .. .. .. 1,5,7, and 11
But if n = 11 (a prime number) all ten numbers from 1 to 10 will count, as by definition none of them can have any factors in common with a prime number. So ø(n) will be 10 in this case.
In the section on codes above, only prime numbers p were being used, so the totient function will be (p - 1) in every case, and this is what is stated as Fermat's 'Little' theorem where it says a^(p - 1) = 1 (mod p).
