preLoad Image preLoad Image
검색 바로가기
주메뉴 바로가기
주요 기사 바로가기
다른 기사, 광고영역 바로가기
중앙일보 사이트맵 바로가기
닫기
닫기

실용성 없던 소수 연구, 암호학 만나 ‘몸값’ 크게 올라

[수학이 뭐길래] 소인수분해
2001년 영화로 만들어진 론 하워드 감독, 러셀 크로 주연의 ‘뷰티풀 마인드’ 포스터.

2001년 영화로 만들어진 론 하워드 감독, 러셀 크로 주연의 ‘뷰티풀 마인드’ 포스터.

약수나 배수, 공약수나 공배수 같은 단어는 학창 시절 수학을 공부한 이들에게는 그리 낯설지 않을 것이다. 이 내용은 초등학교 5학년 때 처음 등장하는데, 이후 중학교 1학년에 이르면 소수와 소인수분해로 좀 더 확장된다. 소인수분해는 여러 약수 중 소수로 수를 나누는 과정이고, 소수는 배수가 아닌 수이며, 공약수는 공통으로 나누어지는 소수다. 이때 수의 크기가 작으면 소수로 나누어 소인수분해하는 것이 그리 어렵지 않다.

고대 수학자 에라토스테네스의 체
소수 구하는 가장 오래된 방법
수 커질수록 소수 밀도 점점 줄어

유클리드, 소수 개수 무한함 증명
전체 소수들에 적용되는 규칙 없어

수퍼컴 써도 소인수분해 까다로워
최근 발견된 50번째 메르센 소수
1초에 숫자 5개씩 써도 54일 걸려

 
문제는 수가 커질 때다. 수가 커지면 수퍼컴퓨터를 이용해도 소인수분해가 쉽지 않기 때문이다. 그런데도 수학자들은 오랫동안 소수에 대해 연구하고 그러한 소수로 소인수분해하는 문제에 대해 고민해 왔다. 이런 연구는 왜 하는 걸까? 이 문제를 이해하기 위해서는 먼저 소수에 관해 살펴볼 필요가 있다.
 
2, 3, 5, 7의 배수 걸러내 소수 구해
수학자 존 내시의 삶을 담은 『뷰티풀 마인드』. 존 내시가 리만 가설을 풀다 조현병에 걸렸다는 사실이 밝혀지면서 20세기 후반 40여 년 간 수학자들이 이 연구를 멀리한 것으로 알려져 있다.

수학자 존 내시의 삶을 담은 『뷰티풀 마인드』. 존 내시가 리만 가설을 풀다 조현병에 걸렸다는 사실이 밝혀지면서 20세기 후반 40여 년 간 수학자들이 이 연구를 멀리한 것으로 알려져 있다.

모든 수는 두 수의 곱으로 나타낼 수 있다. 그런데 이 중에는 1과 자기 자신의 곱으로만 표현되는 수들이 있다. 가령 6은 1×6과 2×3으로 나타낼 수 있지만, 7은 1×7의 곱으로만 나타낼 수 있다. 이때 6 같은 수가 합성수이고, 7 같은 수가 소수다. 단 1은 1×1로 나타낼 수 있지만, 소수라고 부르지 않는다. 이것은 고대부터 무언가를 세는 단위인 ‘하나’를 수에서 제외했던 전통에 기인한다(이와는 달리 기하학의 길이나 넓이 등은 셀 수 없는 양을 측정하는 데 사용됐다). 다양한 소수의 특징을 연구하기 위해서도 1을 소수에서 제외하는 것이 수월하다. 따라서 소수는 1을 제외하고, 약수가 1과 자기 자신뿐인 자연수로 정의된다.
 
소인수분해는 자연수를 바로 이러한 소수들로 분해하는 작업이다. 가령, 18이라는 자연수가 있을 때, 18은 2와 3이라는 소수를 이용해 2×3×3으로 소인수분해된다. 우리가 비교적 작은 수의 소인수분해를 쉽게 하는 것은 우리도 모르게 작은 소수에 익숙해 있기 때문이다. 사실 교과서에 나오는 대부분의 자연수는 2, 3, 5, 7, 11, 13, 17, 19 같은 소수들로 소인수분해된다.
 
그런데 앞에서도 이야기했지만, 수가 아주 많이 커지면 소인수분해가 어려워진다. 우리가 주로 사용하는 10 이하나 100 이하의 소수들로는 나누어떨어지지 않기 때문이다. 가령 62,473,207과 같은 여덟 자릿수를 생각해 보자. 이 수는 오로지 두 소수 7901과 7907로 소인수분해된다. 소인수분해를 하려면 주어진 수를 작은 소수부터 시작해서 계속해서 소수로 나누어 보아야 하는데, 이 경우엔 소수가 무엇인지를 파악하기조차 쉽지 않다.
 
그럼 소수는 어떻게 구할 수 있을까? 가장 오래된 방법의 하나는 고대 그리스의 수학자인 에라토스테네스의 체를 이용하는 방식이다. 가령 1부터 100까지의 자연수 중에서 소수를 찾는다고 하자. 이 경우 다음과 같은 방식으로 수를 나열한 뒤 2를 제외한 2의 배수부터 시작해, 3을 제외한 3의 배수, 5를 제외한 5의 배수, 그리고 7을 제외한 7의 배수를 순서대로 체로 거르면 아래와 같이 최종적으로 네모 칸 안의 소수만 남는다.
 
이러한 방식을 활용하면 100을 넘는 수의 표에서도 소수들을 구할 수 있는데, 현재는 천만 이상의 수의 체까지 확장되어 있다.
 
그렇다면 소수의 개수는 주어진 구간마다 일정하게 발견될까? 가령 1부터 100 사이의 소수를 생각해 보자. 이 사이에는 총 스물다섯 개의 소수가 존재한다. 이중 1부터 10 사이의 소수가 네 개인 데 비해 91부터 100 사이에는 단 하나의 소수만 존재한다.
 
그러면 수가 커질수록 다른 수와의 곱으로 표현될 가능성도 커지니 소수가 줄어드는 걸까? 역사적으로 오일러, 르장드르, 가우스 그리고 리만 등을 포함한 많은 수학자가 소수가 어떻게 분포되어 있는지를 밝히기 위해 노력해 왔다. 그 결과 수가 커질수록 소수의 밀도가 점점 줄어든다는 내용의 소수 정리가 발전되기도 했다. 이와 함께 리만 가설과 같이 소수 정리를 증명하려는 다양한 시도들 역시 이어졌다.
 
그렇다면 소수는 도대체 몇 개나 될까? 바로 이 문제에 대해 유클리드 역시 관심을 기울였다. 유클리드는 『기하학 원론』 9권에서 소수의 개수가 무한함을 증명했다. 가령 소수의 개수를 n개라고 가정하고 순서대로 나열한 뒤 그 모든 소수를 곱해서 생기는 공배수 하나를 생각해 보자. 그 공배수에 1을 더하면 앞의 어떤 소수로도 나누어지지 않는다. 새로운 소수가 생기는 것이다. 마찬가지 방식으로 새로 얻은 소수까지 포함해 곱한 뒤 새로운 공배수를 구하고 다시 1을 더하는 과정을 거듭하면 계속해서 새로운 소수가 만들어진다. 결국 소수의 개수를 한정해도 계속해서 새로운 소수가 생길 수 있으므로 소수는 무한하다는 결론에 도달한다.
 
지적호기심이 부른 소수의 신비 찾기
소수를 구하기 위한 에라토스테네스의 체.

소수를 구하기 위한 에라토스테네스의 체.

그러면 이 많은 소수에는 어떤 규칙이 존재할까? 결론부터 말하자면, 전체 소수들에 적용되는 규칙은 존재하지 않는다. 그러나 그런데도 수학자들은 여기에서 포기하지 않았다. 그들은 계속해서 일부 소수라도 나타낼 수 있는 규칙을 찾고자 끊임없이 노력했다. 서유럽에서 소수를 포함한 전문적인 정수론 연구를 부활시켰던 페르마는 1640년에 오늘날 ‘페르마 수’라고 불리는 소수의 규칙을 발표했다.
 
22n+1의 형태의 수가 소수라는 것인데, n이 0부터 4까지의 수인 경우에는 소수가 됨이 확인됐다. 그러나 1732년 오일러는 n=5일 경우에는 225+1=4294967297=641×6700417이 되어 소수가 되지 않음을 보였다.  
 
한편 메르센은 2n-1의 형태와 소수 사이의 관계에 대해 고민했다. 1644년 메르센은 n이 2, 3, 4, 7, 13, 19, 31, 67, 127, 257일 경우에만  2n-1의 형태의 수가 소수가 된다고 결론지었다. 메르센의 결론에는 오류가 있었지만, 결국 일부 큰 소수들에 대해서는  2n-1의 형태의 수가 소수가 됨이 밝혀졌다. 이후 메르센 소수라고 불리게 된 소수였다.
 
독일 수학자 골드바흐는 오일러에게 보낸 편지에서 2보다 큰 모든 짝수는 두 개의 소수의 합으로 표현될 수 있고, 5보다 큰 모든 홀수는 세 소수의 합으로 표현될 수 있을 거라고 제안했다. 골드바흐의 추측이라고 불리는 이 가설은 매우 큰 수에 대해서는 맞는 것으로 확인됐다. 그러나 모든 수에 대해서는 아직 증명되지 않은 상태다. 이외에도 소수에 대해서는 그동안 많은 추측과 정리들이 나왔다. 일부는 증명되었으나 아직 많은 것들이 증명되지 않은 상태다. 
 
뜻하지 않은 곳서 큰 성과 내는 게 수학
2017년 12월 26일 조나단 패이스에 의해 발견된 가장 큰 소수의 일부.

2017년 12월 26일 조나단 패이스에 의해 발견된 가장 큰 소수의 일부.

그렇다면 이제까지 밝혀진 소수 중 가장 큰 소수는 무엇일까? 1876년 프랑스의 수학자 에두아르 뤼카는  2127-1이 소수임을 증명했는데, 이는 1951년 컴퓨터를 사용해 79자리 소수를 발견하기 이전까지 가장 큰 소수였다. 이후 컴퓨터 성능이 발전하면서 소수 계산은 비약적으로 빨라지기 시작했고, 그와 함께 소수의 크기 역시 증가됐다. 1996년에는 ‘인터넷 메르센 소수 탐색(the Great Internet Mersenne Prime Search)’ 프로젝트가 발족됐다. 이와 함께 21,398,269-1이라는 35번째 메르센 소수가 발견됐다. 이후 프로젝트가 네트워크로 연결되어 공조 작업이 가능해지면서 거의 해마다 더 큰 소수가 발견되고 있다. 최근에 발견된 가장 큰 소수는 미국의 전기공학자 조나단 패이스가 발견한 50번째 메르센 소수 277,232,917269-1이다. 1초에 숫자 5개씩 54일 동안 써야 모두 적을 수 있을 만큼 큰 수다.
 
그렇다면 이런 일을 왜 하는 걸까? 오랫동안 수학자들을 매료시켰던 가장 큰 이유는 아마도 지적 호기심 때문이었을 것이다. 그러나 20세기 후반 암호학이 발전하면서 소수에 대한 관심은 새로운 전환을 맞고 있다. 암호는 역사적으로 오래됐지만, 컴퓨터 통신 기술의 발전을 통해 기밀 정보를 네트워크를 통해 송수신하는 일이 증가하면서 해킹의 위협과 함께 더욱 중요해졌다. 이와 함께 다양한 암호 체계 역시 개발됐는데, 그중에서도 1977년 매사추세츠공대(MIT)의 세 수학자에 의해 고안된 RSA 암호 방식은 널리 활용되며 주목받고 있다.
 
이 방식은 정보를 보내는 사람이 큰 자연수를 이용해 해당 정보를 암호화하는 방식인데, 이 자연수의 두 소인수를 구해야만 암호를 풀고 정보를 읽을 수 있다. 그런데 이게 몹시 까다롭다. 가령 100자리의 자연수를 소인수분해 하려면 1초에 1000조(1015)개의 셈을 하는 수퍼컴퓨터를 사용해도 1035초, 대략 3×1027년이 걸린다. 미리 소인수분해하는 방법을 알고 있다면 암호를 풀 수 있겠지만, 그렇지 않다면 이 암호는 풀 수 없다.
 
소수 등을 다루는 정수론 분야는 오랫동안 실용성과는 무관한 순수수학의 한 분야였다. 그러나 최근 암호학 연구에 응용되면서 크게 주목받고 있다. 역사적으로 수학은 뜻하지 않은 곳에서 큰 성과를 보여 왔다. 수학을 강조하는 이유가 여기에 있다.
 
 
조수남 수학사학자 sunamcho@gmail.com
서울대 과학사 및 과학철학 협동과정 박사. 현 서울대 강사이다. 과학사와 수학사를 연구하고 있다. 고등과학원 초학제연구단에서 연구했으며, 『욕망과 상상의 과학사』 등을 썼다.

포함의 아픔을 아직도 그대로...

AD
온라인 구독신청 지면 구독신청

PHOTO & VIDEO

shpping&life

많이 본 기사

댓글 많은 기사