[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.18,0:00:02.43,Default,,0000,0000,0000,,- [Voiceover] Over 2,000\Nyears ago, Euclid showed
Dialogue: 0,0:00:02.43,0:00:06.00,Default,,0000,0000,0000,,every number has exactly\None prime factorization,
Dialogue: 0,0:00:06.00,0:00:09.11,Default,,0000,0000,0000,,which we can think of as a secret key.
Dialogue: 0,0:00:09.11,0:00:11.20,Default,,0000,0000,0000,,It turns out that prime factorization
Dialogue: 0,0:00:11.20,0:00:14.40,Default,,0000,0000,0000,,is a fundamentally hard problem.
Dialogue: 0,0:00:14.40,0:00:17.80,Default,,0000,0000,0000,,Let's clarify what we\Nmean by "easy" and "hard",
Dialogue: 0,0:00:17.80,0:00:21.16,Default,,0000,0000,0000,,by introducing what's\Ncalled "time complexity".
Dialogue: 0,0:00:21.16,0:00:23.19,Default,,0000,0000,0000,,We have all multiplied numbers before,
Dialogue: 0,0:00:23.19,0:00:25.51,Default,,0000,0000,0000,,and each of us our own rules for doing so,
Dialogue: 0,0:00:25.51,0:00:27.55,Default,,0000,0000,0000,,in order to speed things up.
Dialogue: 0,0:00:27.55,0:00:29.88,Default,,0000,0000,0000,,If we program a computer\Nto multiply numbers,
Dialogue: 0,0:00:29.88,0:00:33.48,Default,,0000,0000,0000,,it can do so much faster\Nthan any human can.
Dialogue: 0,0:00:33.48,0:00:35.80,Default,,0000,0000,0000,,Here is a graph that\Nshows the time required
Dialogue: 0,0:00:35.80,0:00:38.79,Default,,0000,0000,0000,,for a computer to multiply two numbers.
Dialogue: 0,0:00:38.79,0:00:41.36,Default,,0000,0000,0000,,And, of course, the time\Nrequired to find the answer
Dialogue: 0,0:00:41.36,0:00:44.50,Default,,0000,0000,0000,,increases as the numbers get larger.
Dialogue: 0,0:00:44.50,0:00:46.39,Default,,0000,0000,0000,,Notice that the computation time
Dialogue: 0,0:00:46.39,0:00:48.39,Default,,0000,0000,0000,,stays well under one second,
Dialogue: 0,0:00:48.39,0:00:50.84,Default,,0000,0000,0000,,even with fairly large numbers.
Dialogue: 0,0:00:50.84,0:00:53.41,Default,,0000,0000,0000,,Therefore, it is "easy" to perform.
Dialogue: 0,0:00:53.41,0:00:56.05,Default,,0000,0000,0000,,Now, compare this to prime factorization.
Dialogue: 0,0:00:56.05,0:00:59.96,Default,,0000,0000,0000,,If someone told you to find\Nthe prime factorization of 589,
Dialogue: 0,0:00:59.96,0:01:02.88,Default,,0000,0000,0000,,you will notice the problem feels harder.
Dialogue: 0,0:01:02.88,0:01:04.66,Default,,0000,0000,0000,,No matter what your strategy,
Dialogue: 0,0:01:04.66,0:01:06.64,Default,,0000,0000,0000,,it will require some trial and error
Dialogue: 0,0:01:06.64,0:01:10.74,Default,,0000,0000,0000,,until you find a number\Nwhich evenly divides 589.
Dialogue: 0,0:01:10.74,0:01:12.42,Default,,0000,0000,0000,,After some struggle, you will find
Dialogue: 0,0:01:12.42,0:01:16.74,Default,,0000,0000,0000,,19 times 31 is the prime factorization.
Dialogue: 0,0:01:16.74,0:01:19.14,Default,,0000,0000,0000,,If you were told to find\Nthe prime factorization
Dialogue: 0,0:01:19.14,0:01:24.04,Default,,0000,0000,0000,,of 437, 231, you'd probably give up
Dialogue: 0,0:01:24.04,0:01:26.44,Default,,0000,0000,0000,,and get a computer to help you.
Dialogue: 0,0:01:26.44,0:01:28.23,Default,,0000,0000,0000,,This works fine for small numbers,
Dialogue: 0,0:01:28.23,0:01:29.68,Default,,0000,0000,0000,,though if we try to get a computer
Dialogue: 0,0:01:29.68,0:01:32.45,Default,,0000,0000,0000,,to factor larger and larger numbers,
Dialogue: 0,0:01:32.45,0:01:34.90,Default,,0000,0000,0000,,there is a runaway effect.
Dialogue: 0,0:01:34.90,0:01:37.41,Default,,0000,0000,0000,,The time needed to\Nperform the calculations
Dialogue: 0,0:01:37.41,0:01:41.02,Default,,0000,0000,0000,,increases rapidly, as there\Nare more steps involved.
Dialogue: 0,0:01:41.02,0:01:43.63,Default,,0000,0000,0000,,As the numbers grow, the\Ncomputer needs minutes,
Dialogue: 0,0:01:43.63,0:01:45.97,Default,,0000,0000,0000,,then hours, and eventually it will require
Dialogue: 0,0:01:45.97,0:01:50.21,Default,,0000,0000,0000,,hundreds, or thousands of\Nyears to factor huge numbers.
Dialogue: 0,0:01:50.21,0:01:53.55,Default,,0000,0000,0000,,We therefore say it is a "hard" problem
Dialogue: 0,0:01:53.55,0:01:57.57,Default,,0000,0000,0000,,due to this growth rate of\Ntime needed to solve it.
Dialogue: 0,0:01:57.57,0:01:59.68,Default,,0000,0000,0000,,So factorization is what Cocks used
Dialogue: 0,0:01:59.68,0:02:01.95,Default,,0000,0000,0000,,to build the trapdoor solution.
Dialogue: 0,0:02:01.95,0:02:05.36,Default,,0000,0000,0000,,Step one, imagine Alice randomly generated
Dialogue: 0,0:02:05.36,0:02:08.09,Default,,0000,0000,0000,,a prime number over 150 digits long;
Dialogue: 0,0:02:08.09,0:02:09.86,Default,,0000,0000,0000,,call this "p one".
Dialogue: 0,0:02:09.86,0:02:12.03,Default,,0000,0000,0000,,Then, a second randon prime number
Dialogue: 0,0:02:12.03,0:02:15.04,Default,,0000,0000,0000,,roughly the same size; call this "p two".
Dialogue: 0,0:02:15.04,0:02:18.20,Default,,0000,0000,0000,,She then multiplies\Nthese two primes together
Dialogue: 0,0:02:18.20,0:02:20.50,Default,,0000,0000,0000,,to get a composite number, N,
Dialogue: 0,0:02:20.50,0:02:23.46,Default,,0000,0000,0000,,which is over 300 digits long.
Dialogue: 0,0:02:23.46,0:02:26.55,Default,,0000,0000,0000,,This multiplication step\Nwould take less than second;
Dialogue: 0,0:02:26.55,0:02:30.06,Default,,0000,0000,0000,,we could even do it in a web browser.
Dialogue: 0,0:02:30.07,0:02:32.14,Default,,0000,0000,0000,,Then, she takes the factorization of N,
Dialogue: 0,0:02:32.14,0:02:35.43,Default,,0000,0000,0000,,p one times p two, and hides it.
Dialogue: 0,0:02:35.43,0:02:38.20,Default,,0000,0000,0000,,Now, if she gave N to anyone else,
Dialogue: 0,0:02:38.20,0:02:39.70,Default,,0000,0000,0000,,they would have to have a computer running
Dialogue: 0,0:02:39.70,0:02:42.43,Default,,0000,0000,0000,,for years to find the solution.
Dialogue: 0,0:02:43.11,0:02:45.98,Default,,0000,0000,0000,,Step two, Cocks needed to find a function
Dialogue: 0,0:02:45.98,0:02:50.15,Default,,0000,0000,0000,,which depends on knowing\Nthe factorization of N.
Dialogue: 0,0:02:50.15,0:02:53.11,Default,,0000,0000,0000,,For this, he looked back\Nto work done in 1760
Dialogue: 0,0:02:53.11,0:02:56.91,Default,,0000,0000,0000,,by Swiss mathematician, Leonhard Euler.