WEBVTT

00:00:00.181 --> 00:00:02.434
유클리드는 2000년 전에

00:00:02.434 --> 00:00:06.002
모든 숫자는 하나의 소인수분해 
밖에 없다고 증명했고

00:00:06.002 --> 00:00:09.106
우리는 이가 비밀의 "열쇠"라고
생각할 수 있습니다.

00:00:09.106 --> 00:00:11.204
소인수분해는 사실

00:00:11.204 --> 00:00:14.403
어려운 문제입니다.

00:00:14.403 --> 00:00:17.795
일단 쉬운것과 어려운것을

00:00:17.795 --> 00:00:21.162
"시간의 복잡성"을 통해 정의 해 봅시다.

00:00:21.162 --> 00:00:23.186
우린 모두 수를 곱한 적이 있고

00:00:23.186 --> 00:00:25.507
계산을 빨리 하기 위해 나름의

00:00:25.507 --> 00:00:27.554
규칙을 쓰기도 하죠.

00:00:27.554 --> 00:00:29.875
반면에 컴퓨터를 수를 곱하기 위해 
프로그래밍을 하면

00:00:29.875 --> 00:00:33.475
인간보다 월등히 빨리 계산할 수 있게 
됩니다.

00:00:33.475 --> 00:00:35.796
이는 컴퓨터가 두 수를 곱하기 위해 
필요한 시간을

00:00:35.796 --> 00:00:38.786
표시하는 그래프입니다.

00:00:38.786 --> 00:00:41.363
그리고 당연히 수가 커질수록

00:00:41.363 --> 00:00:44.499
계산하는 시간도 늘겠죠.

00:00:44.499 --> 00:00:46.387
여기서 계산하는 시간이

00:00:46.387 --> 00:00:48.387
1초 미만인 사실을 주의 하세요.

00:00:48.387 --> 00:00:50.835
아무리 수가 커져도 마찬가지입니다.

00:00:50.835 --> 00:00:53.413
그래서 이 문제는 "쉬울"겁니다.

00:00:53.413 --> 00:00:56.050
이제 소인수분해의 문제와 비교해 
봅시다.

00:00:56.050 --> 00:00:59.956
누군가가 589란 숫자를 소인수분해
하라고 시키면

00:00:59.956 --> 00:01:02.882
훨씬 어려운 문제로 느낄겁니다.

00:01:02.882 --> 00:01:04.660
어떤 전략을 써도라도

00:01:04.660 --> 00:01:06.640
589와 나누어지는 수를 찾을 때 까지

00:01:06.640 --> 00:01:10.739
어느만큼의 시행착오가 필요합니다.

00:01:10.739 --> 00:01:12.419
조금 헤매다 보면 소인수분해의

00:01:12.419 --> 00:01:16.742
19 곱하기 39가 나올겁니다.

00:01:16.742 --> 00:01:19.139
이제 다시 437,231란 숫자를
소인수분해하라고

00:01:19.139 --> 00:01:24.035
시키면 아마도 포기하고

00:01:24.035 --> 00:01:26.435
컴퓨터를 사용할 겁니다.

00:01:26.435 --> 00:01:28.230
작은 숫자에겐 괜찮지만

00:01:28.230 --> 00:01:29.675
더욱 큰 수를 컴퓨터에게

00:01:29.675 --> 00:01:32.452
소인수분해하라고 하면

00:01:32.452 --> 00:01:34.902
"달아나는"현상이 나타납니다.

00:01:34.902 --> 00:01:37.411
이 계산을 하기 위해 필요한 시간은

00:01:37.411 --> 00:01:41.024
수에 따라 급격히 증가합니다.

00:01:41.024 --> 00:01:43.632
수가 증가하는 만큼 컴퓨터는 
몇분,

00:01:43.632 --> 00:01:45.968
몇 시간, 그리고 결국엔

00:01:45.968 --> 00:01:50.208
백, 또는 천년이 소인수분해하기 위해
필요합니다.

00:01:50.208 --> 00:01:53.547
따라서 이런 문제는 "어렵"다고 말하죠.

00:01:53.547 --> 00:01:57.568
왜냐하면 이러한 시간의 상승률이 있기 
때문입니다.

00:01:57.568 --> 00:01:59.681
그래서 콕스는 트랩도어의의 
해결책을

00:01:59.681 --> 00:02:01.952
소인수분해를 사용해 썼습니다.

00:02:01.952 --> 00:02:05.361
첫째, 알리스가 150자리의 
소수를

00:02:05.361 --> 00:02:08.086
무작위로 생산하고

00:02:08.086 --> 00:02:09.860
이를 p1이라고 부릅니다.

00:02:09.860 --> 00:02:12.032
그리고 크기가 비슷한

00:02:12.032 --> 00:02:15.041
둘째의 소수 p2를 생산합니다.

00:02:15.041 --> 00:02:18.197
그리고 이 두 소수를 곱해서

00:02:18.197 --> 00:02:20.496
300자리가 넘는

00:02:20.496 --> 00:02:23.456
N이란 수를 얻습니다.

00:02:23.456 --> 00:02:26.553
이 곱하기 단계는 1초도 안걸리고

00:02:26.553 --> 00:02:30.055
인터넷으로도 할 수 있습니다.

00:02:30.070 --> 00:02:32.137
그다음 앨리스는 N의 소인수분해인

00:02:32.137 --> 00:02:35.432
p1과 p2를 숨깁니다.

00:02:35.432 --> 00:02:38.202
그리고 N을 누구한테도 줘도

00:02:38.202 --> 00:02:39.703
그들은 소인수분해를 찾기위해

00:02:39.703 --> 00:02:42.433
몇년간 컴퓨터를 돌려야 됩니다.

00:02:43.113 --> 00:02:45.976
둘째, 콕스는 N의 소인수분해에

00:02:45.976 --> 00:02:50.153
의존하는 함수가 필요했습니다.

00:02:50.153 --> 00:02:53.113
그리고 이를 위해 콕스는
1760년대 스위스 수학자

00:02:53.113 --> 00:02:56.912
레온하르트 오일러의 정의를 찾아보았습니다