1
00:00:24,710 --> 00:00:29,810
So. Welcome, everyone. I, i work in the mathematics department and occasionally give talks like this.
2
00:00:30,260 --> 00:00:32,600
I'm going to tell you a bit about prime numbers today.
3
00:00:33,500 --> 00:00:43,639
You might well imagine most people know what a prime number is in case you don't, let me just take you through what the definition is.
4
00:00:43,640 --> 00:00:48,860
So prime numbers, something that can't be broken down really into any of the factors.
5
00:00:49,250 --> 00:00:53,719
So that number is like two and three and five and six definitely isn't because
6
00:00:53,720 --> 00:00:58,040
it's three times two and we don't usually consider one to be a prime factor.
7
00:00:58,130 --> 00:01:02,120
A prime number. That's something I'll tell you a little bit about in a moment.
8
00:01:02,510 --> 00:01:07,340
So we start listing these prime numbers. These are what they look like.
9
00:01:07,350 --> 00:01:13,620
They seem to go on a little randomly. They go to three, five, seven, 11, 13, 17, and so on.
10
00:01:14,460 --> 00:01:20,670
And then they go on. They get slightly more rare. But the issue is still the list seems to go on for quite a way.
11
00:01:21,060 --> 00:01:26,850
And in fact, the list goes on forever. And that's something I hope to prove today might be a little bit hard.
12
00:01:26,850 --> 00:01:32,250
So I'll try and take you through through that proof. You might wonder why people are interested in prime numbers.
13
00:01:32,640 --> 00:01:40,040
And that's something I want to give you a sense of today. So if you think about the times, you might have bought something from an Internet company,
14
00:01:40,050 --> 00:01:44,820
perhaps like Amazon or something like that, downloaded something or had your parents do it for you.
15
00:01:45,060 --> 00:01:48,900
It's actually prime numbers that's making all that secure that your parents credit
16
00:01:48,900 --> 00:01:53,190
cards aren't being sort of their numbers aren't being found out by other people.
17
00:01:53,400 --> 00:01:57,150
What makes it all secure is actually prime numbers. I want to say a little bit about that as well.
18
00:01:58,020 --> 00:02:02,460
And people also test out really fast computers trying to find the next big prime number.
19
00:02:02,880 --> 00:02:10,200
This is the largest known prime number at the moment, too, to the 57 million or so it was found earlier this year.
20
00:02:11,070 --> 00:02:15,870
It's got 17 million digits. Okay. So you never run out of prime numbers.
21
00:02:15,870 --> 00:02:19,710
They go on forever. And that's the biggest one we know at the moment.
22
00:02:23,020 --> 00:02:27,280
So let's let's see a little bit about why prime numbers are important.
23
00:02:27,310 --> 00:02:36,459
So if you if I gave you any number like, well, six is the easy one up there you can write six is two times three, oh, three times two.
24
00:02:36,460 --> 00:02:44,350
But that's basically the same thing you can write 24 well, 24 is two times two times two times three.
25
00:02:44,590 --> 00:02:49,840
But every number can be broken down into prime numbers.
26
00:02:49,840 --> 00:02:55,420
Every whole number can be broken down like that. Some of them, like this big number, are actually just prime and that's just it.
27
00:02:55,840 --> 00:02:59,770
And over numbers like six and 24 can be broken down into smaller things.
28
00:03:00,190 --> 00:03:03,390
Do you know how I can get this slide? Is all here still? No.
29
00:03:03,400 --> 00:03:07,330
No one knows. Okay. I was going to use the board as well anyway.
30
00:03:07,330 --> 00:03:16,000
I'll. I'll. You'll be seeing that will find all numbers in fact can be written in this way so everything can be broken down.
31
00:03:16,450 --> 00:03:21,160
And that sort of makes them like the atoms of multiplication, everything.
32
00:03:21,550 --> 00:03:25,430
If you think of this lot like a, a numbers, a molecule really can be broken down.
33
00:03:25,430 --> 00:03:31,209
There's certain way into these atoms and 24 can just be written as two times, two times two times three,
34
00:03:31,210 --> 00:03:36,040
and only in that way, rarely you could rejig the numbers around and put them in a different order.
35
00:03:36,400 --> 00:03:40,060
But really there's just those ways of doing it.
36
00:03:41,860 --> 00:03:46,360
Okay. And this is why we sort of think that, one, it really shouldn't be counted as a prime number.
37
00:03:46,360 --> 00:03:51,820
So if you if you thought one was a prime number, well, then what I just told you would be wrong.
38
00:03:52,480 --> 00:03:55,930
There's you can write six is two times three.
39
00:03:55,930 --> 00:03:59,950
But if one was a prime number you could also Roger is one times two times three. And that would be a different way of doing it.
40
00:04:00,250 --> 00:04:05,170
A One times one, times two times three. So I think I've worked out how to get these balls up.
41
00:04:05,170 --> 00:04:13,690
Let me. That looks promising. Okay. So because of that, you want to say every number can be broken down in a unique way.
42
00:04:13,960 --> 00:04:17,620
And so we don't really want to say one is a prime number.
43
00:04:18,760 --> 00:04:21,969
I've got to stand here doing this. Let's just nothing.
44
00:04:21,970 --> 00:04:26,830
That's far enough for now. So how would you find these out?
45
00:04:26,830 --> 00:04:30,830
Let me give you an example here. You need to find some patterns area.
46
00:04:32,290 --> 00:04:38,710
So if I said how would you break down a number into fact, I'll get this off the board for now.
47
00:04:39,160 --> 00:04:43,600
One seven. 1794.
48
00:04:43,650 --> 00:04:50,760
Okay. How would you break this down into all its numbers that make it up?
49
00:04:51,930 --> 00:04:58,590
And I think you all must know that if that number ends in knots, then it's got a factor of ten in there or a factor of two and a factor of five.
50
00:04:59,130 --> 00:05:05,910
So, you know, if you you can divide this by two and five and you'd get one seven, nine four.
51
00:05:07,440 --> 00:05:15,630
And because this number ends in two, sorry, engine four, you know, it's an even number and it's divisible by two itself.
52
00:05:16,170 --> 00:05:20,430
And if you break that down further, you're going to get eight, nine, seven.
53
00:05:23,920 --> 00:05:27,450
Now, it might not be very apparent to you. So that's divided by two.
54
00:05:30,310 --> 00:05:36,130
That was divided by two and five. What about eight, nine, seven?
55
00:05:36,160 --> 00:05:42,220
Does anyone know what eight, nine, seven might be factored by three goes into it because you can.
56
00:05:42,310 --> 00:05:48,850
Perhaps he's. I'm not sure how he spelled it. Perhaps the easiest thing is to say, well, nine hundreds of multiple of three three goes into the 900.
57
00:05:49,270 --> 00:05:56,320
And this is just 300, 900. So if you divide by three, you get 299.
58
00:05:58,510 --> 00:06:02,700
Now, does anyone know what goes into 299? Perhaps.
59
00:06:02,700 --> 00:06:06,509
Is that a sneak preview for the next ball? They know. But other than that, this is a bit hard.
60
00:06:06,510 --> 00:06:11,180
And you sat there thinking, is that prime or just three go into it?
61
00:06:11,190 --> 00:06:14,580
No, the seven. Well, you'd have to go and check.
62
00:06:14,970 --> 00:06:23,550
And actually it turns out that 299 is 13 times 23, but it take you a while to go and check that.
63
00:06:24,150 --> 00:06:30,540
So in the end, this is 13 times 23 and you've ended up getting all the factors.
64
00:06:30,540 --> 00:06:34,600
We've got a two, a five, a two, a three, a 13 and a 23.
65
00:06:35,370 --> 00:06:41,310
But I hope you can see now that if you're starting to get bigger numbers and obviously doesn't have a two or three that goes in,
66
00:06:41,610 --> 00:06:48,810
it might take you quite a while, even with a calculator to work out just how this is going to affect Horizon there.
67
00:06:48,900 --> 00:06:54,240
Yet that's one of the ways that the actual Internet security is based,
68
00:06:54,240 --> 00:06:58,050
that actually factories in these things can get quite hard if you've got really big numbers.
69
00:06:59,760 --> 00:07:03,600
Anyway, let me let me take you through this proof. I imagine you haven't seen much in the way proof.
70
00:07:03,600 --> 00:07:10,710
So let me go through this slowly and I'll try and give you an example on the next slide to show how this works.
71
00:07:11,760 --> 00:07:18,780
So, so if you don't quite get all this, don't worry. But this is sort of like a proof from several thousand years ago.
72
00:07:18,780 --> 00:07:24,900
You can see a Greek mathematician called Euclid proved in about 300 B.C. He lived in Alexandria,
73
00:07:25,230 --> 00:07:28,590
now in Egypt, and he proved there are actually infinitely many prime numbers.
74
00:07:29,340 --> 00:07:32,850
And he had a very clever way of doing these called proof by contradiction.
75
00:07:33,420 --> 00:07:35,190
So we sort of like say to ourselves,
76
00:07:35,640 --> 00:07:43,650
let's pretend this is false and try and make some conclusions and get to a point where actually we've ended up with some nonsense.
77
00:07:43,650 --> 00:07:47,190
So we know we started with a wrong, wrong starting place.
78
00:07:47,820 --> 00:07:55,080
So what he says is, let's suppose there were just finite many prime numbers that the list stops.
79
00:07:55,380 --> 00:08:01,020
It doesn't go on forever. It actually stops. And if you've only got so many of those prime numbers, you could list them all.
80
00:08:02,370 --> 00:08:06,239
And what is clever idea is if you've just got so many prime numbers like P1,
81
00:08:06,240 --> 00:08:10,320
P2 up to P.K., these are all the prime numbers, Euclid fault there might be.
82
00:08:10,860 --> 00:08:15,630
What he did is he multiplied them all together and added one OC.
83
00:08:15,750 --> 00:08:22,350
And why he did that is because if you multiply all those numbers together and add one, you've definitely got a number.
84
00:08:22,350 --> 00:08:26,550
Now that none of the other numbers that you had divided it.
85
00:08:26,790 --> 00:08:31,350
Okay, if you divide them main, they all leave remainder one, none of them go in.
86
00:08:32,220 --> 00:08:39,780
But that new number, that really big number he's probably created and doesn't have any of your known prime numbers as factors.
87
00:08:40,470 --> 00:08:44,130
So the only possibility is now over. It's prime.
88
00:08:44,790 --> 00:08:48,930
Or if you went and looked at its prime factors, they wouldn't be on your list.
89
00:08:49,380 --> 00:08:54,840
You've deliberately found something that's new, gives you a new prime number one way or another.
90
00:08:55,560 --> 00:09:02,250
So just in case that might seem a little bit confusing, let's try and do it with an example and see what Euclid's method would have done.
91
00:09:03,810 --> 00:09:08,580
So I'm like, Let's say we were really quite lazy and we only fault there were two prime numbers,
92
00:09:08,580 --> 00:09:11,700
two and five, which is a very good effort, at least in them all.
93
00:09:11,700 --> 00:09:21,180
But let's say we started with that. Then what Euclid would say is take you two and you five, multiply them together, add one, and that gives us 11.
94
00:09:21,900 --> 00:09:29,310
Now, either this new number, 11 is prime, or if we factories 11, we get some numbers that aren't two or five.
95
00:09:30,120 --> 00:09:34,440
So in this case, here we get 11 and that's a new prime. So we've got one more on our list.
96
00:09:35,460 --> 00:09:41,310
So we might say, okay, maybe we've got them all. Now let's take two and five and 11.
97
00:09:41,340 --> 00:09:50,850
I think I've got them all. Well, Euclid would say multiply them all together, add one and you got 111 and it isn't prime actually 111,
98
00:09:51,480 --> 00:09:56,730
but it's prime factors which are three and 37 and new ones not on our list.
99
00:09:57,270 --> 00:10:01,739
So if, however, we felt fault, we'd got all the prime numbers, he had a way of saying,
100
00:10:01,740 --> 00:10:05,850
multiply them all together, add one, and I'm guaranteed to get you a new prime number.
101
00:10:06,330 --> 00:10:10,020
So that means you can never list them all. The list must go on forever.
102
00:10:11,810 --> 00:10:15,530
But anyway, the reassuring thing is we're never going to run out of prime numbers.
103
00:10:15,860 --> 00:10:19,880
You can always find bigger and bigger and larger prime numbers.
104
00:10:20,900 --> 00:10:23,990
And there's nothing images actually from in this museum.
105
00:10:25,250 --> 00:10:29,060
This is you played our statue of Euclid. I guess no one really quite knows what he looks like.
106
00:10:29,870 --> 00:10:35,960
And this is a statue of him in the museum. He wrote very famous books called The Elements.
107
00:10:36,380 --> 00:10:40,940
And there's been more editions of The Element than probably any book except the Bible.
108
00:10:40,970 --> 00:10:47,450
I mean, this was really the mass book of the maps books until really the start of the 20th century.
109
00:10:48,260 --> 00:10:49,910
So a very famous Greek mathematician.
110
00:10:53,650 --> 00:11:02,530
So if I if I gave you some examples a bit like this again and said, which of these a prime how easy would some of them be to find?
111
00:11:02,540 --> 00:11:07,450
Does anyone want to make any cross a few off my list and say such and such isn't prime going.
112
00:11:10,180 --> 00:11:14,220
Okay. And we know that because what what factor of using. Okay.
113
00:11:14,260 --> 00:11:20,380
So even if there's any even ones that we know they're not going to be prime anyone else cross any of the areas of.
114
00:11:20,420 --> 00:11:25,149
Yeah. The second one because. Okay.
115
00:11:25,150 --> 00:11:30,700
So you know if something ends in five or not, it's divisible by five in any one spot.
116
00:11:30,700 --> 00:11:34,410
Any of the others. We are going.
117
00:11:38,200 --> 00:11:41,440
Oh, I'd love to have a think about that.
118
00:11:41,760 --> 00:11:45,880
It depends. What? Whether 273 is divisible by seven. Yes, it is. It is divisible by seven.
119
00:11:46,120 --> 00:11:50,290
Very small. And it's also divisible by three. But good, good sport.
120
00:11:51,040 --> 00:11:55,540
What about any of the others? Yep.
121
00:11:58,510 --> 00:12:03,060
Uh, I don't think so. Why do you think it is?
122
00:12:05,220 --> 00:12:08,310
Uh, no, definitely isn't, I'm afraid.
123
00:12:08,430 --> 00:12:13,260
Isn't divisible by three. Can anyone spot the fall four and what that might be divisible by?
124
00:12:15,940 --> 00:12:19,510
Anyone. Because he's got a certain pattern to it doesn't it.
125
00:12:19,810 --> 00:12:24,880
337337. And they won't think of you doing very well.
126
00:12:30,900 --> 00:12:35,680
Sorry. 14 no football.
127
00:12:35,850 --> 00:12:44,250
All the lost ones are old so 14 could divided also be an even number now 337 you see divides the four four.
128
00:12:44,850 --> 00:12:47,910
Can anyone see how many times 337 goes into the fourth one.
129
00:12:51,670 --> 00:12:54,979
No. So 1001 times.
130
00:12:54,980 --> 00:12:58,969
It's just that's why it sort of repeated like that. It's 337 times.
131
00:12:58,970 --> 00:13:04,790
2001 is the fourth one. But you can see they're getting a bit harder and.
132
00:13:06,590 --> 00:13:09,700
Here are some tricks for simple things.
133
00:13:09,710 --> 00:13:15,170
Obviously, it's fairly easy to work out whether something is divisible by two and it's not too hard for four,
134
00:13:15,170 --> 00:13:22,370
and eight over five is also fairly easy, mainly because we just use decimal and that's base ten.
135
00:13:22,370 --> 00:13:34,790
So two and five factors of tightness that makes a bit easier if you want to pull the numbers in all the digits in a number like for example,
136
00:13:35,150 --> 00:13:40,040
2732, one few other two and seven and three and two and one.
137
00:13:40,040 --> 00:13:45,949
You get what, nine, 12, 14, 15 and because 15 is divisible by three, so is that number.
138
00:13:45,950 --> 00:13:50,870
That's a trick you might not have seen before if you had to pull the digits and it's
139
00:13:50,870 --> 00:13:55,189
divisible by three that so the number would have been and the same worked for nine as well.
140
00:13:55,190 --> 00:14:00,440
If you add up all the numbers and it's divisible by nine the sum, so would the original number.
141
00:14:00,440 --> 00:14:04,400
So that number isn't divisible by nine because 15 is not divisible by nine.
142
00:14:05,090 --> 00:14:15,260
But these are just tricks for small numbers. If you wanted to work out some of the others, they're getting a bit hard as it happens.
143
00:14:17,210 --> 00:14:22,250
100 and fall 7 to 9 is prime. It's quite a large prime.
144
00:14:22,280 --> 00:14:25,340
It would take you quite a while to work this out.
145
00:14:25,670 --> 00:14:30,829
This other big number, though, is actually not prime,
146
00:14:30,830 --> 00:14:39,410
but you'd have to try all the prime numbers until eventually you got to 331 to find a factor that's going to take you quite a while.
147
00:14:39,800 --> 00:14:47,540
You'd have to try 66 prime numbers before you actually got to the 67th prime number, and that's going to take you a long time.
148
00:14:47,900 --> 00:14:53,780
So find verifying that's prime and showing that isn't would take quite a while and there were only six digits long those numbers.
149
00:14:55,700 --> 00:15:03,160
Okay. So this is what I'm sort of getting out wave with some of these aspects.
150
00:15:04,540 --> 00:15:08,810
If you're going to guarantee some of these pricing, you basically have to go to the square root.
151
00:15:08,830 --> 00:15:15,100
I imagine you've come across ideas of square roots. So the square root of four is two, square root of nine is three.
152
00:15:15,370 --> 00:15:22,810
You'd have to go up to the square root checking all the prime numbers, and if none of them divided it, then it was prime.
153
00:15:23,410 --> 00:15:35,920
So if you wanted to check the 104,729 was prime, you got to try every prime number, really quite a few of them, 66 until you get up to 323.
154
00:15:36,310 --> 00:15:41,680
And then by that point, you've actually checked his prime. But that's really quite a hard thing to do.
155
00:15:42,430 --> 00:15:53,530
So actually working out in general, this sort of factorisation is quite hard even for computers once the numbers start getting quite big.
156
00:15:54,310 --> 00:15:58,390
So that's really why we use it in security.
157
00:15:59,840 --> 00:16:06,140
Here's a novel way, a clever way. Do it due to a Frenchman man from the 17th century fermor.
158
00:16:07,670 --> 00:16:16,070
So if a P is a prime, an end is a whole number, then the prime number will divide.
159
00:16:16,370 --> 00:16:20,989
And the P minus sign. That's a theorem that you might meet at university if you studied maths there,
160
00:16:20,990 --> 00:16:26,780
but we're only really interested in it from a point of view of helping test prime numbers.
161
00:16:27,350 --> 00:16:32,629
So if we just check it here, what his theorem says is that for something like five,
162
00:16:32,630 --> 00:16:38,360
which is definitely five, definitely prime five divides two to the power of five minus two.
163
00:16:39,080 --> 00:16:47,600
So two to the power, five minus two is 30 to -2 and we get 30 and five also divides three to the five minus three
164
00:16:47,600 --> 00:16:54,470
because that's 240 and five will also divide fall to the five minus four because that's 1020.
165
00:16:55,490 --> 00:16:58,220
And so if you turn it on its head and say, well,
166
00:16:58,580 --> 00:17:07,520
suppose I had a number that didn't this theorem didn't hold for then I knew it wasn't prime could be useful the oval way round.
167
00:17:07,520 --> 00:17:15,020
Well having to check all these factors you could do one possibly big calculation, but one calculation and get it right.
168
00:17:15,770 --> 00:17:22,070
And so you could say to yourself, well, if P is prime, it's going to divide two to the P minus two.
169
00:17:22,940 --> 00:17:33,110
So if I have a number that isn't prime or if I have a number N and it doesn't divide two to the N minus two, then I won't be prime.
170
00:17:33,110 --> 00:17:35,690
And sometimes that's an easy thing to work through.
171
00:17:36,020 --> 00:17:42,260
Then when you've got a large number and you're trying to work out all its possible factors, so that could be a way of crossing it off.
172
00:17:43,310 --> 00:17:48,020
The trouble is there are some nasty numbers out there that still satisfy all these tests.
173
00:17:48,020 --> 00:17:53,510
So we thought we'd call these things pseudo primes, and they do this.
174
00:17:53,630 --> 00:18:05,930
They satisfy all this without being prime themselves. It won't be very obvious, but 561 is one of these numbers, so 561 satisfies all.
175
00:18:07,070 --> 00:18:16,370
This Theorem 561 would always divide added to the 561 minus sign, but it isn't itself prime.
176
00:18:16,370 --> 00:18:23,509
So there are some annoying numbers out there that sort of like even if you checked with this, you wouldn't be 100% sure they were prime.
177
00:18:23,510 --> 00:18:31,339
You just you'd think they were probably prime. But there are annoyingly 100 there are infinitely many of these false primes out there.
178
00:18:31,340 --> 00:18:35,960
So actually working out whether some of these prime are not can be quite, quite hard.
179
00:18:36,320 --> 00:18:42,770
There are ways of quickly showing something isn't, but there are these false primes out there.
180
00:18:44,060 --> 00:18:50,240
Let me change topic a little bit here, first of all. So that's so picture of wiles.
181
00:18:51,320 --> 00:18:53,090
This is on true now? I'm afraid so.
182
00:18:53,240 --> 00:18:58,520
So the new maps built in which you're actually going to I think after this or some of you it's called the Andrew Wiles building.
183
00:18:59,240 --> 00:19:04,550
And the Andrew Wiles building was named unsurprisingly after Andrew Wiles, who is here doing Master Oxford.
184
00:19:04,830 --> 00:19:13,910
He's the man who proved Fermat's Last Theorem, which was one of the really famous theorems of mathematics that been unproved for 350 years.
185
00:19:14,300 --> 00:19:22,910
And he came along and proved it in the nineties. But so you may well be seeing the new Andrew Wiles building after this.
186
00:19:23,110 --> 00:19:26,450
Fermat was an important mathematician in the 17th century.
187
00:19:27,970 --> 00:19:34,520
Let's change topic a little bit now and think to ourselves, how is this going to be useful?
188
00:19:34,540 --> 00:19:41,800
Well, I'm talking about in the real world because you might be thinking prime numbers are nice enough, but what point are they?
189
00:19:43,180 --> 00:19:45,420
Well, actually, you use them a lot without really knowing.
190
00:19:45,430 --> 00:19:52,060
It's like I say, if ever you buy anything off the Internet, then you basically are using prime numbers.
191
00:19:53,650 --> 00:20:02,050
So what's the setup in the Internet? You've got yourself your computer and you sort of like on the Internet with a Internet company.
192
00:20:02,200 --> 00:20:11,260
How are they going to be able to get from you, your or your parents credit card number to them without anyone that saying,
193
00:20:11,860 --> 00:20:18,040
you know, intercepting the communication or anyone who would like to steal your computer or something like that.
194
00:20:18,250 --> 00:20:21,790
How can you be sure that your credit card number will be safe?
195
00:20:24,210 --> 00:20:29,850
And you got to remember, there are millions and millions of people out there using the Internet all the time to buy things.
196
00:20:31,130 --> 00:20:37,810
Well, there are always all sorts of problems with communications in front of you if you want to and code sorry.
197
00:20:37,820 --> 00:20:42,740
If you want to read a good book on this, there's a book by Simon Singh.
198
00:20:45,680 --> 00:20:57,510
Just call the code book. It's a very good read for finding out about how people used to communicate in secret over the years.
199
00:20:57,930 --> 00:21:01,739
It's not it's not hugely mathematical, but there's. So it's a very good read.
200
00:21:01,740 --> 00:21:04,920
And so some of this detail will be in that book as well.
201
00:21:05,850 --> 00:21:13,319
So how might you do this? If you think to yourself, I'd like to keep a secret, but I want to, you know, share it with a few friends,
202
00:21:13,320 --> 00:21:18,720
but only those friends so that it really is secret amongst us, but no one else.
203
00:21:19,740 --> 00:21:25,830
Well, they used to do this many, many years ago by just using a very simple cipher.
204
00:21:26,490 --> 00:21:29,880
What you might do is you've got this message you want to send.
205
00:21:30,630 --> 00:21:35,250
What you could do is just change every letter in some way that you was agreed.
206
00:21:35,460 --> 00:21:39,990
Okay. You and all your friends would know that this was how you were going to communicate.
207
00:21:39,990 --> 00:21:46,049
You were going to scramble your message by taking a word and swapping letters, for example.
208
00:21:46,050 --> 00:21:55,550
Let me give you an example here. So what you do is at the top here, you've got yourself what's called the key.
209
00:21:56,120 --> 00:21:59,180
Whenever you see a nay, you're going to replace it by a G.
210
00:21:59,540 --> 00:22:04,610
Whenever you see a B, you're going to replace it by a P. Whenever you see your name, you're going to replace it by a Q.
211
00:22:05,270 --> 00:22:09,290
So if I get a phrase like Oxford Mathematics, if I've done this right.
212
00:22:09,650 --> 00:22:14,960
O became L and X became W and F became N and so on.
213
00:22:15,560 --> 00:22:22,880
But if you sort of like manage to, oh, if you lost this message or your friends lost it.
214
00:22:23,240 --> 00:22:25,610
Anyone just picking this up, would it know what they said?
215
00:22:26,360 --> 00:22:32,180
Okay, this would be a scrambled message and they wouldn't know anything about what you've been trying to say to one another.
216
00:22:33,290 --> 00:22:40,850
The trouble is, once you start saying a lot to one another over, people could stop making guesses as to what the how it got scrambled.
217
00:22:41,630 --> 00:22:48,830
Because the I mean, there's all sorts of problems here. One is, how do you carefully get this private key to all your friends?
218
00:22:49,550 --> 00:22:56,930
And then if you keep communicating enough, people can start making guesses as to what you might have been writing.
219
00:22:57,800 --> 00:23:10,340
So if I had a page, you know, quite a long bit of text and I used my key to scramble it all, sent it to you, but you accidentally got intercepted.
220
00:23:11,460 --> 00:23:18,020
What what letter do you think might appear most in the scrambled, uh, scrambled work?
221
00:23:18,020 --> 00:23:23,700
Can anyone make a guess? If I was using this copier, what do you think would appear most?
222
00:23:24,510 --> 00:23:29,920
G. G. You're going for G because. H on the ray.
223
00:23:30,290 --> 00:23:36,309
He's a very common light. That's a good suggestion. There would be a lot of GS, but it wouldn't be the most common one.
224
00:23:36,310 --> 00:23:38,799
Does anyone know? It would be J?
225
00:23:38,800 --> 00:23:45,700
But there would be a lot of GS, but the probably be most j's because E's the most common letter in the English alphabet.
226
00:23:45,730 --> 00:23:50,860
Does anyone know what the second most common is? No.
227
00:23:51,010 --> 00:23:54,500
Afraid not. If we could be a while. I suppose we have to have this. It's gone.
228
00:23:55,600 --> 00:23:59,180
No, no, it's actually t. T is the next most common one.
229
00:23:59,720 --> 00:24:03,290
But you can see you're already guessing the way people are.
230
00:24:03,290 --> 00:24:07,130
If you saw a lot of JS, you'd be thinking, maybe that came from me.
231
00:24:07,580 --> 00:24:14,719
Maybe that came from T. And then if you saw, like saw a lot of things that were maybe T something e you might be thinking to yourself,
232
00:24:14,720 --> 00:24:17,870
that's perhaps an H that was the something between them.
233
00:24:18,500 --> 00:24:28,190
This is what Phumzile call frequency analysis. So here are the how common the English letters are.
234
00:24:28,760 --> 00:24:37,459
So you can see E appears most commonly at 12.7% of the time on t is the next most common one at 9.1.
235
00:24:37,460 --> 00:24:41,750
But as common as someone said, and this is also pretty common as well.
236
00:24:42,470 --> 00:24:48,049
So there's you could sort of once you add a lot of text, you could start making educated guesses.
237
00:24:48,050 --> 00:24:55,070
You wouldn't want to just go in randomly and start thinking this might be that and this might be that, but you could do some frequency analysis.
238
00:24:55,760 --> 00:25:02,600
So it was actually Islamic mathematicians around 800 A.D. that actually started being able to break down this code.
239
00:25:02,600 --> 00:25:07,280
So you can't just use a set, especially in this day of modern computers.
240
00:25:07,670 --> 00:25:12,860
You can't just sort like use a SCI for the way they used to do back in Roman times or something like that.
241
00:25:12,860 --> 00:25:17,840
It would just be much too easy to crack. So you don't have to be a bit smarter.
242
00:25:18,860 --> 00:25:22,309
Also, if you were sort of like an Internet company, perhaps someone like Amazon or something like that,
243
00:25:22,310 --> 00:25:28,100
they've got millions and millions of customers, even if they came up with something a bit better than this.
244
00:25:28,640 --> 00:25:34,850
Are they really going to have to send all this to all the customers around the world and be sure that
245
00:25:34,850 --> 00:25:39,380
everyone sort of like taking good care of it and not leaving it on the bus and various things like that.
246
00:25:39,740 --> 00:25:47,560
They're really going to have to come up with something better than that. So this is this has always been an issue of what I call private keys.
247
00:25:47,680 --> 00:25:58,420
How do you get the key to your friends? Because if if maybe one of your friends isn't not trustworthy or they lose it all, it just gets intercepted.
248
00:25:58,840 --> 00:26:04,149
All your enemies. Because we might be talking about this at wartime. All your enemies can now have it.
249
00:26:04,150 --> 00:26:08,410
And these are either competitor companies or their enemies at war time.
250
00:26:08,410 --> 00:26:17,860
Security is a major issue. You know, we've we've, you know, personal details with secrets, with things like that could be majorly important.
251
00:26:18,520 --> 00:26:24,380
This information gets kept secret. So these are guys.
252
00:26:25,640 --> 00:26:33,170
So we've asked Jemmy and Adam, and they gave their initials to what is basically the most used bit of mass really, I guess in the world today.
253
00:26:33,920 --> 00:26:38,660
It's a mass or it's a large part of the mathematics behind Internet security.
254
00:26:39,290 --> 00:26:47,000
If you give over your credit card details, send it on to some Internet company, it would be they sell some version of this.
255
00:26:47,210 --> 00:26:49,010
That's basically keeping it a secret.
256
00:26:49,880 --> 00:26:56,630
It's actually it's reasonably new mass because this came in 1977, which I guess might seem a long time ago to you people.
257
00:26:56,630 --> 00:27:01,360
But yeah, I remember 1977, and that's quite new for mathematics.
258
00:27:01,380 --> 00:27:08,630
1977, they came up with this idea. It uses what I told you about earlier Fermat's Little Theorem.
259
00:27:09,170 --> 00:27:13,580
So it's 17th century maths and the Chinese remainder theorem, which is even older maths.
260
00:27:14,240 --> 00:27:18,139
So the actual maths behind this, you could explain to Fermat. I need to understand it.
261
00:27:18,140 --> 00:27:26,450
Fine. What he'd be astonished about is how you've got to know about prime numbers that are like hundreds and millions of digits long.
262
00:27:26,850 --> 00:27:29,190
He'd have no idea about the modern computer age.
263
00:27:29,190 --> 00:27:35,000
He wouldn't know how you'd be able to come up with a prime number of 17 million digits, like we mentioned earlier.
264
00:27:36,800 --> 00:27:40,940
So I'm going to tell you a little bit about how prime numbers are used in this.
265
00:27:42,030 --> 00:27:45,870
So this is sort of the we don't really want to use a private key system.
266
00:27:46,380 --> 00:27:57,300
We want to use a public key system. It's a bit better. So what the Internet company does is tell all its customers or really the customers computers,
267
00:27:57,660 --> 00:28:07,170
how they're going to be able to scramble their message so that you can send on your credit card details in a careful way.
268
00:28:07,890 --> 00:28:11,549
You won't be able to unscramble them, but you will be able to scramble them.
269
00:28:11,550 --> 00:28:19,860
And that's quite, quite so. So what they do, the Internet company sends to your machine something called the public key.
270
00:28:21,060 --> 00:28:26,550
They don't mind if it gets lost the Internet company, because all it is is a means of scrambling.
271
00:28:26,640 --> 00:28:30,420
Okay. Then your computer gets it.
272
00:28:30,750 --> 00:28:34,950
You go and you buy what you want on the Internet and you send your details on.
273
00:28:35,190 --> 00:28:41,310
And only the Internet company knows how to scramble it, unscramble it, decrypt it is a fancy word.
274
00:28:42,700 --> 00:28:52,390
Okay. And what makes this secure and what makes this basically mean that no one's going to be able to break it is if you multiply numbers together,
275
00:28:52,870 --> 00:28:57,790
that's easy. Any computer can do it quite quickly, even if the numbers are huge.
276
00:28:58,360 --> 00:29:02,800
But if you're going to have to raise it, then it takes a long, long time.
277
00:29:02,830 --> 00:29:09,430
Okay. So if I gave a computer a very large number and said, please go and work out its factors,
278
00:29:09,730 --> 00:29:11,980
especially if there were many of them and the factors were big,
279
00:29:12,280 --> 00:29:19,360
it might sit there for ages and ages and years and years and in fact, millennia and millennia before we actually came up with the answer.
280
00:29:19,840 --> 00:29:25,840
So that's why the system secure. So if you multiply two large numbers together, it's easy.
281
00:29:26,320 --> 00:29:32,830
If you then gave the computer that product and said find them, then it might sit there working for a long, long time.
282
00:29:33,500 --> 00:29:40,780
And this is what's called a one way function where it's very easy to go one way, an incredibly hard, at least computation wise to come backwards.
283
00:29:42,970 --> 00:29:44,920
So let me give you a few more details here.
284
00:29:46,690 --> 00:29:58,060
So what what goes on in your computer is the Internet company gives you all computer, just two numbers and an E.
285
00:29:58,960 --> 00:30:03,700
And actually what goes on in the computer is very simple, is called the encryption power.
286
00:30:04,330 --> 00:30:08,170
And the number is huge. It might be like a thousand digits long.
287
00:30:09,920 --> 00:30:14,700
And it's only got two factors. He's got two prime numbers as its factors.
288
00:30:16,850 --> 00:30:25,400
All this system is still a cipher. It's like taking those 26 letters we had before and moving them around and rearranging them as 26.
289
00:30:25,610 --> 00:30:28,760
But we're not using 26 anymore. We're now using N.
290
00:30:29,660 --> 00:30:33,830
And so N is about ten to the power of a thousand, a huge, huge number.
291
00:30:34,490 --> 00:30:36,920
And so if you thought to yourself, you know, where am I?
292
00:30:36,920 --> 00:30:42,649
E's on my TS amongst these ten to the thousand numbers, you just can't do frequency analysis anymore.
293
00:30:42,650 --> 00:30:46,520
It's just too, too big. You're going to have to find other ways of doing it.
294
00:30:46,940 --> 00:30:51,680
So it's still a cipher, but we're using a number much, much bigger than 26 now.
295
00:30:55,600 --> 00:31:00,940
And all your computer does. I mean, it might be explained a bit more.
296
00:31:00,940 --> 00:31:05,560
Is something called clockwork arithmetic or modular arithmetic that I've just explained in different ways here.
297
00:31:07,580 --> 00:31:16,070
You want to send them your credit card details? Let's say this is some number and and I'm probably going to be less than nine.
298
00:31:16,190 --> 00:31:20,179
But if not, you could send it by beat your message. So let's say M is bigger.
299
00:31:20,180 --> 00:31:30,020
That is less than. All your computer does is take that number E that the Internet company gave it.
300
00:31:31,070 --> 00:31:38,180
Raise it to the power e divide by the number n and you get some remainder.
301
00:31:38,480 --> 00:31:41,870
It goes so many times does and and that leaves some remainder.
302
00:31:42,200 --> 00:31:49,909
And the remainder is just what gets sent off. So it's very big numbers are involved, but the actual maths is really quite simple.
303
00:31:49,910 --> 00:31:54,620
You raise it to the power e you divide by N and whatever the remainder is you
304
00:31:54,620 --> 00:31:59,449
send on this is now your scrambled message and if someone intercepted it,
305
00:31:59,450 --> 00:32:02,510
it would just be gobbledegook to them. They wouldn't know anything about it.
306
00:32:04,610 --> 00:32:08,570
Maybe there were people there thinking I could break that. That would be easy enough to break.
307
00:32:10,040 --> 00:32:13,340
So let's talk about cracking it. How would you crack this?
308
00:32:13,970 --> 00:32:24,530
Let me actually let me go back. One slide here. If you've got any public key system, what you have told people how to do is encrypt.
309
00:32:25,100 --> 00:32:28,340
That's a bit like giving someone half of an English French dictionary.
310
00:32:28,610 --> 00:32:32,540
Okay, let's say I gave you the English French half of the dictionary.
311
00:32:33,230 --> 00:32:37,010
And I said to you, What does this mean? What does your de mean?
312
00:32:37,340 --> 00:32:43,760
And Thursday. Okay. How long do you think it would take you not knowing that and we've only the English French.
313
00:32:43,790 --> 00:32:47,930
But what would you have to do to work out? Jeopardy meant Thursday.
314
00:32:49,220 --> 00:32:55,730
Why would it take you a while? Yeah.
315
00:32:55,750 --> 00:32:58,670
You'd have to just keep looking. You wouldn't know where to start.
316
00:32:58,670 --> 00:33:02,840
But in principle, if you sat there and sat there and sat there and eventually got to TS,
317
00:33:03,320 --> 00:33:06,440
then you'd work out that Jody met Thursday but would tell you ages.
318
00:33:07,280 --> 00:33:16,640
So if I gave you the English French half of the dictionary and said, make the other half, you could tell you a long, long time.
319
00:33:17,030 --> 00:33:24,710
But if someone tells you how to encrypt or change something into a different language, you always have in principle a way of getting it back.
320
00:33:25,070 --> 00:33:28,340
But that's going to have to take you a long, long time for this to be secure.
321
00:33:28,340 --> 00:33:32,510
And it would take you a long, long time because you'd have to sort of like take in words.
322
00:33:32,960 --> 00:33:36,530
All I know is I've been turned to add numbers and then you'd have to work out
323
00:33:36,530 --> 00:33:40,850
all these calculations and then sort of alphabetise the other half to get back.
324
00:33:41,270 --> 00:33:49,280
That's going to take for ages. Another thing you might try and do is just actually work out what the factors of that end is.
325
00:33:49,730 --> 00:33:53,090
The end is this thousand digit number somewhere in your computer.
326
00:33:53,610 --> 00:33:57,410
If you can go and work how those factors are. You can break the code.
327
00:33:57,920 --> 00:34:00,950
But that's going to take you pretty much forever. Okay.
328
00:34:00,980 --> 00:34:06,350
And the Internet company tomorrow or probably even later this afternoon, are going to be using different prime numbers.
329
00:34:06,800 --> 00:34:10,940
So you don't have the rest of the universe to sort of like work this through.
330
00:34:11,180 --> 00:34:16,280
You've only got sort of like perhaps the next ten, 15 minutes before another set of numbers are used.
331
00:34:17,450 --> 00:34:26,029
So it's pretty secure. At the offer end, the the Internet company has got what matters.
332
00:34:26,030 --> 00:34:31,880
They've got the factors. Then they know those. And because of that, they can work out the decryption power.
333
00:34:32,390 --> 00:34:36,680
So when you've sent on your scrambled message, see? Okay, here.
334
00:34:37,310 --> 00:34:47,719
Then at the other hand, they just raise it to a decryption power d known only to then divide again by N and as if by magic.
335
00:34:47,720 --> 00:34:52,160
But it's just Fermat's Last Theorem and the Chinese remainder theorem.
336
00:34:52,340 --> 00:34:59,600
When you divide by an impulse out, they now know your credit card details what you want to buy, where they need to send it.
337
00:34:59,630 --> 00:35:05,140
All the information comes out, so it's really just quite simple maths that is going on.
338
00:35:06,850 --> 00:35:17,850
Okay. So I can say here, if you wanted to go and try and crack this, then you could do this by trying to do all the scrambling,
339
00:35:18,060 --> 00:35:20,880
rearrange the scrambling, and make the other half of the dictionary.
340
00:35:21,150 --> 00:35:27,230
That would take forever, pretty much all you could try to rise in this number, and that's pretty much going to take forever as well.
341
00:35:27,240 --> 00:35:32,799
So it's a very, very secure system. Okay.
342
00:35:32,800 --> 00:35:40,120
Let me sort of like draw this to a close a bit by talking a little bit about how the primes are distributed.
343
00:35:41,260 --> 00:35:45,610
So I hope you now at least see that primes can be really quite useful.
344
00:35:46,890 --> 00:35:51,660
They're funnier primes and it's very easy to ask very hard questions about them.
345
00:35:52,380 --> 00:35:57,240
You can do all sorts of things. Like if you look at if you look at this list,
346
00:35:59,100 --> 00:36:07,490
you can see you've got three and five next to an end of a five and seven, 11 and 13, 17, 17 and 1929 and 31.
347
00:36:07,500 --> 00:36:12,840
These are what are called twin primes, apart from two no number, that's even as prime.
348
00:36:13,860 --> 00:36:20,490
So all primes are old apart from two. And this means that the nearest two of them could be together is just a difference of two.
349
00:36:21,090 --> 00:36:26,280
And you can see quite a few examples here, 29 and 31, 71 and 73.
350
00:36:26,640 --> 00:36:33,150
And these are called twin primes. And people want to know whether or not they're infinitely many twin primes.
351
00:36:33,150 --> 00:36:38,790
And no one knows. No one's close to knowing, really at the moment there's been progress with that problem.
352
00:36:38,790 --> 00:36:43,799
Just this year, a lot of mathematicians got excited about various results related to that,
353
00:36:43,800 --> 00:36:49,200
but no one actually knows whether there are infinite many, many primes, just two apart.
354
00:36:49,500 --> 00:36:53,430
So it's very easy to ask very hard questions about these sorts of things.
355
00:36:54,240 --> 00:36:59,970
One thing we do sort of understand, though, is just how frequent they are because they might look a bit random,
356
00:37:00,450 --> 00:37:04,830
but long term we can actually get a fairly good sense of how how often they pop up.
357
00:37:05,310 --> 00:37:11,690
And that's something called the Prime Number Theorem. Okay.
358
00:37:12,480 --> 00:37:18,320
And my guess is you might not have met this idea before, so let me just tell you what a factorial is.
359
00:37:19,190 --> 00:37:24,650
You've probably seen it on your calculator. Uh, is this an and then an exclamation mark?
360
00:37:25,110 --> 00:37:31,420
And if you've never been sure what it was, it just multiplies all the numbers up to it together.
361
00:37:31,430 --> 00:37:35,180
So three factorial is one times. Two times three, which is six.
362
00:37:35,840 --> 00:37:42,829
Four factorial is one times two. Three times four, which is 24 and five factorial c is 126.
363
00:37:42,830 --> 00:37:51,680
Factorial 720. Why am I mentioned in this is because you can use this idea to show there are quite large gaps amongst the primes.
364
00:37:52,700 --> 00:37:59,630
If I said to you, find me 100 numbers, one after another that none of them are prime.
365
00:38:00,190 --> 00:38:04,570
I'm not. You might be thinking to yourself, that's impossible. Around 100 numbers, one after another.
366
00:38:04,850 --> 00:38:08,150
They aren't prime, but there are gaps like that in amongst the primes.
367
00:38:08,570 --> 00:38:12,440
And you can actually see that using this idea. Okay.
368
00:38:12,440 --> 00:38:16,400
So there are large gaps in the prime, in the primes, as large as you want them to be.
369
00:38:18,070 --> 00:38:28,660
If I if I take an factorial plus two and you're some number two was in that product ten factorial.
370
00:38:29,860 --> 00:38:34,720
So two divides N factorial and factorial is one times two all the way up to end.
371
00:38:35,410 --> 00:38:38,800
And if I add to this number, still going to be divisible by two.
372
00:38:39,610 --> 00:38:46,810
If you look at the next number, if any is bigger than three, then three will divide and factorial.
373
00:38:47,710 --> 00:38:51,910
Okay. It'll also divide three. So the next number is divisible by three.
374
00:38:52,870 --> 00:38:57,910
And if it's bigger than four or five or more than four will be in four factorial.
375
00:38:57,940 --> 00:39:02,800
Go into four factorial and also be divisible by four. So the first number's divisible by two.
376
00:39:02,830 --> 00:39:08,200
The next one by three. The next one by four. If I choose n as large as I want it to be.
377
00:39:08,470 --> 00:39:12,100
Here is a list of numbers. One after the over. I have no primes.
378
00:39:12,760 --> 00:39:27,130
So, for example, here, five factorial plus 222 is divisible by 223 is divisible by 320 fours, divisible by four, 125 divisible by five.
379
00:39:27,880 --> 00:39:33,550
So if I used N is 101, I'd actually have 100 numbers one after ANOVA, none of which are prime.
380
00:39:33,550 --> 00:39:37,600
So there's gaps as large as you want in amongst the prime numbers.
381
00:39:38,170 --> 00:39:42,820
But at the same time, we sometimes think that infinitely often there's two just next door to one another.
382
00:39:43,420 --> 00:39:49,090
So you get you get odd sort of like spurts of prime numbers and then huge gaps.
383
00:39:52,200 --> 00:39:57,770
Here's another thing you might have seen on your calculator, but perhaps never quite know what it was.
384
00:39:57,790 --> 00:40:06,600
So this is called the Aladdin function. Okay. Which is a I'm not going to use that much here, but Aladdin is basically stands for natural logarithm.
385
00:40:07,920 --> 00:40:12,420
You can work it out on your calculator. That's a graph of what it looks like.
386
00:40:12,420 --> 00:40:16,360
Aladdin of One is not a line of larger numbers.
387
00:40:16,380 --> 00:40:19,830
Aladdin of a number between two and three is one.
388
00:40:21,480 --> 00:40:27,570
You can work out a few things about it, but I'm just going to use it here to tell you a little bit about primes.
389
00:40:29,240 --> 00:40:36,050
It's got these nice properties. It basically takes multiplication and turns it into additions.
390
00:40:36,980 --> 00:40:43,100
So if you take a line of a product, you just add the values of that line.
391
00:40:44,090 --> 00:40:49,970
And it's not a line. Numbers aren't very big compared with what originally you had.
392
00:40:50,180 --> 00:40:53,530
So why a line of a million is just 13.8. Okay.
393
00:40:53,570 --> 00:40:59,870
So it takes quite large numbers and gives you quite small ones, but you don't really need to know much about it.
394
00:40:59,870 --> 00:41:10,580
But it does come up in this next theorem. So this is gives you a sense that actually primes do follow some sort of pattern.
395
00:41:11,600 --> 00:41:15,559
You might think to yourself, how many numbers are there? How many prime numbers are there?
396
00:41:15,560 --> 00:41:22,460
Less than a million or a billion or a trillion. And you can get pretty good estimates for that without actually working them all out.
397
00:41:23,390 --> 00:41:30,200
And that's what mathematicians suspected since 18th century proved at the end of the 19th century,
398
00:41:30,830 --> 00:41:37,820
that if you have want to work out how many prime numbers there are less than, say, about a billion.
399
00:41:38,570 --> 00:41:42,170
You work out a billion divided by a line of a billion.
400
00:41:43,010 --> 00:41:49,700
And that would give you a pretty good estimate of how many prime numbers there are without having to work them all out.
401
00:41:50,570 --> 00:41:53,620
And in fact, here's a picture of the graph. Okay.
402
00:41:53,620 --> 00:41:57,050
So I'm not sure you can actually see this in this slide, but there are actually two lines there.
403
00:41:57,920 --> 00:42:09,710
So the top line, the blue one, is how many prime numbers there are less than all these numbers and the N divided by.
404
00:42:09,890 --> 00:42:13,160
So X divided by a line of X is the estimate.
405
00:42:13,670 --> 00:42:16,640
And it's always a bit of an underestimate, at least initially. Okay.
406
00:42:16,970 --> 00:42:23,600
So it gives you a bit of an underestimate here, but it makes a pretty good estimate of how many they are.
407
00:42:23,900 --> 00:42:28,340
And long term, they're basically pretty much the same number.
408
00:42:28,390 --> 00:42:39,440
Well, what this twiddle is means on the previous slide is that if you divide how many prime numbers there are,
409
00:42:39,650 --> 00:42:43,520
by your estimate, long term, that number goes to about one.
410
00:42:44,120 --> 00:42:48,260
So pretty much is 100% long term, but it's estimated.
411
00:42:51,600 --> 00:43:00,120
Anyway, I'm almost done here. So let me let me try and give you a sense of, first of all, how hard it is to factor ice things.
412
00:43:01,990 --> 00:43:11,740
Using this prime number theory. From what I said to you, how many how many prime numbers am I going to have to try?
413
00:43:11,770 --> 00:43:21,370
How many factorisation I'm going to have to try to actually work out, say whether something in the order of ten to the 20 is actually prime.
414
00:43:21,430 --> 00:43:27,430
So I've got a 20 digit number, not a thousand digit number like we had in our say, a 20 digit number.
415
00:43:28,710 --> 00:43:36,690
To test whether it's really prime or not. I've got to try potentially all the prime numbers up to its square root.
416
00:43:37,710 --> 00:43:38,060
All right.
417
00:43:38,070 --> 00:43:47,460
And if you use the previous theorem to work out how many calculations I'd have to do, it ends up being about two RU ten divided by this number.
418
00:43:47,830 --> 00:43:56,280
And so just to give you an example here, if I was trying to work out whether a number with 20 digits actually was prime,
419
00:43:56,670 --> 00:44:03,300
and let's say it was I'm going to try all these that many calculations to actually work out where it was.
420
00:44:03,750 --> 00:44:08,100
I'm just for this 20 digit number. I've got to do 400 million.
421
00:44:08,370 --> 00:44:11,909
Trial factorisation of quite large numbers. Okay.
422
00:44:11,910 --> 00:44:15,600
So just a 20 digit number is going to be quite hard to check.
423
00:44:15,600 --> 00:44:22,110
It's prime. I might have to do 400 million calculations to actually work that out.
424
00:44:23,610 --> 00:44:29,220
There are over all sorts of ways of trying to test this, but it's always going to be a hard thing to check.
425
00:44:31,920 --> 00:44:37,860
So as I said here, there's actually it's actually quite easy to make claims about prime numbers that might be very hard to prove.
426
00:44:39,930 --> 00:44:52,790
Here are a few things we do know to be true. If you take all the prime numbers on and they are inverses, so I'll call a reciprocal.
427
00:44:53,760 --> 00:45:00,419
You take all the sums. That's some keeps getting bigger and bigger and bigger and basically goes off to infinity.
428
00:45:00,420 --> 00:45:10,140
So that becomes large. And Euler prove that if you take any what's called arithmetic progression.
429
00:45:10,920 --> 00:45:18,300
So something like perhaps three, seven, 11, 15, 19, 23 and so on.
430
00:45:19,260 --> 00:45:22,680
So you start with a certain number and then you have a common difference all the time.
431
00:45:23,940 --> 00:45:29,930
Now you can see here I've got various things that are prime. And I've got various things that aren't.
432
00:45:30,350 --> 00:45:36,209
Well, there's got to more primacy about the next one isn't. A man called Jerry Schley.
433
00:45:36,210 --> 00:45:41,490
He went and proved all these sequences will always have infinitely many primes in them.
434
00:45:41,820 --> 00:45:49,260
Okay, so for any sequence like that, yes, you'll get some things that aren't prime, but there will be infinitely many primes in those.
435
00:45:49,290 --> 00:45:49,940
He proved that.
436
00:45:50,700 --> 00:45:58,690
And a man called Chevy chef who was a Russian mathematician, he showed that there'll always be a prime number between any N and it's double.
437
00:45:58,710 --> 00:46:02,250
So if I gave you ten and 20, there's a prime number between those.
438
00:46:02,610 --> 00:46:06,450
If I gave you a hundred and $200, always be a prime number between those, perhaps lots of them.
439
00:46:07,290 --> 00:46:12,090
But you proved that. Always be a prime number before between those and then just to finish.
440
00:46:12,540 --> 00:46:16,050
Uh, these are things we don't know.
441
00:46:18,030 --> 00:46:23,820
Can't every hole number, every even number be written as the sum of two primes?
442
00:46:24,450 --> 00:46:30,630
If I gave you ten, you can write it as three and seven. If I gave you 12, that's five and seven.
443
00:46:31,870 --> 00:46:36,060
If I gave you 20, this is three and 17.
444
00:46:37,530 --> 00:46:42,210
Oh, you know, no one knows if every eve number can be written like that.
445
00:46:42,360 --> 00:46:46,290
We we've checked it up to about sort of like ten to the 20 or something like that.
446
00:46:46,290 --> 00:46:50,010
It's probably true, but only takes one counterexample to show it isn't.
447
00:46:50,240 --> 00:46:56,610
And no one knows the answer. No one knows whether it's possible to write every eve a number as the sum of two primes.
448
00:46:57,540 --> 00:47:02,190
Keep trying if you wish. But people, like I say, have gone up to ten to the 20, and that hasn't.
449
00:47:02,880 --> 00:47:09,240
I'm no one's found one yet. And then there are over important types of primes, primes of this form two to the P minus one,
450
00:47:09,660 --> 00:47:15,330
and no one knows whether they're infinitely many of those either. So problems are an important thing.
451
00:47:15,570 --> 00:47:20,490
The very easy to describe in some ways very useful in things like Internet security.
452
00:47:21,210 --> 00:47:26,190
But it's also very easy to ask very hard questions about them. So I think I'm going to finish there.
453
00:47:26,710 --> 00:47:30,030
Is anyone got any questions they might want asking?
454
00:47:30,510 --> 00:47:38,670
Like you say, if you want to find out more about how to create secure codes and how to scramble messages carefully,
455
00:47:38,970 --> 00:47:42,690
then Simon Singh's books, very good. If you want to have a read on this further.
456
00:47:43,170 --> 00:47:46,980
Okay. I think I'll hand over to Zarina if she's in the audience. Thank you.