왜 수학에서는 소수(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)+무언가" 같은 것으로 가정한 후 숫자를 표기하는 것이다. 물론 값은 실제 값이 아니라 들쑥날쑥 조금씩 다르겠다. 대신에 큰 수를 다룰 때 필요한 엄청 큰 크기의 소수 테이블은 없앨 수도 있다. 하지만 소수의 법칙이 제대로 발견되지 전까지는 소수 정리가 보여주는 불규칙성을 그대로 내재하게 된다. 사실 지금까지 발견된 근사한 소수의 법칙으로는 제대로 쓸 수 있는 소프트웨어를 만들 수 없는 것이 현실이다. 그저 단순히 값이 많이 틀려도 되는 단순 예측, 추세 확인 정도나 할 수 있겠다.
오늘 시작한 주제는 여기 까지이다. 이렇게 수학의 몇몇 주제를 소프트웨어 개발 관점에 바라보면 수학자들이 논의하는 의미를 알아차리기 힘들거나 어려워 보이는 일들이, 실제 어떤 의미를 지니는 지 더 확실하게 알 수 있다. 필자가 발견한 것은 소프트웨어 개발이라는 것은 자연과학의 기계적 관점을 체화하여 경험하는 일이기 때문에, 사실은 수학자와 같은 논리적인 생각을 할 수 있고 그 주제를 더 잘 이해할 수 있는 수학 친화적인 직업이라는 점이다. 그래서 최적화를 고민하게 되면 늘 수학자들이 고민하는 최전선을 경험하는 일로 이어진다.
오늘은 몇가지 주제 중에서 소수가 어떤 의미를 지니는지, 소수가 무엇을 할 수 있는지, 소수의 규칙을 발견하는 일이 어떤 것인지 간단히 다루어 보았다. 모든 것이 가만히 보면 이렇게 최적화와 연관이 된다. 그리고 이 다음시간에는 섀넌의 정보이론에 나오는 압축에 대한 내용을 살펴보자. 압축으로 이해하면 이 무슨 이야기인지 모를 내용이 너무 당연한 것으로 다가오게 된다.
'SW개발의수학적본성' 카테고리의 다른 글
| 코딩, 전산과 순수 수학은 어떻게 관계가 있는가? 어떻게 도울 수 있는가? (0) | 2023.10.14 |
|---|---|
| Computational Mathematics가 가능하다 (0) | 2023.07.08 |
| 소프트웨어 개발과 수학과의 관계 - Intro (0) | 2021.08.14 |
