0:00:00.181,0:00:02.434 - [Voiceover] Over 2,000[br]years ago, Euclid showed 0:00:02.434,0:00:06.002 every number has exactly[br]one prime factorization, 0:00:06.002,0:00:09.106 which we can think of as a secret key. 0:00:09.106,0:00:11.204 It turns out that prime factorization 0:00:11.204,0:00:14.403 is a fundamentally hard problem. 0:00:14.403,0:00:17.795 Let's clarify what we[br]mean by "easy" and "hard", 0:00:17.795,0:00:21.162 by introducing what's[br]called "time complexity". 0:00:21.162,0:00:23.186 We have all multiplied numbers before, 0:00:23.186,0:00:25.507 and each of us our own rules for doing so, 0:00:25.507,0:00:27.554 in order to speed things up. 0:00:27.554,0:00:29.875 If we program a computer[br]to multiply numbers, 0:00:29.875,0:00:33.475 it can do so much faster[br]than any human can. 0:00:33.475,0:00:35.796 Here is a graph that[br]shows the time required 0:00:35.796,0:00:38.786 for a computer to multiply two numbers. 0:00:38.786,0:00:41.363 And, of course, the time[br]required to find the answer 0:00:41.363,0:00:44.499 increases as the numbers get larger. 0:00:44.499,0:00:46.387 Notice that the computation time 0:00:46.387,0:00:48.387 stays well under one second, 0:00:48.387,0:00:50.835 even with fairly large numbers. 0:00:50.835,0:00:53.413 Therefore, it is "easy" to perform. 0:00:53.413,0:00:56.050 Now, compare this to prime factorization. 0:00:56.050,0:00:59.956 If someone told you to find[br]the prime factorization of 589, 0:00:59.956,0:01:02.882 you will notice the problem feels harder. 0:01:02.882,0:01:04.660 No matter what your strategy, 0:01:04.660,0:01:06.640 it will require some trial and error 0:01:06.640,0:01:10.739 until you find a number[br]which evenly divides 589. 0:01:10.739,0:01:12.419 After some struggle, you will find 0:01:12.419,0:01:16.742 19 times 31 is the prime factorization. 0:01:16.742,0:01:19.139 If you were told to find[br]the prime factorization 0:01:19.139,0:01:24.035 of 437, 231, you'd probably give up 0:01:24.035,0:01:26.435 and get a computer to help you. 0:01:26.435,0:01:28.230 This works fine for small numbers, 0:01:28.230,0:01:29.675 though if we try to get a computer 0:01:29.675,0:01:32.452 to factor larger and larger numbers, 0:01:32.452,0:01:34.902 there is a runaway effect. 0:01:34.902,0:01:37.411 The time needed to[br]perform the calculations 0:01:37.411,0:01:41.024 increases rapidly, as there[br]are more steps involved. 0:01:41.024,0:01:43.632 As the numbers grow, the[br]computer needs minutes, 0:01:43.632,0:01:45.968 then hours, and eventually it will require 0:01:45.968,0:01:50.208 hundreds, or thousands of[br]years to factor huge numbers. 0:01:50.208,0:01:53.547 We therefore say it is a "hard" problem 0:01:53.547,0:01:57.568 due to this growth rate of[br]time needed to solve it. 0:01:57.568,0:01:59.681 So factorization is what Cocks used 0:01:59.681,0:02:01.952 to build the trapdoor solution. 0:02:01.952,0:02:05.361 Step one, imagine Alice randomly generated 0:02:05.361,0:02:08.086 a prime number over 150 digits long; 0:02:08.086,0:02:09.860 call this "p one". 0:02:09.860,0:02:12.032 Then, a second randon prime number 0:02:12.032,0:02:15.041 roughly the same size; call this "p two". 0:02:15.041,0:02:18.197 She then multiplies[br]these two primes together 0:02:18.197,0:02:20.496 to get a composite number, N, 0:02:20.496,0:02:23.456 which is over 300 digits long. 0:02:23.456,0:02:26.553 This multiplication step[br]would take less than second; 0:02:26.553,0:02:30.055 we could even do it in a web browser. 0:02:30.070,0:02:32.137 Then, she takes the factorization of N, 0:02:32.137,0:02:35.432 p one times p two, and hides it. 0:02:35.432,0:02:38.202 Now, if she gave N to anyone else, 0:02:38.202,0:02:39.703 they would have to have a computer running 0:02:39.703,0:02:42.433 for years to find the solution. 0:02:43.113,0:02:45.976 Step two, Cocks needed to find a function 0:02:45.976,0:02:50.153 which depends on knowing[br]the factorization of N. 0:02:50.153,0:02:53.113 For this, he looked back[br]to work done in 1760 0:02:53.113,0:02:56.912 by Swiss mathematician, Leonhard Euler.