유클리드는 2000년 전에

모든 숫자는 하나의 소인수분해 
밖에 없다고 증명했고

우리는 이가 비밀의 "열쇠"라고
생각할 수 있습니다.

소인수분해는 사실

어려운 문제입니다.

일단 쉬운것과 어려운것을

"시간의 복잡성"을 통해 정의 해 봅시다.

우린 모두 수를 곱한 적이 있고

계산을 빨리 하기 위해 나름의

규칙을 쓰기도 하죠.

반면에 컴퓨터를 수를 곱하기 위해 
프로그래밍을 하면

인간보다 월등히 빨리 계산할 수 있게 
됩니다.

이는 컴퓨터가 두 수를 곱하기 위해 
필요한 시간을

표시하는 그래프입니다.

그리고 당연히 수가 커질수록

계산하는 시간도 늘겠죠.

여기서 계산하는 시간이

1초 미만인 사실을 주의 하세요.

아무리 수가 커져도 마찬가지입니다.

그래서 이 문제는 "쉬울"겁니다.

이제 소인수분해의 문제와 비교해 
봅시다.

누군가가 589란 숫자를 소인수분해
하라고 시키면

훨씬 어려운 문제로 느낄겁니다.

어떤 전략을 써도라도

589와 나누어지는 수를 찾을 때 까지

어느만큼의 시행착오가 필요합니다.

조금 헤매다 보면 소인수분해의

19 곱하기 39가 나올겁니다.

이제 다시 437,231란 숫자를
소인수분해하라고

시키면 아마도 포기하고

컴퓨터를 사용할 겁니다.

작은 숫자에겐 괜찮지만

더욱 큰 수를 컴퓨터에게

소인수분해하라고 하면

"달아나는"현상이 나타납니다.

이 계산을 하기 위해 필요한 시간은

수에 따라 급격히 증가합니다.

수가 증가하는 만큼 컴퓨터는 
몇분,

몇 시간, 그리고 결국엔

백, 또는 천년이 소인수분해하기 위해
필요합니다.

따라서 이런 문제는 "어렵"다고 말하죠.

왜냐하면 이러한 시간의 상승률이 있기 
때문입니다.

그래서 콕스는 트랩도어의의 
해결책을

소인수분해를 사용해 썼습니다.

첫째, 알리스가 150자리의 
소수를

무작위로 생산하고

이를 p1이라고 부릅니다.

그리고 크기가 비슷한

둘째의 소수 p2를 생산합니다.

그리고 이 두 소수를 곱해서

300자리가 넘는

N이란 수를 얻습니다.

이 곱하기 단계는 1초도 안걸리고

인터넷으로도 할 수 있습니다.

그다음 앨리스는 N의 소인수분해인

p1과 p2를 숨깁니다.

그리고 N을 누구한테도 줘도

그들은 소인수분해를 찾기위해

몇년간 컴퓨터를 돌려야 됩니다.

둘째, 콕스는 N의 소인수분해에

의존하는 함수가 필요했습니다.

그리고 이를 위해 콕스는
1760년대 스위스 수학자

레온하르트 오일러의 정의를 찾아보았습니다