[김대수의 수학 어드벤처] 소수 첫 기록 파피루스에 등장 … 컴퓨터 보안에 필수

고도의 정보화 사회를 맞이하여 컴퓨터, 휴대전화, 금융거래 등의 정보 보안에 대한 염려가 현실화되고 있는 가운데 암호를 푸는 해킹을 통해 중요한 정보에 불법적으로 접근하는 사례가 빈번히 일어나고 있다. 이러한 때에 정보 보안에 있어서 소수에 관한 이론이 매우 소중하게 활용되고 있다.

소수(素數, prime number)는 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 자연수를 말한다. 예를 들면 2, 3, 5, 7, 11, 13… 등은 모두 소수다. 4, 6, 9와 같이 소수가 아닌 자연수는 합성수라고 한다.

소수는 수학에서 주요 분야 중의 하나인 정수론에서 매우 중요한 역할을 담당한다. 또한 최근에는 암호 분야에서 활발하게 사용되면서 그 중요성이 더욱 부각되고 있다.

우리는 중학교 시절 2, 3, 4, 5…로부터 소수를 찾아내는 방법으로 비교적 간단한 방법의 ‘에라토스테네스의 체’를 사용한 적이 있는데, 그 방법은 다음과 같다.

(1)찾고자 하는 범위의 자연수를 나열한다. (2)2부터 시작해 2의 배수를 지워나간다. (3)다음 수의 배수를 모두 지운다. 이를 반복하여 마지막까지 지우면 남는 수들이 소수가 된다.

소수에 대한 최초의 기록은 고대 이집트의 종이인 파피루스에서 찾을 수 있는데, 그 속에는 소수와 합성수가 구분돼 적혀 있다. 그 후 그리스 시대인 기원전 300년 전에 출간된 유클리드 원론에는 무한히 많은 소수가 존재한다는 것이 증명됐다. 그 이후부터 가장 큰 소수를 찾고자 하는 노력은 끊임없이 지속되어 왔다. 1876년에는 39자리의 소수가 발견되었으며, 1952년에는 2281자리, 2001년에는 400만 자리를 거쳐 현재까지 발견된 가장 큰 소수는 2014년 1월을 기준으로 25788만5161 -1 로서 무려 1742만5170자리의 어마어마한 숫자다. 이처럼 큰 소수의 발견은 수퍼컴퓨터의 개발로 가능하게 되었다.

보다 큰 소수를 발견하는 사람에 대한 상금이 NF재단에 의해 시상된 바 있으며, 지금도 여러 기관에서 큰 상금을 걸어놓고 있다.

소수는 컴퓨터 시스템의 보안에 많이 활용되는 수학 이론 중 하나다. 미국 국방부의 요청으로 1973년 IBM에서 개발한 DES 알고리즘은 64비트의 조합으로 만들기 때문에 해독이 사실상 매우 어렵다. 더군다나 이 시스템의 단점을 보완해 1977년에 개발된 RSA 알고리즘은 상당히 큰 소수의 소인수 분해가 힘들다는 점을 이용해서 만든 놀라운 암호화 시스템이다.

이들은 모두 큰 규모의 소수를 활용하므로 암호에 대한 연구는 소수에 대한 이해로부터 시작한다고 해도 과언이 아니다. 이런 점에서 볼 때 첨단 컴퓨터 이론에도 역시 수학적 이론이 필수적인 바탕이 되고 있다는 것을 알 수 있다.

[문제 1]에서는 안과 밖의 도형이 바뀐 변화와 색칠한 것을 면밀히 관찰해 그 변화를 똑같이 적용하면 된다.

[문제 2]에서는 나눗셈을 포함하며, 그 결과가 정수여야 하므로 적절한 위치에다 괄호를 넣어 3으로 나누어 떨어지게 하는 데 착안한다. 다양한 결합을 머릿속에 시도해 본다.

[문제 3]에서는 총 면적을 고려해 짐작해 보는데 다양한 방법으로 생각하면 풀릴 것이다.