요약

축하드립니다 이제 이번 수업의 분기점에 가까워 졌습니다 지금까지 몇몇의 서로 다른 아이디어들이 소개되었고 여러가지 방향들 중에서 앞으로 움직이기 전에 우리 스스로의 방향을 정하는 것이 중요합니다 그럼 무엇이 이 강의의 계기가 되었을까요? 우리는 RSA 암호화에 대해 배웠고 RSA는 두 가지 사실에 의존하고 있습니다 첫 번째는 소인수분해는 어렵다는 것 만일 큰 소수 P1과 P2를 곱해서 만든 N을 여러분에게 드렸다면 여러분이 그 두 소수를 다시 찾아내는데는 아주 긴 시간, 어쩌면 여러분의 인생보다도 긴 시간이 걸릴 수도 있다고 생각하고 그렇게 믿고있습니다 두 번째는 RSA가 필요로 하는 큰 소수들은 쉽게 만들 수 있어야 한다는 것입니다 즉 매우 빠르게 큰 소수를 만들 수 있어야 한다는 것이죠 그럼 처음으로 언급한 문제 즉 소인수분해는 어렵다는 것으로 돌아가보죠 소인수분해나 소수 스스로의 어떠한 점이 이러한 문제들을 어렵게 만드는 걸까요? 그것을 알아내기 위해 핵심 문제부터 시작해보죠 X가 주어졌을 때, 소수일까요 합성수일까요? 어떤 방식으로 소수임을 확인할 수 있을까요? 우리는 마침내 이러한 문제들을 풀기위한 방법을 만들어 냈습니다 그러면서 우리는 이 문제가 매우 복잡하고 많은 양의 계산이 있음을 알았습니다 즉 이 문제를 즉석에서 푸는 방법은 없다는 것입니다 입력값이 커질수록 답을 찾기 위한 알고리즘과 연관된 시간이나 단계도 증가하였습니다 이제 소수 정리를 사용해서 이러한 찾는 범위를 예상할수 있으므로 찾는 간격이 얼마나 커졌는지 더 잘 이해할 수 있습니다 진짜 문제는 다음과 같은 그래프로 생각할 수도 있습니다 Y축이 알고리즘 내에서 사용하는 각 단계의 수이고 간단하게 시간으로 생각해도 됩니다 X축은 입력된 값의 크기인 그래프라고 말이죠 그리고 이 그래프는 입력값이 커지면 시간도 증가합니다 그 다음 우리에게 닥친 문제는 이 곡선의 모양을 받아들일 수 없었다는 것이었습니다 이 경우에는 N이 20자리 수만 되더라도 최악의 상황에서는 이 문제를 더이상 풀 수 없기 때문이죠 만일 이 알고리즘에 수백 자리를 가진 수를 넣었더라면 제대로 작동하지 않을 것이라는 건 당연했습니다 이 경우에는 아마도 오류가 나겠죠 그래서 지금의 전략으로 큰 수를 입력하면 그 수가 소수인지 알아내는 것은 사실상 불가능합니다 다시 처음에 이야기했던 소인수분해로 돌아가보죠 지금까지 배운 내용들을 토대로 보자면 소수의 판별보다 소인수분해가 더 어려울 것입니다 즉 어떤 수가 소수인지를 알아내는 것보다 어떤 수를 소인수분해하는 것이 더 많은 단계를 가지고 있기 때문입니다 기억하고 있듯이 소인수분해에서는 입력된 수의 N의 모든 소인수를 찾아야 하지만 소수 판별을 위해서는 단지 하나의 약수만 찾으면 되기 때문이죠 이러한 사실들을 깨달은 몇몇 사람들은 실제로 이런 소인수분해 알고리즘을 가지고 첫 약수를 찾을때까지 반복하는 것으로 간단하게 소수판별 알고리즘으로 바꾸었습니다 그러므로 소수 판별법은 단지 소인수분해 알고리즘 안에 있는 하위루틴의 일종이라는 것이죠 그래서 이 그래프로 돌아서 보자면 소인수분해 알고리즘의 그래프는 아마도 이렇게 되겠죠 입력된 수가 커지더라도 소인수분해 알고리즘의 그래프는 소수 판별 알고리즘의 그래프의 위에 있을 겁니다 그러면 어떤 상황에서도 우리에게는 항상 컴퓨터 상의 한계 즉 우리에게 주어진 시점의 컴퓨터가 계산 가능한 단계의 수와 우리가 가지고 있는 시간이 정해져있다는 것을 알 수 있습니다 그리고 이것은 이 그래프의 가로선이나 역치값이라고 생각할 수 있습니다 이 선 위에 있는 어떠한 수도 문제를 풀 수는 없습니다 이 강의에서 우리는 로버에 탑재된 꽤 느린 컴퓨터에 따른 제한때문에 20자리밖에 안되는 수들의 소수 판별조차 할 수 없었습니다 그러나 우리가 1년동안 작동하도록 할 수있는 1000대의 컴퓨터를 가지고있다 해도 그것은 단지 가로선을 위로 올려서 또 다른 역치값을 만들 뿐입니다 그리고 이 방식은 보다 큰 수의 테스트를 가능하게 하지만 여러분이 볼 수 있듯이 또 다시 더 이상 문제를 풀 수 없는 어떤 한계를 항상 만나게 됩니다 이러한 사항들은 수많은 흥미로운 문제들로 이어지게 되는데요 하지만 저는 여기에서 두 개만 밝혀볼 생각입니다 우선 지금까지 이 증가곡선에 대한 명확한 이야기를 한 적이 없었습니다 도움이 될진 모르겠지만 상상을 한번 해봅시다 여러분이 그것을 풀기위해선 무슨 알고리즘이든 시도할 수 있고 어떠한 기계를 사용하여도 상관 없다면 우리는 이 그래프 위에 비슷한 형태의 증가 곡선을 그릴 수 있습니다 간단히 그 알고리즘의 설명을 보고 말이죠 만일 여러분이 이것을 할 수 있다면 어떠한 문제를 푸는 것이 얼마나 어려운지를 말해주는 어떤 분류의 성장의 형태를 알 수 있게 될 것입니다 이런 방식으로 우리는 실행시키기도 전에 알고리즘을 이해할 수도 있으며 이는 매우 중요한 사실입니다 만일 제가 여러분의 알고리즘이 적혀있는 종이를 전달받아 그것을 보면서 다음과 같이 이야기할 수 있다는 것이죠 이 크기의 입력값이라면 이 알고리즘으로는 풀 수가 없습니다 그리고 이는 시간복잡도에 대한 이야기로 이어집니다 시간복잡도는 여러분이 나중에 필요로 할 아주 중요한 개념입니다 만일 여러분이 다항 시간 혹은 지수 시간 안에 이 알고리즘이 실행된다는 말을 들어 보았다면 이런것들이 시간복잡도를 이야기할때 사용하는 용어들입니다 많은 분들이 궁금해 할겁니다 실제로 이러한 임의의 소수를 어떻게 만들어낼까요? RSA에 대한 두 번째 포인트이기도 하죠 좋아요 빠르게 알아봅시다 큰 임의의 수백 자리의 소수들을 만들기 위해서 우리는 다음과 같은 단계의 명령들을 따라가야 합니다 임의의 숫자를 만들고 그것이 소수인지를 판별합니다 만일 그것이 소수라면 우리는 할 것을 다 했습니다 만일 그것이 소수가 아니라면 소수를 만날때까지 이를 반복합니다 이러한 3단계 순서 중에서 특히 그것이 소수임을 판단하는 두번째 단계가 제일 중요합니다 만일 이 단계가 작동하지 않는다면, 전체가 작동하지 않을 것입니다 그러면 오늘날 이것은 어떻게 작동할까요? 우리의 문제에 대한 정의는 미묘한 변화를 근거로 합니다 그리고 임의성의 사용은 더욱 중요해졌습니다 그리고 이는 랜덤 알고리즘들에 대한 다른 강의를 듣고 싶게 할 것입니다 그리고 마지막으로 만일 여러분이 진행하면서 풀기 어려운 문제들이 있다면 아래에 그것을 올려주세요 같이 강의 계획을 짜보도록 할게요 예를 들어 우리가 이미 알고있는 Trial Division 방식의 소수 판별법의 속도를 빠르게하기 위해서는 아직 우리가 알아보지 않은 좀 더 깊은 수학적인 부분을 찾아볼 수 있겠죠 그리고 여러분이 생각하는 또 다른 것이 있나요? 아래에서 그 내용을 공유해 보세요