0:00:00.181,0:00:02.434 유클리드는 2000년 전에 0:00:02.434,0:00:06.002 모든 숫자는 하나의 소인수분해 [br]밖에 없다고 증명했고 0:00:06.002,0:00:09.106 우리는 이가 비밀의 "열쇠"라고[br]생각할 수 있습니다. 0:00:09.106,0:00:11.204 소인수분해는 사실 0:00:11.204,0:00:14.403 어려운 문제입니다. 0:00:14.403,0:00:17.795 일단 쉬운것과 어려운것을 0:00:17.795,0:00:21.162 "시간의 복잡성"을 통해 정의 해 봅시다. 0:00:21.162,0:00:23.186 우린 모두 수를 곱한 적이 있고 0:00:23.186,0:00:25.507 계산을 빨리 하기 위해 나름의 0:00:25.507,0:00:27.554 규칙을 쓰기도 하죠. 0:00:27.554,0:00:29.875 반면에 컴퓨터를 수를 곱하기 위해 [br]프로그래밍을 하면 0:00:29.875,0:00:33.475 인간보다 월등히 빨리 계산할 수 있게 [br]됩니다. 0:00:33.475,0:00:35.796 이는 컴퓨터가 두 수를 곱하기 위해 [br]필요한 시간을 0:00:35.796,0:00:38.786 표시하는 그래프입니다. 0:00:38.786,0:00:41.363 그리고 당연히 수가 커질수록 0:00:41.363,0:00:44.499 계산하는 시간도 늘겠죠. 0:00:44.499,0:00:46.387 여기서 계산하는 시간이 0:00:46.387,0:00:48.387 1초 미만인 사실을 주의 하세요. 0:00:48.387,0:00:50.835 아무리 수가 커져도 마찬가지입니다. 0:00:50.835,0:00:53.413 그래서 이 문제는 "쉬울"겁니다. 0:00:53.413,0:00:56.050 이제 소인수분해의 문제와 비교해 [br]봅시다. 0:00:56.050,0:00:59.956 누군가가 589란 숫자를 소인수분해[br]하라고 시키면 0:00:59.956,0:01:02.882 훨씬 어려운 문제로 느낄겁니다. 0:01:02.882,0:01:04.660 어떤 전략을 써도라도 0:01:04.660,0:01:06.640 589와 나누어지는 수를 찾을 때 까지 0:01:06.640,0:01:10.739 어느만큼의 시행착오가 필요합니다. 0:01:10.739,0:01:12.419 조금 헤매다 보면 소인수분해의 0:01:12.419,0:01:16.742 19 곱하기 39가 나올겁니다. 0:01:16.742,0:01:19.139 이제 다시 437,231란 숫자를[br]소인수분해하라고 0:01:19.139,0:01:24.035 시키면 아마도 포기하고 0:01:24.035,0:01:26.435 컴퓨터를 사용할 겁니다. 0:01:26.435,0:01:28.230 작은 숫자에겐 괜찮지만 0:01:28.230,0:01:29.675 더욱 큰 수를 컴퓨터에게 0:01:29.675,0:01:32.452 소인수분해하라고 하면 0:01:32.452,0:01:34.902 "달아나는"현상이 나타납니다. 0:01:34.902,0:01:37.411 이 계산을 하기 위해 필요한 시간은 0:01:37.411,0:01:41.024 수에 따라 급격히 증가합니다. 0:01:41.024,0:01:43.632 수가 증가하는 만큼 컴퓨터는 [br]몇분, 0:01:43.632,0:01:45.968 몇 시간, 그리고 결국엔 0:01:45.968,0:01:50.208 백, 또는 천년이 소인수분해하기 위해[br]필요합니다. 0:01:50.208,0:01:53.547 따라서 이런 문제는 "어렵"다고 말하죠. 0:01:53.547,0:01:57.568 왜냐하면 이러한 시간의 상승률이 있기 [br]때문입니다. 0:01:57.568,0:01:59.681 그래서 콕스는 트랩도어의의 [br]해결책을 0:01:59.681,0:02:01.952 소인수분해를 사용해 썼습니다. 0:02:01.952,0:02:05.361 첫째, 알리스가 150자리의 [br]소수를 0:02:05.361,0:02:08.086 무작위로 생산하고 0:02:08.086,0:02:09.860 이를 p1이라고 부릅니다. 0:02:09.860,0:02:12.032 그리고 크기가 비슷한 0:02:12.032,0:02:15.041 둘째의 소수 p2를 생산합니다. 0:02:15.041,0:02:18.197 그리고 이 두 소수를 곱해서 0:02:18.197,0:02:20.496 300자리가 넘는 0:02:20.496,0:02:23.456 N이란 수를 얻습니다. 0:02:23.456,0:02:26.553 이 곱하기 단계는 1초도 안걸리고 0:02:26.553,0:02:30.055 인터넷으로도 할 수 있습니다. 0:02:30.070,0:02:32.137 그다음 앨리스는 N의 소인수분해인 0:02:32.137,0:02:35.432 p1과 p2를 숨깁니다. 0:02:35.432,0:02:38.202 그리고 N을 누구한테도 줘도 0:02:38.202,0:02:39.703 그들은 소인수분해를 찾기위해 0:02:39.703,0:02:42.433 몇년간 컴퓨터를 돌려야 됩니다. 0:02:43.113,0:02:45.976 둘째, 콕스는 N의 소인수분해에 0:02:45.976,0:02:50.153 의존하는 함수가 필요했습니다. 0:02:50.153,0:02:53.113 그리고 이를 위해 콕스는[br]1760년대 스위스 수학자 0:02:53.113,0:02:56.912 레온하르트 오일러의 정의를 찾아보았습니다