소수는 자연수 중에서 약수의 개수가 2개인 수를 말하잖아요. 그러면 2, 3, 5, 7, 11,··· 인데 분명히 자연수 중의 일부이니까 자연수보다는 개수가 적지 않나요? 소수의 개수도 무한히 많다고 할 수 있나요?

ⓒ 북멘토 | 저작권자의 허가 없이 사용할 수 없습니다.

자연수 중에서 약수의 개수가 2개인 수를 소수라고 합니다. 달리 말하면 약수가 1과 자기 자신 뿐인 수 중에서 1을 제외한 자연수를 소수라고 합니다. 어떤 물질의 성질을 분석하기 위해 물질을 구성하는 원소들을 살펴보는 것과 같이 어떤 수의 성질을 분석하는 데는 그 수를 구성하는 소수들로 분해해 보는 것이 중요합니다. 소수의 중요한 성질에 대해 알아봅시다.

ⓒ 북멘토 | 저작권자의 허가 없이 사용할 수 없습니다.

소수는 무한히 많다

먼저 소수가 갖는 기본적인 성질부터 알아보아요. 소수가 무한히 많다고 하는데 어떻게 그걸 알 수 있을까요? 자연수가 무한히 많다는 것은 누구나 쉽게 알 수 있습니다. 어떤 자연수n에 1을 더해서n＋1이라는 새로운 자연수를 계속 만들어 낼 수 있으니까요. 짝수나 홀수도 2n, 2n＋1에 계속 2씩 더하면 새로운 짝수나 홀수를 얼마든지 만들 수 있으니 무한히 많은 짝수, 홀수가 있다는 것을 쉽게 알 수 있습니다. 그런데 소수에 대해서도 자연수나 짝수에서와 같은 생각으로 새로운 소수를 만들어 낼 수는 없습니다. 소수에 어떤 소수를 더했을 때 3＋5＝8처럼 반드시 소수가 되는 것은 아니기 때문입니다. 이에 대해 2300여년 전 유클리드라는 수학자가 다음과 같이 답을 했다고 합니다.

소수를 찾는 일반적인 식은 아직 없다

그러나 유클리드 이후 소수가 무한히 많다는 것을 알려졌지만 소수를 만들어 내는 일반적인 식을 찾은 사람은 없습니다. 몇몇 수학자들이 소수를 찾아내는 식을 만들어보았지만 후에 적당한 수를 식에 대입하면 소수가 아닌 수가 발견되곤 하였습니다.

다만 어떤 수가 소수인지 여부를 판단하기 위해서는 몇 가지 방법이 있는데 가장 기본적인 방법으로 에라토스테네스의 체라고 불리는 다음과 같은 방법이 있습니다. 가령 1부터 100까지의 수 중에서 소수를 구한다면 다음과 같이 소수가 아닌 수를 지워나가면 소수를 찾아낼 수 있습니다.

1에서 100까지 숫자를 차례로 적습니다. 그리고 다음과 같이 수를 지워나갑니다.
먼저 1을 지웁니다.
다음 2을 제외한 2의 배수를 모두 지웁니다.
세 번째로 3을 제외한 3의 배수를 모두 지웁니다.
네 번째로 5을 제외한 5의 배수를 모두 지웁니다.
다섯 번째로 7을 제외한 7의 배수를 모두 지웁니다.
⋮

이런 식으로 작은 수부터 소수들의 배수들을 모두 지워 나가면 체에 걸러지듯 남는 수가 소수입니다.

에라토스테네스의 체에 걸러진 1부터 100까지의 자연수

ⓒ 북멘토 | 저작권자의 허가 없이 사용할 수 없습니다.

그런데 한 번 더 생각해 보면 100보다 작은 모든 소수에 대해 위와 같은 작업을 할 필요는 없다는 것을 알 수 있습니다. 즉, 100 이하의 소수를 구하기 위해서는 2, 3, 5, 7의 배수만 지우면 가능합니다. 왜냐하면 100은 10의 제곱수이므로 10보다 작은 소수들만 지우는 작업을 하면 되는 것입니다. 예를 들어 11의 배수를 지운다고 합시다. 11×2, 11×3, 11×4, ···, 11×9 등등을 지우려고 하는데, 사실 2×11, 3×11, ··· 이므로 이미 지워져 있습니다.(2의 배수, 3의 배수 등은 이미 지워져 있습니다.)

만약 200이라면 200의 제곱근이 14.×××××이므로 이보다 작은 소수 2, 3, 5, 7, 11, 13까지 작업을 하면 됩니다. 좀 더 일반적으로 말하자면 어떤 자연수n에 대해서n 이하의 소수를 모두 찾아보려면 이하의 소수들만으로 에라토스테네스의 체를 적용하면 소수를 모두 찾을 수 있습니다. 그러나 이 방법은 적은 수의 소수를 찾을 때 유용한 방법입니다. 앞에서처럼 지워 나가면n이 점점 커짐에 따라 소수를 찾는 작업 시간도 점점 많이 걸리고 충분히 큰 수에 대해서는 별로 실용적이지 못합니다.

에라토스테네스의 체 말고도 ‘윌슨의 정리’나 ‘APR 소수 판정법’ 등 좀 더 어려운 수학적 지식을 필요로 하는 소수 판정법이 있지만 여전히 아주 커다란 수인 경우 소수인지 여부를 판정하는 데는 많은 시간이 걸립니다.

곱셈 계산은 쉬우나 소인수분해는 쉽지 않다

두 개의 소수를 곱하면 당연히 처음에 곱했던 두 개의 소수로 나누어지는 숫자를 얻게 됩니다. 예를 들어 소수인 7과 소수인 5를 곱하면 35를 얻게 되고, 이 35는 7과 5로 나누어집니다. 그런데 이렇게 두개의 소수를 곱하는 것은 아무것도 아니지만 거꾸로 하는 것, 즉 어떤 소수의 곱으로 이뤄진 숫자에서 곱한 소수를 찾는 것은 매우 어렵습니다. 두 소수의 곱은 11927×20903＝249310081로 쉽게 계산할 수 있지만 거꾸로 249310081을 처음의 두 소수로 다시 쪼개는 건 정말 까다롭습니다.

소수는 무한히 많은데, 그들은 소수라는 공통점을 제외하고는 어떤 식으로 표현할 수 있는 일정한 규칙이 없기 때문입니다. 바로 이런 소수의 특성 때문에 현대에 암호 만드는 방식 중 가장 일반적인 방법 중의 하나인 RSA 방식의 암호가 만들어질 수 있었습니다. 큰 숫자를 소수의 곱으로 분리하는 것은 앞에서 본 것과 같이 에라토스테네스 체로 걸러내는 것과 같은 번거로운 작업을 거쳐야 하기 때문에 세상에서 제일 강력한 컴퓨터로도 엄청나게 긴 시간 동안 작업을 해야 합니다.

그러면 이렇게 얘기할 수도 있겠지요. 컴퓨터를 계속 돌리면 언젠가는 암호를 깰 수 있지 않겠냐고 말입니다. 실제로 RSA 방식의 암호를 만들어 낸 수학자들에게 그와 같은 문제 제기가 있었다고 합니다. 이에 대해 그 수학자들은 해독하는 데 ‘수백만 년’이 걸릴 것이라며 아래와 같은 ‘간단한’ 129자리 숫자를 제시하면서 이 수를 소인수분해해 보라고 제시했다고 합니다.

114381625757888867669235779976146612010218296721242362562561842
935706935245733897830597123563958705058989075147599290026879543541

그 수학자들은 위의 소수를 이용해서 암호화시켜 놓은 암호문을 해독하는 것이 불가능할 것이라 확신했고, 그들의 암호문이 안전할 거라 큰소리쳤습니다. 그런데 1993년 전 세계 약 600여명의 학자와 관심 있는 사람이 모여서 인터넷을 통한 공동 작업으로 이 129자리 숫자를 공격해 보자는 프로젝트를 시작합니다. 그러고 나서 일 년도 못 되어서 문제의 두 개의 소수를 알아냅니다. 하나는 64자리 수이고, 다른 하나는 65자리 수였습니다. 이 사건이 있고 나서 129자리 키는 정말 중요한 정보를 암호화하기엔 부족하다는 사실을 모두가 알게 되었습니다. 이처럼 컴퓨터를 계속 돌린다면 아무리 큰 수일지라도 기술이 발달하면 소인수분해되겠지만, 아주 긴 시간이 걸린다는 사실은 여전히 변함없습니다. 수학자들은 컴퓨터 성능이 아무리 좋아져도 250자리 수를 소인수분해하는 데는 수백만 년 이상이 걸릴 거라고 얘기합니다.