All too often pupils get bored with maths lessons because the subject is presented in a way which disregards how it can be used in real life situations.
Admittedly there have been useful advances in this area of teaching over recent years, but still the kinds of problem set for discussion or coursework can be artificial and invented specifically to chime with the syllabus rather than the modern world.
In my opinion, one of the most important qualities we need to inculcate in our schools is enthusiasm for the subject, and this applies whether its maths or another subject.
The very small percentage of our pupils who are mathematically gifted and may well go on to study the subject at University and possibly become noted in their field one day will not have a problem in this respect. They will quickly see the shape and meaning of abstract concepts. I am more concerned with helping the vast majority who find maths strange, difficult, or even dislikeable. Given the correct encouragement I'm sure that many of these could become competent if not brilliant mathematicians.
So how do we do this?
In a nutshell, by two principal strategies:-
1. By harnessing their interest, showing how maths is relevant to some important activity in today's world (e.g. computing; encryption and security; driving a car; finance; barcodes)
2. By encouraging them to master a topic or procedure beyond what the syllabus requires, so that they feel they 're 'good at maths'.
Any teaching scheme incorporating these two elements has to be enormously beneficial to the student.
Tuesday 8 February 2011
Monday 7 February 2011
The Maths of Codes
In this blog I'll explain how to code messages using prime numbers combined with 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 goes into 24 exactly 4 times and into 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 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.
Clock-face arithmetic:-
(Also known as 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 that 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 woud be 5 hours, since 5 + 24 = 29. So 29 ends up as 5, and is written as 29 = 5(mod12).
Similarly, something like 115 hours would show as 7 after subtracting nine rotations of 12. ( 115 = 7 + 108, or 7 + 9 x 12).
So 115 is equivalent to 7 on the clockface, and is written as 115 = 7(mod 12).
This makes multiplication in clock-face arithmetic 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. How many complete 12's are there in this? Well, 12 x 277 = 3324, which leaves 11 when subtracted from 3335. 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, which leaves a remainder of 11 when divided by 12. (i.e. 5 x 7 = 11, mod12)
All the above calculations have been based on mod 12 arithmetic, but the important thing about modular 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.)
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:-
The procedure 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 more manageable, smaller numbers.
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). So 7 to the power of 13 x 61 is equivalent to 7 to the power of 1, which is just 7.
5. To encode a message, convert 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 a letter 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'?!!
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 goes into 24 exactly 4 times and into 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 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.
Clock-face arithmetic:-
(Also known as 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 that 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 woud be 5 hours, since 5 + 24 = 29. So 29 ends up as 5, and is written as 29 = 5(mod12).
Similarly, something like 115 hours would show as 7 after subtracting nine rotations of 12. ( 115 = 7 + 108, or 7 + 9 x 12).
So 115 is equivalent to 7 on the clockface, and is written as 115 = 7(mod 12).
This makes multiplication in clock-face arithmetic 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. How many complete 12's are there in this? Well, 12 x 277 = 3324, which leaves 11 when subtracted from 3335. 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, which leaves a remainder of 11 when divided by 12. (i.e. 5 x 7 = 11, mod12)
All the above calculations have been based on mod 12 arithmetic, but the important thing about modular 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.)
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:-
The procedure 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 more manageable, smaller numbers.
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). So 7 to the power of 13 x 61 is equivalent to 7 to the power of 1, which is just 7.
5. To encode a message, convert 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 a letter 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'?!!
Subscribe to:
Posts (Atom)