소수란 무엇인가?

제 2부. 소수의 종류에는 무엇이 있을까?

✔ 시작하기에 앞서서...

제 1부에서 소개한 소수(Prime Number)의 수학적 정의는 1과 자기 자신 이외의 다른 양의 정수로 나누어지지 않는 1보다 큰 정수라고 하였습니다. 이번 칼럼에서는 이 정의를 확장하여 더욱 이색적이고 특별한 소수의 종류에 대해서 소개하겠습니다. 소수의 종류에는 에라토스테네스의 체(Sieve of Eratosthenes), 페르마 소수(Fermat Prime), 메르센 소수(Mersenne Prime), 쌍둥이 소수(Twin Prime), 다계승 소수(Multifactorial Prime), 제르맹 소수(Germain Prime), Primorial Prime 등 많은 종류의 소수가 있습니다. 따라서 지금부터 소수의 종류에 대해 하나씩 알아보도록 하겠습니다.

※ 소수를 찾아내는 방법의 종류라고 생각해주시면 됩니다.

✔ 에라토스테네스의 체 (Sieve of Eratosthenes)

 중학교 1학년 수학 시간에 소수에 대해 처음 배우면서 슬쩍 구경하고 지나치는 정도로 접한 그 방법입니다. 하지만 인류는 오랜 옛날부터 소수에 대해 관심이 많았기에 찾아내는 방법 또한 옛날부터 알게되어 지금까지 전해져 왔습니다. 그 중에서 잘 알려진 방법이 "에라토스테네스의 쳬" 라고 말할 수 있습니다. "에라토스테네스의 체" 는 그리스 출신의 에라토스테네스가 고안한 방법으로 그는 그리스의 지리학자이며, 시인이며, 천문학자며, 수학자였습니다. "에라토스테네스" 라는 분은 아마 중학교 과학시간에 배울 때 지구의 둘레를 상당히 정확한 정도로 처음 잰 사람으로 유명하다고 배웠을 것입니다. (제가 배울땐 3학년 1학기에 있었는데 있던걸로 기억합니다.) 그 외에도 자전축이 기울어진 정도 역시 상당히 정확하게 측정했었고, 위도, 경도의 개념을 만들기도 하였습니다.

 에라토스테네스가 수학에 남긴 족적으로 "에라토스테네스의 체" 라고 부르는 소수 생성법이 있습니다. 이름에서 알 수 있듯이 자연수를 "체"로 쳐서 "소수"만 골라내는 방법으로 간단히 아래에 박스에서 알아보겠습니다.

 특정 숫자 이하의 모든 소수를 찾는 방법 중 이보다 더 단순한 방법은 없을 것 같아 보입니다. 단순한 방법이지만 의외로 효율이 좋아서, 발견된 지 2000년이 훌쩍 넘은 현재까지도 작은 규모의 소수를 찾는데 제법 애용되는 방법이며, 컴퓨터 프로그래밍의 예제로 단골처럼 등장하고 있습니다.

 ✔ 페르마 소수 (Fermat Prime)

 먼저 페르마는 왼쪽 형태의 모든 수는 소수일 것이라고 짐작했습니다. 그래서 우리는 이것을 페르마 수라고 부르고 왼쪽의 수가 소수일 때, 그것을 페르마 소수라고 부릅니다. 현재까지 밝혀진 페르마소수는 처음의 5개의 페르마 수 (3,5,17,357,65537) 입니다. 이로 볼 때 단지 유한개의 페르마 소수가 있는 것처럼 보입니다. 1732년에 오일러는 641이 65537을 나눈다는 것을 발견했습니다. 이것은 오일러가 2보다 큰 n을 가지는 Fn 의 모든 약수는 형태를 가진다는 것을 보여줬기 때문에 이 인수를 찾기 위한 시도에서 얻어진 것이였습니다. F5 (=65537) 의 경우 위와 같은 방식으로 나타내면 n=5 이므로 꼴입니다. 257과 641을 시도해보겠습니다. 현재 129, 385, 513은 소수가 아니기에 필자는 31보다 작으면서 n이 아닌 다른 수를 가지는 페르마 수는 합성수라는 것을 알게 됩니다. 즉, 최초의 페르마 수를 찾기 위한 가장 빠른 방법 (만약 더 작은 인수를 찾기 위한 나누는 시도가 실패했을 경우)은 Pepin's test를 사용하는 것입니다.

 페르마 수의 인수분해 방법은 와 같은 종류의 x와 y를 찾는 것으로 이루어져 있습니다. 방정식의 좌변은 로 인수분해 되고, 만약 x-y 가 1이 아닐 때 non-trivial factorization 을 찾을 수 있습니다. 이 아이디어를 이용해 여러가지 새로운 사실들을 알 수 있습니다.

 예를 들어, 을 푸는 대신에 우리는 형태의 x와 y를 찾을 수 있습니다. 이것은 n이 을 나누고, x가 y와 mod n 에 대해 같지 않으면, gcd(x-y, n) 혹은 gcd(x+y, n) 이 n의 non-trivial factor 이여야 한다는 뜻이 됩니다. 예를 들어, n=91 인 인수를 가정해 봅시다. 처음 몇 번의 제곱수는 mod 91 에 대해 1, 4, 9, 16, 25 등으로 나타나게 됩니다. 여기서 임을 알 수 있습니다. 그리고 91의 적절한 약수가 gcd(10-3, 91)=7 혹은 gcd(10+3, 91)=13 인지 예상할 수 있습니다. 페르마의 방법이 인수들을 찾는 효과적인 방법이라 생각하기엔 힘들지만 더 많은 현대적 방법들을 탄생시킨 기반이 되었으므로 매우 중요하다고 할 수 있습니다. 최근의 소수판정법인 이차체, 다항식 이차체, 그리고 "The special and the general number field sieves" 는 모두 이 방법에 기반을 두고 있습니다.

✔ 메르센 소수 (Mersenne Prime)

소수가 무한히 많다는 것이 증명되었지만 소수가 어떤 특별한 형태를 갖는지는 아직 발견되지 않았습니다. 따라서 큰 소수를 구하기 위해 특별한 경우를 살펴보아야 합니다. 수학에는 특별한 이름이 붙은 수가 많이 있습니다. 그 중에는 2의 거듭제곱에서 1만큼 모자라는 메르센 수라는 것이 있습니다. 즉, 지수 n에 대한 메르센 수를 2의 n거듭제곱에서 1만큼 부족한 수를 나타냅니다.

 메르센 수는 프랑스 수학자 메르센(Marin Mersenne, 1588~1648) 의 이름을 딴 것입니다. 메르센 수에서 3, 7, 31 등과 같이 특히 소수인 것을 메르센 소수라고 하는데, 메르센 수가 메르센 소수가 되기 위해서는 2의 지수인 n이 소수라는 사실이 밝혀졌습니다. 메르센 소수는 몇 년에 하나씩 발견되다가 최근에는 거의 매년 하나씩 새로 발견되고 있습니다.

 2003년 10월에 발견된 40번째 메르센 소수 M(20996011) 는 2GHz 의 펜티엄 4 컴퓨터를 19일동안 가동하여 찾았습니다. 2004년 6월에 발견된 41번째 메르센 소수 M(24036583) 는 무려 723만 5733 자리의 수로 손으로 쓰는데 6주가 걸리며, 수를 쓴 길이는 25km 에 달한다고 합니다. 2005년 2월에 발견된 42번째 메르센 소수 M(25964951) 는 2.4GHz 의 펜티엄 4 컴퓨터를 50일 동안 가동하여 찾았습니다. 2005년 12월에 쿠퍼 교수팀에 의해 발견된 43번째 메르센 소수 M(30402457) 는 915만 2052 자리의 수입니다. 그리고 쿠퍼 교수는 1년도 채 지나지 않은 2006년 9월에 44번째 메르센 소수 M(32582657) 을 또 찾았습니다.

 사실 1000만 자리가 넘는 메르센 소수를 찾는 사람에게는 10만 달러의 상금이 걸려 있었지만, 아쉽게도 44번째 메르센 소수도 1000만 자리는 넘지 못했습니다. 12457 로 시작하여 967871 로 끝나는 이 소수는 손으로 쓰는데 꼬박 9주가 걸리고 수의 길이는 34km 정도나 된다고 합니다.

 최근에 찾아진 메르센 소수는 2008년 8월 23일 미국의 한 대학 연구원인 한스와 마이클에 의해서 발견되었습니다. 그들이 찾은 소수는 약 1300만 자리의 수인 M(43112609) 로 이 수는 손으로 쓰려면 약 12주가 걸리고 그 길이만 해도 약 44km 정도가 된다고 하니 정말 어마어마하게 큰 소수입니다. 어쨌든 그들은 이 소수가 45번째 메르센 소수라고 생각했지만 같은 해 9월 6일에 미국 캘리포니아 버클리 대학의 연구팀에 의하여 45번째 메르센 소수 M(37156667) 이 발견되어 한스와 마이클이 발견한 소수는 46번째 메르센 소수로 기록되었습니다. 45번째 메르센 소수도 1000만 자리가 넘었지만 불과 며칠 사이로 10만 달러의 상금을 못 타게 되었으니 안타까운 일입니다. 그런데 중요한 것은 39번째 메르센 소수인 M(13466917) 과 46번째 메르센 소수인 M(43112609) 사이에 다른 메르센 소수가 더 있을지도 아직까지 확실하게 알려져 있지 않습니다. 그래서 만일 그 사이에 다른 메르센 소수가 발견된다면 번호가 바뀔 수 있습니다.

소수란 무엇인가?

제 1부. 소수의 중요한 성질과 생활에서의 적용