[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,,유클리드는 2000년 전에
Dialogue: 0,0:00:02.43,0:00:06.00,Default,,0000,0000,0000,,모든 숫자는 하나의 소인수분해 \N밖에 없다고 증명했고
Dialogue: 0,0:00:06.00,0:00:09.11,Default,,0000,0000,0000,,우리는 이가 비밀의 "열쇠"라고\N생각할 수 있습니다.
Dialogue: 0,0:00:09.11,0:00:11.20,Default,,0000,0000,0000,,소인수분해는 사실
Dialogue: 0,0:00:11.20,0:00:14.40,Default,,0000,0000,0000,,어려운 문제입니다.
Dialogue: 0,0:00:14.40,0:00:17.80,Default,,0000,0000,0000,,일단 쉬운것과 어려운것을
Dialogue: 0,0:00:17.80,0:00:21.16,Default,,0000,0000,0000,,"시간의 복잡성"을 통해 정의 해 봅시다.
Dialogue: 0,0:00:21.16,0:00:23.19,Default,,0000,0000,0000,,우린 모두 수를 곱한 적이 있고
Dialogue: 0,0:00:23.19,0:00:25.51,Default,,0000,0000,0000,,계산을 빨리 하기 위해 나름의
Dialogue: 0,0:00:25.51,0:00:27.55,Default,,0000,0000,0000,,규칙을 쓰기도 하죠.
Dialogue: 0,0:00:27.55,0:00:29.88,Default,,0000,0000,0000,,반면에 컴퓨터를 수를 곱하기 위해 \N프로그래밍을 하면
Dialogue: 0,0:00:29.88,0:00:33.48,Default,,0000,0000,0000,,인간보다 월등히 빨리 계산할 수 있게 \N됩니다.
Dialogue: 0,0:00:33.48,0:00:35.80,Default,,0000,0000,0000,,이는 컴퓨터가 두 수를 곱하기 위해 \N필요한 시간을
Dialogue: 0,0:00:35.80,0:00:38.79,Default,,0000,0000,0000,,표시하는 그래프입니다.
Dialogue: 0,0:00:38.79,0:00:41.36,Default,,0000,0000,0000,,그리고 당연히 수가 커질수록
Dialogue: 0,0:00:41.36,0:00:44.50,Default,,0000,0000,0000,,계산하는 시간도 늘겠죠.
Dialogue: 0,0:00:44.50,0:00:46.39,Default,,0000,0000,0000,,여기서 계산하는 시간이
Dialogue: 0,0:00:46.39,0:00:48.39,Default,,0000,0000,0000,,1초 미만인 사실을 주의 하세요.
Dialogue: 0,0:00:48.39,0:00:50.84,Default,,0000,0000,0000,,아무리 수가 커져도 마찬가지입니다.
Dialogue: 0,0:00:50.84,0:00:53.41,Default,,0000,0000,0000,,그래서 이 문제는 "쉬울"겁니다.
Dialogue: 0,0:00:53.41,0:00:56.05,Default,,0000,0000,0000,,이제 소인수분해의 문제와 비교해 \N봅시다.
Dialogue: 0,0:00:56.05,0:00:59.96,Default,,0000,0000,0000,,누군가가 589란 숫자를 소인수분해\N하라고 시키면
Dialogue: 0,0:00:59.96,0:01:02.88,Default,,0000,0000,0000,,훨씬 어려운 문제로 느낄겁니다.
Dialogue: 0,0:01:02.88,0:01:04.66,Default,,0000,0000,0000,,어떤 전략을 써도라도
Dialogue: 0,0:01:04.66,0:01:06.64,Default,,0000,0000,0000,,589와 나누어지는 수를 찾을 때 까지
Dialogue: 0,0:01:06.64,0:01:10.74,Default,,0000,0000,0000,,어느만큼의 시행착오가 필요합니다.
Dialogue: 0,0:01:10.74,0:01:12.42,Default,,0000,0000,0000,,조금 헤매다 보면 소인수분해의
Dialogue: 0,0:01:12.42,0:01:16.74,Default,,0000,0000,0000,,19 곱하기 39가 나올겁니다.
Dialogue: 0,0:01:16.74,0:01:19.14,Default,,0000,0000,0000,,이제 다시 437,231란 숫자를\N소인수분해하라고
Dialogue: 0,0:01:19.14,0:01:24.04,Default,,0000,0000,0000,,시키면 아마도 포기하고
Dialogue: 0,0:01:24.04,0:01:26.44,Default,,0000,0000,0000,,컴퓨터를 사용할 겁니다.
Dialogue: 0,0:01:26.44,0:01:28.23,Default,,0000,0000,0000,,작은 숫자에겐 괜찮지만
Dialogue: 0,0:01:28.23,0:01:29.68,Default,,0000,0000,0000,,더욱 큰 수를 컴퓨터에게
Dialogue: 0,0:01:29.68,0:01:32.45,Default,,0000,0000,0000,,소인수분해하라고 하면
Dialogue: 0,0:01:32.45,0:01:34.90,Default,,0000,0000,0000,,"달아나는"현상이 나타납니다.
Dialogue: 0,0:01:34.90,0:01:37.41,Default,,0000,0000,0000,,이 계산을 하기 위해 필요한 시간은
Dialogue: 0,0:01:37.41,0:01:41.02,Default,,0000,0000,0000,,수에 따라 급격히 증가합니다.
Dialogue: 0,0:01:41.02,0:01:43.63,Default,,0000,0000,0000,,수가 증가하는 만큼 컴퓨터는 \N몇분,
Dialogue: 0,0:01:43.63,0:01:45.97,Default,,0000,0000,0000,,몇 시간, 그리고 결국엔
Dialogue: 0,0:01:45.97,0:01:50.21,Default,,0000,0000,0000,,백, 또는 천년이 소인수분해하기 위해\N필요합니다.
Dialogue: 0,0:01:50.21,0:01:53.55,Default,,0000,0000,0000,,따라서 이런 문제는 "어렵"다고 말하죠.
Dialogue: 0,0:01:53.55,0:01:57.57,Default,,0000,0000,0000,,왜냐하면 이러한 시간의 상승률이 있기 \N때문입니다.
Dialogue: 0,0:01:57.57,0:01:59.68,Default,,0000,0000,0000,,그래서 콕스는 트랩도어의의 \N해결책을
Dialogue: 0,0:01:59.68,0:02:01.95,Default,,0000,0000,0000,,소인수분해를 사용해 썼습니다.
Dialogue: 0,0:02:01.95,0:02:05.36,Default,,0000,0000,0000,,첫째, 알리스가 150자리의 \N소수를
Dialogue: 0,0:02:05.36,0:02:08.09,Default,,0000,0000,0000,,무작위로 생산하고
Dialogue: 0,0:02:08.09,0:02:09.86,Default,,0000,0000,0000,,이를 p1이라고 부릅니다.
Dialogue: 0,0:02:09.86,0:02:12.03,Default,,0000,0000,0000,,그리고 크기가 비슷한
Dialogue: 0,0:02:12.03,0:02:15.04,Default,,0000,0000,0000,,둘째의 소수 p2를 생산합니다.
Dialogue: 0,0:02:15.04,0:02:18.20,Default,,0000,0000,0000,,그리고 이 두 소수를 곱해서
Dialogue: 0,0:02:18.20,0:02:20.50,Default,,0000,0000,0000,,300자리가 넘는
Dialogue: 0,0:02:20.50,0:02:23.46,Default,,0000,0000,0000,,N이란 수를 얻습니다.
Dialogue: 0,0:02:23.46,0:02:26.55,Default,,0000,0000,0000,,이 곱하기 단계는 1초도 안걸리고
Dialogue: 0,0:02:26.55,0:02:30.06,Default,,0000,0000,0000,,인터넷으로도 할 수 있습니다.
Dialogue: 0,0:02:30.07,0:02:32.14,Default,,0000,0000,0000,,그다음 앨리스는 N의 소인수분해인
Dialogue: 0,0:02:32.14,0:02:35.43,Default,,0000,0000,0000,,p1과 p2를 숨깁니다.
Dialogue: 0,0:02:35.43,0:02:38.20,Default,,0000,0000,0000,,그리고 N을 누구한테도 줘도
Dialogue: 0,0:02:38.20,0:02:39.70,Default,,0000,0000,0000,,그들은 소인수분해를 찾기위해
Dialogue: 0,0:02:39.70,0:02:42.43,Default,,0000,0000,0000,,몇년간 컴퓨터를 돌려야 됩니다.
Dialogue: 0,0:02:43.11,0:02:45.98,Default,,0000,0000,0000,,둘째, 콕스는 N의 소인수분해에
Dialogue: 0,0:02:45.98,0:02:50.15,Default,,0000,0000,0000,,의존하는 함수가 필요했습니다.
Dialogue: 0,0:02:50.15,0:02:53.11,Default,,0000,0000,0000,,그리고 이를 위해 콕스는\N1760년대 스위스 수학자
Dialogue: 0,0:02:53.11,0:02:56.91,Default,,0000,0000,0000,,레온하르트 오일러의 정의를 찾아보았습니다