현재 시간:0:00전체 재생 길이:2:58
0 에너지 포인트
동영상 대본
유클리드는 2000년 전에 모든 수는 하나의 소인수분해 밖에 없다고 증명했고 우리는 이가 비밀의 키 라고 생각할 수 있습니다 소인수분해는 사실 어려운 문제입니다 일단 쉬운것과 어려운것을 시간의 복잡성을 통해 정의해 봅시다 우린 모두 수를 곱해본 적이 있고 계산을 빨리 하기 위해 나름의 규칙을 쓰기도 하죠 반면에 컴퓨터가 수를 곱하는 프로그램을 만들면 인간보다 월등히 빨리 계산할 수 있게 됩니다 이는 컴퓨터가 두 수를 곱하는데 필요한 시간을 표시하는 그래프입니다 그리고 당연히 수가 커질수록 계산하는 시간도 늘겠죠 여기서 계산하는 시간이 1초 미만인 사실을 주의 하세요 꽤 큰 수도 마찬가지입니다 그래서 이 문제는 쉬울겁니다 이제 소인수분해의 문제와 비교해 봅시다 누군가가 589란 숫자를 소인수분해 하라고 하면 문제가 훨씬 어렵다고 느낄겁니다 어떤 전략을 써도 589와 나누어지는 수를 찾을 때까지 어느정도 시행착오가 필요합니다 조금 헤매다 보면 소인수분해가 19 곱하기 39인 것을 찾을 수 있습니다 이제 다시 437,231란 숫자를 소인수분해하라고 시키면 아마도 포기하고 컴퓨터를 사용할 겁니다 작은 숫자에겐 괜찮지만 더욱 큰 수를 컴퓨터에게 소인수분해하라고 하면 통제가 불가능한 상황이 나타납니다 이 계산을 하기 위해 필요한 시간은 수에 따라 급격히 증가합니다 수가 증가하는 만큼 컴퓨터는 몇 분,몇 시간, 그리고 결국엔 몇 백, 몇 천년이 소인수분해하기 위해 필요합니다 따라서 이런 문제는 어렵다고 말하죠 시간의 상승률이 있기 때문입니다 그래서 콕스는 트랩도어로 소인수분해를 사용했습니다 첫째, 앨리스가 150자리의 소수를 무작위로 생산하고 p1이라고 합니다 그리고 크기가 비슷한 둘째의 소수 p2를 생산합니다 그리고 이 두 소수를 곱해서 300자리가 넘는 N이란 수를 얻습니다 이 곱하기 단계는 1초도 안걸리고 인터넷으로도 할 수 있습니다 그 다음 앨리스는 N의 소인수분해인 p1과 p2를 숨깁니다 그리고 N을 누구한테도 줘도 그들은 소인수분해를 찾기위해 몇년간 컴퓨터를 돌려야 됩니다 둘째, 콕스는 N의 소인수분해에 의존하는 함수가 필요했습니다 이를 위해 콕스는 1760년대 스위스 수학자 레온하르트 오일러의 정의를 찾아보았습니다