prime-ative codes, cryptic quantums.






It’s come up a couple of times in conversations and my thoughts over the last few days, so I’ve decided to scrape together my memory and use some induction and try to explain to you how maths ensures your credit card numbers aren’t stolen when you buy things online…

To begin, it will probably be easiest to use an example given by Ian Stewart in one of his books. Imagine you’re standing at a rather quiet party, and there’s someone on the other side of the room that you’re trying to share confidential information with. For reasons of illustration you’re unable to cross the room – all the information you share has to be public.

So how do you do it?

Obviously a code is the best way, so if you were able to meet up before the party and devise a code so you could say anything without anyone knowing what you were on about.

Let’s make it more difficult, and say you weren’t able to meet up – in fact, you’ve never met the person before, you just know they’ll be wearing a bright purple jacket. We’ll call them M for fun.

That is a rather hard task, so we’ll make it a little easier by stating that the information you’re trying to convey is merely a number. and now suddenly your life is easy….given that M knows you’re trying to convey a number, and that M has ‘their’ hands on a couple of helpful algorithms.

Now, the branch of maths that deal with these type of algorithms is under number theory, and (in this example) falls mostly under cryptography.

I’m not going to say too much more about these branches of maths. Whilst I am happy to say I like number theory a lot, I have not yet been exposed to enough of it to give you a decent definition of what it entails.
Now, back to the party.

M shouts across the room “take your secret number and multiply it by 3”
“square your new number”
“add 25 to it”
“tell me your answer”
and you shout back “1321”.
M smiles and walks off, knowing the secret number is 12.
how?
by solving a simple equation:
9x^2+25=1321.
This is a very simplistic form of coding, and anyone in the room who is listening in and can do a bit of algebra can solve this problem. What is needed then is a very complex set of instructions that are very difficult to reverse, and an easy set of instructions that undoes the complex ones. That’s kind of wordy. Perhaps another example is worthwhile at this point:

Back to the party, except now the number you’re trying to convey is 6 digits long. Before we go any further, I need to introduce a deceptively simple function called the modulus, or mod. The mod function takes a number, divides it by another and gives you the remainder. Thus 15 mod 2 is 1, 12 mod 7 is 5, 16 mod 8 is 0. The reason it’s deceptively simple is that there are some cool theorems associated with the mod function, none of which I can currently remember! However, these theorems are what we could use to convey out message.

Lets also state that only you and M know your number is 6 digits long, and lets assume that M is the only one who knows the algorithm to reduce your eventual output back to the original input. Also, lets say that our number has the property that the sum of the 1st, 3rd, and 5th digits minus the sum of the rest has to equal 0, mod 11 (this is often used in bar-coding actually, so that the computer can work out if the barcode is correct, and so we can find the correct digit if one is missing), and that only M knows this property.

This is actually very easy to convey in secret if all these conditions are met. Before the party, M knows that your number is of the form abcdef, where (a+c+e-b-d-f) mod 11 = 0, whereas a counter ‘spy’ only knows you have a number that needs transmitting.
If M asks you too many questions, the spy can work out your code. M therefore needs to ask just enough questions such that the spy gets no information, but M gets all of it. Lets say M asks the following questions:

1)   What is the sum of all the odd digits?
2)   Minus the second number from the second to last number.
3)   What is the sum of digits 2 and 4?
4)   What is the sum of the first and last number?
5)   What is the sum of the last 2 digits?

Question 1 tells M a+c+e
Question 2 tells M e-b
Question 3 tells M b+d
Question 4 tells M a+f
Question 5 tells M e+f

Now, if we take ans 1 ,a+c+e, which is the first half of the mod 11 requirement above. Ans 3 tells us what b+d is. If we minus this from what we’ve just done, we get a+c+e-b-d, which is the majority of the mod requirement. We can use this to find f. We use this along with ans 4 to find a, and ans 5 to find e. These 2 ans with ans 1 tell us c, and e with ans 2 tells us b which with 3 tells us d.  

That can be quite difficult to follow, so we’ll use an example. Say our number is 763290.
Ans 1 will be 7+3+9=19
Ans 2 will be 9-6=3
Ans 3 will be 6+2=8
Ans 4 will be 7+0=7
Ans 5 will be 9+0=9

Ans 1=Ans 3 =11, which (as we’re working with mod here) is the same as 0, hence the last digit is 0. This means that a is 7, e is 9, c is 3, b is 6 and d is 2, which gives the answer 763290, which is correct!


Now this is just one type of coding, and, as I’m sure you can see, it is only as safe as the knowledge is. The more people who know about the algorithm and/or conditions, the easier it is to break the code. Even complex equations can be broken, and with today’s computers it is relatively easy to perform difficult calculations. A different type of coding is described here, but it is likely you will have needed to have studied second year maths to understand it.

A crucial part to coding is prime numbers, as prime numbers are the factors that are used to confuse the e output from hackers – for example, what are the factors of 30? 210? 9 699 690? don’t know? 30 >2,3,5 210>2,3,5,7 9 699 690 > 2*3*5*7*11*13*17*19. now, algorithms can be designed to chug through the different primes and see which ones factor your number, but we’re not talking 6 or 7 digit numbers. we’re talking numbers with anything up to a thousand digits (and we can go bigger, the biggest know prime is 12,978,189 digits long…ok, i feel like getting distracted. average book, about 600 words a page, each word average four letters – make it 5 for the spaces. 3000 letters per page. divide 12 978 189 by that….4 326 pages. the bible is 1200 pages roughly. so the biggest prime in the world, if written down, would take up as many books as 3 and 3/4 bibles. that’s kinda big!)

The bigger you go, the more tricks needed to cut down on the leg work done by the algorithm. It needs shortcuts, otherwise the system will take forever to try and solve the prime factors.

There are quite a few other techniques out there to use on encryption, techniques that, when piled on top of each other, can make it seem almost impossible to crack. Sadly though, they’re not impossible.

But it’s not all bad news!!!!

The encryption processes we use now are far from secure. Hopefully with the current development of incredible computers around the corner, new branches of mathematics will begin to open up, allowing cryptography further chances to strengthen itself, no longer using exhaustion to defeat it’s foes, but perhaps something slightly more intelligent and beautiful.

Advertisements

golden beauty

So….another blog!

I don’t whether today to write about logic, codes, symmetry or the Fibonacci sequence. I think, seeing as I put it off last time, I should do symmetry, but I know we will be doing the Fibonacci sequence in maths tomorrow, and I’m quite keen on seeing if I can pre-empt my lecturer….therefore, I think I’ll start with the Fibonacci sequence, then move onto symmetry….

So. In the late 12th century, a dude named leonardo of pisa or Fibonacci for short (i can’t remember why) decided he wanted to know how many rabbits he would have if he started with a certain amount.

I’m not entirely certain why he wanted to do it, however, in terms of the mathematical bunny leaps that have come from it, I’m fairly glad that he did!

As with most mathematicians, he decided to skirt certain issues and start at a very simple base to get a rough idea of the pattern that ran through the bunny population. He therefore started off with a couple of assumptions:

Firstly, rabbits don’t die.

Secondly, every female has only one baby every month.

Thirdly, except for the first couple, there are always more females than males.

So he started with one rabbit.(female)

And got bored waiting for it do something.

So he got another one. (male)

after one month, the two rabbits had another rabbit. (female)

Now the one male rabbit was happy. So he did what most males love, and the following month, there were two new babies, one male, one female.

all three females gave birth the following month, resulting in 8 rabbits. There are now five females, three males, so the next month there were 13 rabbits, 8 female, 5 male, etc….

that’s a pretty rough outline of the story, and one that isn’t completely true. The most important part of this story is the pattern: 1 rabbit, 1 rabbit, 2 rabbits, 3 rabbits, 5 rabbits, 8 rabbits, 13, 21, 34, 55, 89, 144….

So how do you get this pattern?

Take any number in the pattern, add the previous number to it, and you will get the following number. So to get 13, you add 8 and 5. there are formulas for working out how many ‘rabbits’ there are after so many ‘months’, but I won’t put those into this blog.

Soubtless some of you are going “ok….there’s a pattern….so what?” well, patterns are important things!!! If there’s a pattern, THERE’S A PATTERN, which generally means there is some interesting maths going on somewhere…

so let’s have a closer look at this pattern: 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610….

now have a look at the ratio’s between these numbers: 1/1 =1

2/1 =2

3/2 =1.5

5/3 =1.6666….

8/5 =1.6

13/8 =1.625

21/13= 1.61528462…

etc. the higher the pair of numbers you use, the closer this ratio gets to a very special number, which is called the golden ratio, and is approximately equal to 1.618(rounded to 3 decimal digits)

It is here I must take a breath, as the branches I could take you down are everywhere. The golden ratio is a truly important number, it appears everywhere, in your body, in beauty, in music, nature, shells….almost everything in nature links to this number.

But anyways, let me now tell you about some of the more interesting things about the golden ratio.

firstly, it is easiest to approximate the golden ration by using(sqrt(5)+1)/2. as it is an irrational number, it goes on forever, so we can never get it exactly, which is why we use it’s abbreviated form, 1.618, as this is a much ‘nicer’ number to use when doing calculations. It is also denoted by the Greek letter phi, and often called by such.

as stated above, it appears everywhere…so let’s start with a pineapple (we have to take one to class tomorrow…)

Count the ‘points’ in one clockwise spiral, and the points in one counter clockwise spiral. You will find that the number of points in each spiral will be a Fibonacci number, normally 5,8 or 13-but never 5 and 13, it will always be two consecutive numbers. in other words, the ratio between the spirals approximates the golden ratio.

it’s marvellous fun telling kids to look for a four leaf clover – they’re not very likely to find one. Why? Because four is not a fibonacci number. Seriously. That’s the reason.

now, nature is not saying “oh, four isn’t a Fibonacci number, therefore we can’t have that many leaves/points/ whatever”. people are still searching to find out why this number is so important to nature – for example, why not use a nice number like 1.6 exactly? – and there are some ideas I’ve heard about, such as claiming that the angles that the leaves make to the stem are arranged in the golden proportion to each other, resulting in the fourth leaf being over shadowed by the 6th leaf, therefore causing the 4th to die, resulting in only five. But I did a couple of calculations, and this doesn’t seem to be entirely true, so I will have to keep looking.

Some people claim that the golden ratio was used in the building of the pyramids. However, others say that it is just the fact that the golden ratio is so common that it crops up in measurements, as there is no record of the golden ratio from Egyptian times (it was first mentioned by the Greeks, popularised by Fibonacci). All that I can tell you is that it does seem to crop up almost everywhere, but what I find incredibly interesting is it’s relationship to beauty.

First, let’s start with a rectangle. Draw a rectangle of width 1, and length 1.618.Note that the relationship between the width and length is 1.618. Now, cut a square out of this rectangle with area 1 square unit. You will be left with a rectangle of 1 X 0.618. The relationship between the width and length of this new rectangle, is still 1.618. And you can keep doing this, endlessly, and each time, you will be left with a rectangle whose width and length are in the proportion of 1.618…which is fairly cool!

This rectangle is called the golden rectangle.

Now, I hope you remember some algebra from high-school.

If you want to find a number (lets call it the classic x) such that 1+1/x=x (or x2x-1=0), you find that the answer is phi. This explains why the rectangle cutting works, but I’ll let you try and figure that one out 😛

The rectangle is the first of the geometric shapes that can be drawn in a ‘golden proportion’, but any shape you can think of will have a golden ratio version of it (google it). The golden rectangle, triangle, cross, star, pentagon, spiral etc are generally found to be most ‘pleasing’ to the eye. why? I don’t know. The only common thing between them is this ratio, but you can test it for yourself by drawing a few or googling them and deciding which one you like the most. You may find that you don’t like the ‘golden’ one, but it is a general statement 🙂

Now, the final bit. You need a tape measure.

First, measure your arm, from fingertip to shoulder, then fingertip to elbow. Take the first, divide it by the second….and it’s close to 1.618. Same with your leg to body ratio, hand to elbow, finger to hand….

And then you get to facial features….rather than try to define it for you, go here.

But, whilst general beauty can be ‘created’ using phi, that doesn’t mean that phi is beauty. This is one of the areas that I think maths will never be able to completely explain: that of likes, dislikes, loves, hates, appreciation, ridicule. Whilst we can find (with relative ease) links between things that people like, and therefore create something generic that appeals to most people, we can never find something that anyone will truly find breathtaking. I am a huge fan of the TV series Numb3rs, and on one of the episodes they are dealing with music, and Charlie ‘explains’ that there are some sequences of notes and tones that appeal to everyone, and, using this, we can analyse music and find, with relative accuracy, how well a certain song will do when it’s released. I don’t know how accurate this is, but I do know that we can not quantify something as individual taste. Whilst maths can certainly be used to give us an idea of how people will react to something, we can’t guarantee it’s success. That being said, I do recall a quote that went something like “given all the information, we can predict anything”….

symmetrical flying rats

I was going to write this blog as a discussion on symmetry and time travel as a means of procrastinating from things that I have to do, but I suddenly realised that the ‘things’ I need to do could actually be quite fun to write about….so symmetry and time travel will have to wait for an….earlier date?

In my “general maths” lecture (so called by me as it is a broad summary of some interesting topics in mathematics, primarily aimed at non-mathematicians) we were given the following question: “if you write the numbers from 1-8 in a circle in any order, prove that there will always be a set of 3 consecutive numbers whose sum is at least 14.”

Some guy came up with a clever but messy proof, using logic to deduce that if you start with 8 and start making groups of three that are all below 13, the numbers you’re left with add up to over 14.

As I said, it was clever….but….it was also an ungeneral proof. Unelegant.in other words, everything that maths is NOT.

So…..onto the true beauty….

Our lecturer asked us to use the ‘pigeon hole’ idea to prove it, so called because….I actually have no idea why they used pigeons as an example. Maybe google knows.

But the idea is basic, and is as follows: if you have n pigeon holes, and n+1 pigeons, then there will be at least 1 hole that contains more than one pigeon….or you need to start searching for your missing pigeon…

A simple and obvious idea, but one that results in some useful results when it comes to counting and efficiency…

Now, on to the question…

Oh, on a side note, I can’t be bothered writing the numbers in circles, so I’m just going to do it a line. It would be much appreciated if you switched your imagination on, or, lacking coffee, use pen and paper.

Ok, so we start off with 8 numbers, their sum being 36, and we’re trying to prove that no matter what order we use, there will always be a set of 3 numbers whose sum is greater than 14. Let’s imagine that we have the simple order 1 2 3 4 5 6 7 8. From this formation, we can form the following groups: 123; 234; 345; 456; 567; 678; 781; 812.

Right.

Now what?????

Things to notice about these groups….

There are 8 groups.

Each number appears 3 times.

I had brilliant teacher in high school. He used to say that proving things was very simply a case of writing down what you knew, deducing obvious results, then seeing the “AHA!” stage, and then writing down the total proof. This here is the “aha!” stage…

As each number appears 3 times, the total sum of all the numbers is actually 3 *36 = 108.

As there are 8 different, groups, this total of 108 has to be shared amongst them all…so,108/8=13.5…

As we are only using integers, this means that at least one group has to have a sum of fourteen or more.

If you didn’t follow all of that, think of the pigeon holes. Imagine that there are 108 pigeons, 8 separate structures, each with 13 pigeon holes. If you’re still not getting it, leave a comment, and I’ll get back to you on it….

Now, a small rant, appropriate for a first blog!

Some people seem to get a great kick out of asking (in beautifully derogative tones) “Maths? Where do you hope to get with that?” read this link: Lockharts lament

The above example can be generalised to a random sequence of numbers ( I did have it floating around on my computer somewhere, if anyones interested, a small donation of fresh Columbian coffee in a bottomless mug will be sufficient for me to recreate it), which in turn could have some significance somewhere. At the moment I know not where. For me, the joy in mathematics comes not from the use of maths, but from doing the maths. I hope to introduce to some of you this joy that I find, and to others, I hope to increase your joy.

and it is on that note that i finish this, my first blog. All comments welcome!