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