Skip to main content
Loading Explore guides…
Prime Numbers in CS · Acedra
Home
Explore
Computer Science
Prime Numbers in CS
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
34 segments
Copy
Hide video
0:00
tim welcome back to computer files slightly different circumstances we were doing mega fave numbers in the last one right that's right yes i was talking about my favorite number um which many people were disappointed i didn't know by heart um but it is still my favorite topic to talk about big numbers um in the video i mentioned uh prime numbers in particular and the big number i selected for that video was a prime
0:25
number and i said i'll come back and talk about how they relate to computer science
0:32
prime numbers in computer science are interesting for various reasons
0:37
one of them is it's not always easy to find whether something is a prime number or not and if i give you a number not like 91 can you instantly tell whether it's a prime number or not um then again if i tell you that 7 times 13 is 91 you can quite quickly verify that that's right and therefore 91 is not a prime number um so there's various shortcuts that people found to quickly be able to determine whether something is a prime number but no one has found a shortcut to be
1:13
able to find the actual prime factors so telling that 91 is not a prime number is fairly easy for a computer to do finding the number 7 and 13 is relatively difficult of course i say relatively here because for a computer it's peanuts to find seven and thirteen um so that makes it interesting for computer science um but what makes it even more interesting is its application
1:42
its application is mostly in cryptography if i want to communicate in secret with you then i want to be able to do that so one example of where prime numbers are used in cryptography is the diffie-hellman key exchange which is something that mike pound was spoke about about three years ago on this channel a very interesting video watch it but another important application that uses prime numbers is rsa which stands for revest
2:13
shamir edelman the three developers of the algorithm and it's heavily based on prime numbers we see rsa everywhere don't we it's connecting to the internet we are almost always using rsa at some point is that would i be right in saying that exactly right yes thank you um so public key cryptography is the general class that rsa is in there was a video about this a long time ago by robert miles and he explains what public key crypto is but one of the most
2:42
important modern applications i would say crucial to the internet is the fact that https is built on top of this kind of technology now there are two main flavors to implement it there's rsa which is the older more established algorithm and there's elliptic curve cryptography again a topic of a different video and those are basically the two competing algorithms and of the two rsas based on prime numbers which is why i'm talking about those today in fact i would like to give a
3:15
quick demonstration of how rsa is used by going to our university's website so the browser i'm using is firefox but all browsers will have this functionality what you can see is this little padlock in the top left next to the address which means that your connection is secure now you can actually investigate how the connection is set up by clicking on the padlock clicking on the right buttons and then here's a button that says more information and then there's
3:45
the option to view the certificate which is what we're going to do now and here we see information about these certificates and the relevant information that i want to talk about is right here public key info and so it says the algorithm is rsa which is the algorithm i want to talk about it says something about the key size being 2048 bits then it says exponent which is roughly 65 000 and then there is this number which is the modulus which is a massive number it's cut off here
4:16
in hexadecimal and if we translate this to a decimal number the number we end up with is this number so what you end up with is this 600 digit decimal number it's a massive number and it's not a prime number actually but it is the product of two very very large prime numbers and two 300 digit prime numbers now the idea is that nobody knows what these two prime numbers are if you can figure out what these two big 300 digit prime numbers are that make up
4:48
this larger number i will offer you a fully funded phd and a guaranteed spot in the newspapers and perhaps even a big prize here and there and on top of that you get to hack the nottingham website but how come then this idea that it's difficult to find prime factors actually lays the foundation for a cryptographic protocol in order to explain how it works we need to talk about a slightly different topic first it's called modular arithmetic now it sounds complicated but it's
5:21
actually very easy in fact we do it every day if we're using an analog clock because a clock every 12 hours it goes back to its original position so if i ask you what is 15 hours on the clock you will know it's three hours because it's the remainder after division by 12. we do it often for 24 hour to 12 hour clock conversions but you can even do things like minus one hour which would be 11 on the clock or 25 hours which would be one on the clock now the clock we are going to be
5:53
talking about is not a 12 hour clock but a 91 hour clock because 91 is the product of the two prime numbers we're interested in the magic that actually happens is that if you think of a magic number between 0 and 90 then i can instruct you to take that number and raise it to the fifth power so can you think of any number should we go for let's go for number 18. okay 18. so what i instruct you to do is to take the number 18 raise it to the fifth power but do
6:30
that on a 91 hour clock so this is like 18 times 80 five times and then so it will always be a number between 0 and 90. for a human this is a bit complicated i don't expect you to know the answer but the answer will be 44 which is you know it's a normal number between 0 and 19. and then what i do is i take that number 44 and i raise it to the 29th power so i multiply it with itself 29 times
7:01
on the clock and the number i end up with is 18. so i know in normal arithmetic you have this idea of inverse operations is that a bit like that have we got back to the start doing that yes that's exactly right so 29 is a magical number that we found that will reverse you're doing the power to the s taking the number to the power five so whenever you take a number to the power of five
7:27
if i take that result to the power 29 the result i end up with is the original and it will always be the case on a 91 hour clock so that's something special about 91 hour clocks and i know they're different numbers for different clocks that's right so it's a special property of 5 and 29 and if you can figure out that the number in question is number 29 you can read the secret messages so it is important that no one knows the number 29. um so let's there's three questions we can
8:01
ask ourselves when when we see this equation the first one is where did the magic number 29 come from how do we get that the second one is how does the computation work why does it reverse the operation and number three is is this secure why is this secure let's answer question one so question one is where does the magic number 29 come from now to see where it comes from we need to construct a different clock so we had a 91 hour clock which was constructed by multiplying the two
8:34
prime numbers 7 and 13. we're going to construct the different clock by taking the number before the prime number so 6 because it's 7 minus 1 and 12 because it's 13 minus 1. multiply them to get 72. so we're going to work now in a 72 hour clock and then we're going to pick a prime number which does not divide 72 so we're not allowed to pick two of three because they divide 72 but 5 is allowed so let's say we pick the number 5 that is our encryption value e
9:16
and that is the 5 that we saw before we took 18 to the power 5. so that's an arbitrarily chosen number to some extent but the number 29 is not arbitrarily chosen because what we want to do is we want to valid find a value d such that e in our case 5 times d is equal to 1 on our 72-hour clock
9:39
now finding that by computer is very easy it uses an algorithm called the extended euclidean algorithm i'm going to give you the answer because we know what the answer is going to be it's 29 a computer can find it quickly and indeed if we multiply 5 times 29 what we get is 145 which is one more than 144 and 144 is a multiple of 72 in other words 5 times 29 is indeed equal to 1 on a 72 hour clock and this is where that magic value 29 that we used before comes from so that brings
10:19
us then to the second question how does it work we came up with this magic value 29 and and it
10:29
it has a property that five times 29 is equal to 1 on our 72 hour clock right um so what this means is that if we subtract 1 from 5 times 29 what we end up with is a multiple of 72. now let me just tell you what e times d is without any clocks it's 145. so on a 72 hour clock okay we go once around we go second time around and then we have one hour more okay works perfectly so if we subtract one we end up with the number 144 so 5 times 29 minus 1 is a multiple
11:12
of 72 but that also means it's a multiple of this number six which is seven minus one and it's a multiple of uh 12 which is 13 minus one so eb minus 1 is a multiple of both
11:31
our left prime number minus 1 and our right prime number minus 1 7 and 13 respectively now because it is a multiple uh of both of those numbers for each of them individually we can apply a theorem known as fermat's little theorem fermat was a famous mathematician living hundreds of years ago never having heard of cryptography of course yet his results are very useful today so using that we can actually deduce that this value m to the power e d minus one simplifies to one on our clock
12:06
now because we have this minus one we have one little m left over so what we end up with is one times m which is m uh which is how it cancels out in the end okay so that's quite difficult to to follow i would say but it's quite elegant like things that are not clear somehow fit together as puzzle pieces and they all cancel out and what we end up with is exactly our original value now there's one remaining question is it secure so we know that it works we know why
12:40
our magic numbers are chosen the way they are but the question is is is it secure so how come that i as in this case the university of nottingham am able to deduce this value d but strangers cannot
12:56
now if we look at the way in which the magic numbers were chosen remember that we found the number 72 by taking one prime number seven subtracting one and the other part number thirteen subtracting one and multiplying them how will you do that if you don't know the prime factors of 91
13:14
so you cannot find number 72 simply because you don't know the prime factors of 91 and we established the very beginning that finding prime factors was a difficult problem but computing a number which consists of two prime factors is an easy problem so the university of nottingham came up with two 300 digit prime numbers multiplied them which was relatively easy found the numbers e and d the magic numbers and then forgot about the prime numbers because they are no longer relevant
13:44
and then it's secure because only people that have the numbers p and q will be able to deduce the secret magic numbers and nobody else can know the magic numbers if i go to the site will i see those same magic numbers do you see what i mean so you will see two of the three magic numbers which is the product p times q but you won't know what the original values p and q were
14:10
you will see the number e which in our little problem was in number five but you will not see the other magic value which in our example was the number 29
14:22
so the number e is usually a small number and the number d is usually quite a large number so that's why we found for nottingham that the number e was 65 500 something but the number d which is a secret number could really be any number that is roughly 300 digits long
14:42
we have no idea which number it is you're not going to be able to search them all
14:47
quite quickly 2 to the 16 operations 65 000 operations even on a laptop not going to take very long so i go through and i find all the possible x's that means that any device which is keeping track of time in that way will get really confused and we basically get the millennium [MANUAL PUBLISH]
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat