‘소수’ 수학과 컴퓨터 과학의 접점

모두가 알고 있듯이 소수는 다른 정수를 곱해서 만들 수 없는 수를 의미한다. 얼핏 단순해 보이는 특성이지만, 여기에는 고대와 현대의 여러 수학자를 매료시킨 복잡한 세계가 숨어 있다. 소수의 특성은 컴퓨터 과학과 암호화 영역에서도 필수적으로 응용된다. 

산술의 기본 정리 

용어에서 알 수 있듯이 산술의 기본 정리는 숫자의 동작 방식을 심오하게 다룬다. 이 정리에 따르면, 모든 숫자는 특정 소수의 곱으로 설명할 수 있다. 이는 소수의 기본 정의에 따른 흥미로운 결과다. “흥미로운” 이유는 소수의 정의에서 잘 보이지 않으면서도 그 정의에 따른 거의 직접적인 결과이기도 하기 때문이다. 

수학적 대상의 속성을 취해 거기서 파생되는 결과를 계속 추론해 나가면 최종적으로 디피-헬만(Diffie-Hellman), RSA, 타원곡선(Elliptic curve)과 같은 필수적임 암호화 알고리즘으로 이어지게 된다. 

산술의 기본정리에 따르면 1을 제외한 모든 수는 그 자체가 소수이거나 소수의 고유한 곱이다. 간단한 예로 숫자 25를 보자. 

25=5×5 

다르게 말하면 25의 “소수 서명(prime signature)”은 5×5다. 이 서명을 갖는 수는 25가 유일하며, 5×5의 유일한 결과는 25다. 정수의 전체 범위, 즉 정수의 무한대에 대해 생각해 보면 이 정리가 고유하게 식별할 수 있는 방대한 경우의 공간을 보장한다는 것을 알 수 있다. 

아무 숫자나 집어 들고 ‘이 숫자의 소인수분해는 무엇인가?’라는 질문을 해보자. 이 말은 ‘이 숫자의 소수 서명은 무엇인가?’와 같다. 이 질문의 답을 구하는 것은 매우 어렵다. 알려진 두 소수의 곱인 숫자를 만드는 역연산과 비교할 때 특히 어렵다. 

어려움의 바탕은 기본 정리에 있다. 기본 정리는 전체 공간에서 각 숫자에는 하나의 소인수 집합만 있음을 의미하기 때문이다. 또한 이런 문제를 무차별 대입으로 공격하는 것은 현실성이 없다는 의미이기도 하다. 물론 25의 경우 5×5를 바로 떠올릴 수 있지만 1,000 자릿수의 숫자라면 어떨까? 계산적으로 인수를 추정하기가 거의 불가능하다. 

해시 함수에서의 소수 

코딩에서 소수가 등장하는 또 다른 흥미로운 영역은 해시 함수를 만드는 경우다. 해시 함수의 주 역할은 입력을 받아서 그 입력에 해당하는 숫자로 변환하는 것이다. 이 숫자는 전체 입력의 축소판이며, 그 사실 덕분에 체크섬과 해시테이블 같은 구조 등 많은 부분에서 유용하다. 

해시테이블을 위한 해싱은(자바의 hashCode와 같이 컬렉션에 배치되는 객체에 대한 해시 함수) 상수의 모듈로(modulo)를 사용하며 이 상수는 소수가 되는 것이 좋다. 이런 경우 상수에 소수를 사용하면 충돌 가능성을 낮추는 데 도움이 된다. 숫자의 소수성에 따라 해시테이블 함수와의 공통 분모가 더 적고, 따라서 모듈로 분포가 더 균등해지기 때문이다. 

같은 이유로, 해시테이블 “버킷 카운트(bucket count)”의 소수는 비대칭 충돌을 방지하는 데 도움이 된다. 본질적으로 해싱 상수와 버킷 카운트에 소수를 사용하면 둘 사이의 유의미한 관계 가능성을 줄여 버킷 항목의 적절한 무작위 분포를 보장하는 데 도움이 된다. 

이 관계에 대한 스택 오버플로우의 토론에서 소수와 해시에 대해 더 알아볼 수 있다. 

소수와 해싱이 어울리는 또 다른 영역은 비밀번호 해싱과 암호화폐의 요소로 광범위하게 사용되는 SHA-256, MD5와 같은 함수다. ‘연필과 종이를 사용한 SHA 256 기초’를 보면 비트코인 키를 처음부터 만드는 과정을 통해 수동으로 SHA-256을 재미있게 접할 수 있다. 소수의 역할을 잘 보여주는 글이다. 

소수와 모듈러 수학 

프로그래밍에 많은 영향을 미치는 또 다른 흥미로운 수학 영역은 모듈러 수학이다. 유한한 범위의 숫자를 가져오고 남은 것만 세기 때문에 “시계 수학(clock math)”이라고도 한다. 예를 들어 시계에서 1부터 12까지의 숫자를 사용하고 초과분만 사용해서 13시가 1시가 되는 것이 여기에 해당한다(12에서 시작한다고 가정할 경우). 

모듈러 수학은 특히 암호학을 비롯한 많은 분야에 사용된다. 역수와 같은 원하는 속성을 얻기 위해 모듈러 수학과 소수를 함께 사용해야 하는 경우가 많다. 케임브리지 대학교 출반부가 모듈러로서의 소수에 대해 잘 분석해 놓은 글을 참고하면 좋다. 

에라토스테네스의 체 

이제 반대로 뒤집에서, 수학의 고전적인 문제 중 하나인 소수 발견에 코딩이 어떻게 도움이 되는지 살펴보자. 에라토스테네스는 기원전 3세기에 고대의 알고리즘을 정리했다. ‘에라토스테네스의 체(Sieve of Eratosthenes)’라고 불리는 이 알고리즘은 주어진 숫자에 대한 모든 소수를 찾는 일련의 단계를 제시한다. 

알고리즘의 기본 개념은 숫자 n을 취한 다음 일련의 패스를 통해 소수가 아닌 숫자를 제거해 나가는 것이다. 이 과정을 마치고 남은 숫자가 바로 소수 집합이다. 이 과정은 다양한 방법으로 다듬을 수 있지만 현대판의 기본 체에서는 먼저 2를 취해 이를 소수로 표시한 다음 n에 이르기까지 모든 짝수를 찾아 소수가 아닌 것으로 표시한다. 그런 다음 3으로 가서 3의 배수에 대해 똑 같은 작업을 수행한다. n에 이르기까지 모든 수에 대해 이 작업을 하되, 이미 소수가 아닌 숫자로 표시한 수만 건너뛴다. 

이는 알고리즘의 아주 오래된 예시다. 물론 이제 프로그래머는 이를 실행 가능한 형식으로 바꿀 수 있다. 다음은 자바스크립트 버전이다(출처 : 위키피디아). 

function getPrimeNumbers(max) {
    // A list of booleans where index 2 being true corresponds to 2 being prime
    var isPrime = [];

    // Initial population of isPrime
    for (var i = 0; i < max; i += 1) {
        if (i != 0 && i != 1) {
            isPrime.push(true);
        }
        else {
            isPrime.push(false);
        }
    }

    // Iterate over entire list
    // Element => true if index is prime else false
    for (var i = 0; i < max; i += 1) {
        if (isPrime[i]) {
            for (var j = i + i; j < max; j += i) {
                isPrime[j] = false;
            }
        }
    }

    var primes = [];

    // Assemble list of primes
    for (var i = 0; i < max; i += 1) {
        if (isPrime[i]) {
            primes.push(i);
        }
    }

    return primes;
}
 
이 외에도 앳킨의 체(Sieve of Atkin), 그리고 밀러-라빈 소수성 테스트(C++로 보기)와 같은 확률적 소수성 테스트에 대한 매력적인 접근 방식 등 주어진 영역에서 소수를 발견하기 위한 다른 많은 접근 방법이 개발됐다. 밀러-라빈은 속도는 빠르지만(O(k log3 n)) 확률적인 속성으로 인해 가끔 거짓 양성이 발생할 수 있다. 

소수를 찾기 위한 알고리즘은 잘 알려졌고, 코딩으로 작성하기도 간단하다. 처음의 단순함과 수학 천재들의 1,000년에 걸친 관심에도 불구하고 소수의 특징과 본질은 여전히 신비로운 영역으로 남아 활발한 연구가 이뤄지고 있다는 점은 생각해보면 놀라운 일이다. 

리만 가설 

수학에서 가장 흥미로운 미해결 문제 중 하나는 리만 가설(Riemann Hypothesis)이다. 이를 계산하기 위한 코드베이스를 깃허브에서 다운로드할 수 있다. 

리만은 가우스의 학생이었다. 가우스라는 이름은 어도비 포토샵과 같은 소프트웨어에 있는 “가우시안 블러(Gaussian blur)”를 통해서도 아마 들어봤을 것이다. 가우스는 소수의 발견을 추정하는 함수를 고안했는데, 지금은 이 함수를 소수 정리(Prime Number Theorem)라고 한다. 리만의 함수는 제타 함수로, 복소수를 무한 급수에 통합해 가우스 정리의 정확도를 높인다. 리만 가설은 숫자의 근본적인 동작을 들여다보는 가설이다. 이것이 컴퓨터 과학에 미치는 영향은 아직 다 밝혀지지 않았다. 이 가설의 증명은 이론 수학에서 가장 많은 노력이 이뤄지고 있는 부분이다. 

수학과 컴퓨팅의 접점에서 가장 잘 알려진 인물로는 앨런 튜링이 꼽힌다. 숫자의 계산 가능성에 대한 튜링의 논문은 현대 컴퓨터를 위한 개념적 기반을 제공했다. 튜링은 소수, 특히 리만 가설을 깊이, 그리고 오랫동안 연구했다. 튜링은 리만 가설 머신을 만들고자 했지만 2차 세계대전이 발발하면서 작업이 중단됐고, 개발 과정에서 얻은 지식을 응용해서 나치 암호를 해독하는 분석 머신을 만들었다. 

튜링의 마지막 논문은 리만 제타 함수를 다룬다. 

양자 컴퓨팅에서의 소수 

양자 컴퓨팅은 언젠가는 체계적인 방식으로 지금의 암호화 방식을 위협하게 될 수 있다. 하드웨어만 받쳐준다면, 큐비트가 결국 소수를 줄줄이 찾아내면서 디피-헬만과 같은 함수를 역방향으로 수행하기 위해 필요한 계산 시간을 줄여줄 것이기 때문이다. 

결론 

이 기사에서는 소수 수학과 컴퓨터 과학이 만나는 다양한 영역을 살펴봤다. 극히 단순하게 시작하지만 연구의 최전선에 있는 정수론의 매우 정교한 영역과 직접 연결된다는 면에서 매우 흥미로운 분야다. 프로그래밍과 소수는 우리가 컴퓨터를 사용하는 한 계속해서 서로 영향을 미치고 정보를 주고받을 것이다. 이는 특히 소수의 속성 및 동작을 핵심으로 하는 암호화 분야에서 잘 볼 수 있다.
[email protected]