1
00:00:00,181 --> 00:00:02,434
유클리드는 2000년 전에

2
00:00:02,434 --> 00:00:06,002
모든 숫자는 하나의 소인수분해 
밖에 없다고 증명했고

3
00:00:06,002 --> 00:00:09,106
우리는 이가 비밀의 "열쇠"라고
생각할 수 있습니다.

4
00:00:09,106 --> 00:00:11,204
소인수분해는 사실

5
00:00:11,204 --> 00:00:14,403
어려운 문제입니다.

6
00:00:14,403 --> 00:00:17,795
일단 쉬운것과 어려운것을

7
00:00:17,795 --> 00:00:21,162
"시간의 복잡성"을 통해 정의 해 봅시다.

8
00:00:21,162 --> 00:00:23,186
우린 모두 수를 곱한 적이 있고

9
00:00:23,186 --> 00:00:25,507
계산을 빨리 하기 위해 나름의

10
00:00:25,507 --> 00:00:27,554
규칙을 쓰기도 하죠.

11
00:00:27,554 --> 00:00:29,875
반면에 컴퓨터를 수를 곱하기 위해 
프로그래밍을 하면

12
00:00:29,875 --> 00:00:33,475
인간보다 월등히 빨리 계산할 수 있게 
됩니다.

13
00:00:33,475 --> 00:00:35,796
이는 컴퓨터가 두 수를 곱하기 위해 
필요한 시간을

14
00:00:35,796 --> 00:00:38,786
표시하는 그래프입니다.

15
00:00:38,786 --> 00:00:41,363
그리고 당연히 수가 커질수록

16
00:00:41,363 --> 00:00:44,499
계산하는 시간도 늘겠죠.

17
00:00:44,499 --> 00:00:46,387
여기서 계산하는 시간이

18
00:00:46,387 --> 00:00:48,387
1초 미만인 사실을 주의 하세요.

19
00:00:48,387 --> 00:00:50,835
아무리 수가 커져도 마찬가지입니다.

20
00:00:50,835 --> 00:00:53,413
그래서 이 문제는 "쉬울"겁니다.

21
00:00:53,413 --> 00:00:56,050
이제 소인수분해의 문제와 비교해 
봅시다.

22
00:00:56,050 --> 00:00:59,956
누군가가 589란 숫자를 소인수분해
하라고 시키면

23
00:00:59,956 --> 00:01:02,882
훨씬 어려운 문제로 느낄겁니다.

24
00:01:02,882 --> 00:01:04,660
어떤 전략을 써도라도

25
00:01:04,660 --> 00:01:06,640
589와 나누어지는 수를 찾을 때 까지

26
00:01:06,640 --> 00:01:10,739
어느만큼의 시행착오가 필요합니다.

27
00:01:10,739 --> 00:01:12,419
조금 헤매다 보면 소인수분해의

28
00:01:12,419 --> 00:01:16,742
19 곱하기 39가 나올겁니다.

29
00:01:16,742 --> 00:01:19,139
이제 다시 437,231란 숫자를
소인수분해하라고

30
00:01:19,139 --> 00:01:24,035
시키면 아마도 포기하고

31
00:01:24,035 --> 00:01:26,435
컴퓨터를 사용할 겁니다.

32
00:01:26,435 --> 00:01:28,230
작은 숫자에겐 괜찮지만

33
00:01:28,230 --> 00:01:29,675
더욱 큰 수를 컴퓨터에게

34
00:01:29,675 --> 00:01:32,452
소인수분해하라고 하면

35
00:01:32,452 --> 00:01:34,902
"달아나는"현상이 나타납니다.

36
00:01:34,902 --> 00:01:37,411
이 계산을 하기 위해 필요한 시간은

37
00:01:37,411 --> 00:01:41,024
수에 따라 급격히 증가합니다.

38
00:01:41,024 --> 00:01:43,632
수가 증가하는 만큼 컴퓨터는 
몇분,

39
00:01:43,632 --> 00:01:45,968
몇 시간, 그리고 결국엔

40
00:01:45,968 --> 00:01:50,208
백, 또는 천년이 소인수분해하기 위해
필요합니다.

41
00:01:50,208 --> 00:01:53,547
따라서 이런 문제는 "어렵"다고 말하죠.

42
00:01:53,547 --> 00:01:57,568
왜냐하면 이러한 시간의 상승률이 있기 
때문입니다.

43
00:01:57,568 --> 00:01:59,681
그래서 콕스는 트랩도어의의 
해결책을

44
00:01:59,681 --> 00:02:01,952
소인수분해를 사용해 썼습니다.

45
00:02:01,952 --> 00:02:05,361
첫째, 알리스가 150자리의 
소수를

46
00:02:05,361 --> 00:02:08,086
무작위로 생산하고

47
00:02:08,086 --> 00:02:09,860
이를 p1이라고 부릅니다.

48
00:02:09,860 --> 00:02:12,032
그리고 크기가 비슷한

49
00:02:12,032 --> 00:02:15,041
둘째의 소수 p2를 생산합니다.

50
00:02:15,041 --> 00:02:18,197
그리고 이 두 소수를 곱해서

51
00:02:18,197 --> 00:02:20,496
300자리가 넘는

52
00:02:20,496 --> 00:02:23,456
N이란 수를 얻습니다.

53
00:02:23,456 --> 00:02:26,553
이 곱하기 단계는 1초도 안걸리고

54
00:02:26,553 --> 00:02:30,055
인터넷으로도 할 수 있습니다.

55
00:02:30,070 --> 00:02:32,137
그다음 앨리스는 N의 소인수분해인

56
00:02:32,137 --> 00:02:35,432
p1과 p2를 숨깁니다.

57
00:02:35,432 --> 00:02:38,202
그리고 N을 누구한테도 줘도

58
00:02:38,202 --> 00:02:39,703
그들은 소인수분해를 찾기위해

59
00:02:39,703 --> 00:02:42,433
몇년간 컴퓨터를 돌려야 됩니다.

60
00:02:43,113 --> 00:02:45,976
둘째, 콕스는 N의 소인수분해에

61
00:02:45,976 --> 00:02:50,153
의존하는 함수가 필요했습니다.

62
00:02:50,153 --> 00:02:53,113
그리고 이를 위해 콕스는
1760년대 스위스 수학자

63
00:02:53,113 --> 00:02:56,912
레온하르트 오일러의 정의를 찾아보았습니다