소수(prime number)는 숫자를 압축하여 나타내는 노력의 최전선이다

 왜 수학에서는 소수(prime number)가 중요할까? 흔히들 소수는 숫자의 원자라고 한다. 1과 자기 자신 외에는 나누어 떨어지지 않으면서, 모든 수는 소수들을 몇번씩 곱하면 만들어지기 때문이다. 학생시절 배운 소수를 상기해보자.

[소수를 구하는 에라토스테네스의 체, 각 숫자의 배수는 모두 지우고 남은 수들이다. 구글검색]

 수학을 하다보면 최소 공약수나 최소 공배수가 중요한 순간들도 있다. 그리고 매우 큰 수를 다루다보면 수를 분류하고 싶어지는데 이렇게 시도 하다보면 여지없이 만나게 되는게 이 소수이다. 그렇게 수학자들도 더 쉽고 단순화하다보면 소수를 만나게 된다. 그러면 소프트웨어 개발 관점에서는 이 소수가 어떤 의미를 지닐까? 물론 소수는 RSA 비대칭 암호화에서 핵심 역할을 수행하고 있지만, 그보다 더 본질적으로는 "최적화의 문제"에 이 소수가 등장할 수 있다.

 

 대표적인 질문은, 수를 어떻게 하면 기계적으로 최적화해서 나타낼까? 이다.

 

아니 수를 어떻게 하면 최적화해서 나타내느냐고? 변수 하나 선언해서 하면 될 것이 아닌가. 라고 물을 수 있겠다. 그러나 부동소수점이나 여러가지 다양한 수를 나타내는 방법을 배웠거나 고민해본 사람은 이 문제가 그렇게 단순하지는 않다는 것을 알것이다.

 

우선, 가장 기본적으로는 컴퓨터는 정수를 2진수의 나열로 나타낸다. 컴퓨터에서 가장 기본이 아닐까 싶다. 모두가 아는대로

 

10(10진수) = 1010(2진수)

 

로 나타낼 수 있다. 순서를 갖는 2bit의 전압이 있고 없는 메모리 공간 4개를 저렇게 약속하면 된다. 그렇다 "약속"하면 된다.

 

( 이 숫자 체계를 이해함에 있어서 사실은 대칭이나 그 본질을 더 깊숙하게 이해하면 좋은데 아래 링크를 추천한다. 이 글이 곱씹을 만하다고 느껴지면 왜 대칭 체계에 소수가 역시 등장할 수 밖에 없는지 이 링크 글을 참조하기를 바란다 - https://infoengineer.tistory.com/31 )

 

 정수와 관련하여 위와 같이 정의하면 간단히 끝날 일이기도 하다. 그런데 앞서 소개했듯이 소수를 이용하면 이 "약속"을 더 최적화할 수 있다. 즉, 수를 각 소수들의 곱으로 나타내는 일이다. 그리고 이것이 숫자의 원자가 필요한 이유이다. 원자는 그것을 분해하여 최적화할 수 있게 해준다.

 

         10(10진수) = (5^1) * (2^1) (5를 한번, 2를 한번 곱하면 된다)

 

 

이를 테면 우리가 소수의 테이블을 prime 배열로 관리한다고 치면(ex> prime = {1,2,3,5,7,11,...}, 참고로 1은 소수에 포함을 안시키는 수학자가 많긴 하다.여기서는 편의상 포함시켰다.) 위 10진수의 10은,

 

prime[0] = 1

prime[1] = 2

prime[2] = 3

prime[3] = 5 ...

 

10(10진수) = prime[3]^1 * prime[1]^1

 

이렇게 나타낼 수 있다. 이렇게 해서 무슨 이득이 있을까? 더 복잡해 보일 수 있겠다. 하지만 가만히 생각해보라. 작은 수에서는 별 이득이 없겠지만 무한의 수를 다루면 장점은 엄청나다. 최소한의 비트만 가지고 매우 큰 수를 나타낼 수 있게 된다. 그리고 제곱하는 수 마저도 이렇게 소수를 이용해서 나타낼 수 있다. 10은

 

 

10(10진수) = prime[3]^prime[0] * prime[1]^prime[0]

 

 

이 된다. 예를 들면 소수로 된 숫자체계를 저렇게 테이블로 정의할 수 있고, 그렇게 되면 매우 큰 수를 최소한의 비트로 표현할 수 있게 된다. 한번 시험해보기 위해, 2^256 (2의 256제곱이다) 을 나타내보자. 이 숫자를 나타내려면 원래 방식대로라면 대략 2비트 256개가 필요하다. 10000....(2진수) 이렇게 나타내야 한다. 그런데 위 소수 진법(?)으로는

 

prime[1]^256 = prime[1]^(prime[1]^8)

                                         = prime[1]^prime[1]^(prime[1]^3)

                                                   = prime[1]^prime[1]^prime[1]^prime[2]

 

 이렇게 나타낼 수 있다. 몇가지 약속만 있으면 우리가 약속한 소수테이블을 4번 정도 참조하는 것만으로 2비트 256개의 표현을 4개의 비트로 절약될 수도 있는 셈이다. (이 숫자를 처리하기 위한 연산량의 많고 적음은 좀 나중에 고민할 수 있다. 우리는 지금 이성의 세계를 탐색하고 있으니 말이다. 그리고 사실은 우리가 컴퓨터를 전부 개조해서 모든 H/W가 매우 큰 수를 다루는 경우 저렇게 소수 단위로 처리하게 했다면 전세계의 컴퓨터 메모리와 디스크를 엄청나게 절약했을 수도 있다.)

 

 앞 글에 소개한대로 대칭에 기반한 숫자체계를 단순하기 위해 고민하다보면, 이렇게 소수의 테이블을 참조하는 구현방식 외에 더 단순하게 나타내는 이론적이 없다는 것을 깨닫게 된다(수학자들이 수천년간 고민한 결과는 그렇다). 만약에 엔지니어가 이를 더 단순화할 수 있는 본질적인 방법을 발명해낸다면, 반대로 수학자에게는 수 체계의 새로운 지평을 열어줄 수도 있겠다.

 

 자 그럼 이제 수학자들의 고민을 살펴보자. 그들은 여러 경로를 통해 이 소수에 관심을 갖게되었고 자연스레, 이 소수의 규칙을 찾고 있다. 가우스의 소수에 대한 다양한 추측이나 리만의 제타 함수들은 결국 이런 과정에서 탄생한 녀석들이다. 아주 쉽게 가우스는 우리가 규칙성이 없어서 테이블화한 저 소수에 대해 이런 규칙을 알고 있다. 대략 소수가 어찌어찌 분포한다는 근사 법칙이다.

( https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_%EC%A0%95%EB%A6%AC )

 

이런 규칙을 가지고 어떻게 써먹는다는 말인가?

 

 바로 위 소수 테이블을 또다시 인코딩하여 더 단순화할 수 있게 된다. 현재로서는 2,3,5,7,11의 패턴은 그저 숫자를 하나하나 붙여서 테이블화 할 수 밖에 없다(테이블 말고는 이 배열을 정의할 방법이 없다). 만약에 저 수가 2,4,6,8,10 형태의 짝수이면 어떻게 되었겠는가? 곧바로 구태여 메모리를 잡아 먹는 저 소수 테이블을 없앨 수 있다는 사실을 알게 된다. 매우 큰 수에서 저 소수 테이블이 엄청나게 커지게 됨은 불을 보듯 뻔한데, 저 테이블을 유한한 숫자만으로 제한 할 수 있다거나, 없앨 수 있다면 굉장한 공헌이 아닐 수 없다. 수학자들에게 따라서 소수의 정확한 규칙(근사 말고)을 발견했다는 것은 소프트웨어 개발자에게 위의 메모리 최적화에 대한 답을 제공해주는 것과 동치의 발견이 된다.

 

 조금 다르게 표현하면, 소수의 규칙을 발견했다는 것은, 위 소수 테이블을 더 단순화하여 숫자를 추가로 압축하여 나타낼 수 있다는 의미가 된다. 메모리와 디스크가 획기적으로 줄어든다! 그런데 결론은 아직은 정확한 규칙이 밝혀지지 않았다.

 

 다만, 위 가우스의 소수 정리 등을 가지고도 좀 근사해서 개발 할 수는 있다. 억지로 소수 테이블을 저 소수 정리에 나오는 로그의 규칙을 따라 정의하면, 예를 들어 n번째 소수를 "log(n)+무언가" 같은 것으로 가정한 후 숫자를 표기하는 것이다. 물론 값은 실제 값이 아니라 들쑥날쑥 조금씩 다르겠다. 대신에 큰 수를 다룰 때 필요한 엄청 큰 크기의 소수 테이블은 없앨 수도 있다. 하지만 소수의 법칙이 제대로 발견되지 전까지는 소수 정리가 보여주는 불규칙성을 그대로 내재하게 된다. 사실 지금까지 발견된 근사한 소수의 법칙으로는 제대로 쓸 수 있는 소프트웨어를 만들 수 없는 것이 현실이다. 그저 단순히 값이 많이 틀려도 되는 단순 예측, 추세 확인 정도나 할 수 있겠다.

 

 오늘 시작한 주제는 여기 까지이다. 이렇게 수학의 몇몇 주제를 소프트웨어 개발 관점에 바라보면 수학자들이 논의하는 의미를 알아차리기 힘들거나 어려워 보이는 일들이, 실제 어떤 의미를 지니는 지 더 확실하게 알 수 있다. 필자가 발견한 것은 소프트웨어 개발이라는 것은 자연과학의 기계적 관점을 체화하여 경험하는 일이기 때문에, 사실은 수학자와 같은 논리적인 생각을 할 수 있고 그 주제를 더 잘 이해할 수 있는 수학 친화적인 직업이라는 점이다. 그래서 최적화를 고민하게 되면 늘 수학자들이 고민하는 최전선을 경험하는 일로 이어진다.

 

 오늘은 몇가지 주제 중에서 소수가 어떤 의미를 지니는지, 소수가 무엇을 할 수 있는지, 소수의 규칙을 발견하는 일이 어떤 것인지 간단히 다루어 보았다. 모든 것이 가만히 보면 이렇게 최적화와 연관이 된다. 그리고 이 다음시간에는 섀넌의 정보이론에 나오는 압축에 대한 내용을 살펴보자. 압축으로 이해하면 이 무슨 이야기인지 모를 내용이 너무 당연한 것으로 다가오게 된다.