가장 큰 소수(素數) 찾기

1천달러 상금의 주인은 누구?

지난 1월 캘리포니아 주립대의 한 시골 캠퍼스에 다니는 19세의 롤랜드 클락슨은 펜티엄 컴퓨터를 이용해 이때까지 발견한 어느 소수보다 큰 소수(${2}^{3021377}$－1)를 발견했다.

이 소수는 10진법으로 환산하면 90만9천5백26자리가 되며, 1cm에 4개씩 들어가는 활자(12포인트)로 과학동아 지면을 4백55장 메꿀 수 있을 만큼 큰 수다. 그냥 한 줄로 쓰면 2.3km나 뻗어나간다. 매일 8시간씩 한달 동안 읽어야 할 만큼 긴 수가 1을 제외하고 자신보다 작은 수로 나누지지 않는다는 사실이 좀처럼 믿어지지 않는다.

자연수 중에서 1과 자신으로밖에 나누어지지 않는 수, 즉 2, 3, 5, 7, 11,…과 같은 수를 소수(素數)라고 한다. 소수가 무한히 많다는 것은 기원전 3세기경에 유클리드(기원전 303?-275?)가 쓴 '원론'에도 증명돼 있다. 소수의 개념은 간단하지만 아직 많은 미해결의 문제를 가지고 있다. 그래서 어떤 수학자는 소수를 '수론(數論)의 꽃'이라고 부르기도 한다.
 

(표1) 53자리 미만의 완전수^6,28,496,8128 등은 기원전에 이미 완전수로 알려졌다.

컴퓨터 성능 진단

소수는 컴퓨터 발달과 더불어 날로 중요성이 더해가고 있다. 컴퓨터 성능을 확인할 때 소수만큼 유용한 것이 없기 때문이다. 미리 알고 있는 소수를 컴퓨터에게 찾아보라고 해서 그 결과를 비교해보면 컴퓨터가 제대로 계산해내는지를 알 수 있기 때문이다.

이와 달리 컴퓨터를 이용해 새로운 소수를 찾기도 한다. 1963년 일리노이대 디지털컴퓨터연구소에 근무하던 도널드 길리스(1928-75)는 새로 개발한 슈퍼컴퓨터 일리악 II를 시험하는 과정에서 ${2}^{9689}$－1, ${2}^{9941}$－1, ${2}^{11213}$－1 등 세 소수를 발견했다. 이와 같이 새로운 컴퓨터를 설계하거나 설치할 때는 성능을 시험하기 위해 큰 소수를 찾거나 소수점 아래 수십만 자리의 π값을 계산한다. 일리노이대에서는 길리스의 업적을 기리기 위해 우편물에 우표 대신 '${2}^{11213}$－1은 소수'라는 글을 넣은 스탬프를 찍고 있다(사진1).

${2}^{11213}$－1은 1971년에 터커맨이 ${2}^{19937}$－1을 발견할 때까지 무려 8년 동안이나 가장 큰 소수의 자리를 지켰다. 그런데 터커맨의 기록도 1978년 캘리포니아주에 사는 로라 닉켈과 커트 놀이라는 두 고등학생에 의해 깨지고 말았다. 두 학생은 이웃 대학의 대형컴퓨터를 4백40시간 동안 돌려 소수 ${2}^{21701}$－1를 찾았다. 닉켈과 놀의 최대 소수 발견은 뉴욕타임스 1면을 장식했고, 그들의 얼굴은 TV를 통해 전세계에 소개됐다. 놀은 이듬해에 ${2}^{23209}$－1을 찾아 자신의 기록을 다시 갱신했다.

그러나 놀의 기록은 오래가지 않았다. 같은 해에 크래이컴퓨터연구소에 근무하는 데이비드 슬로빈스키가 ${2}^{44497}$－1을 찾아 그 기록을 깬 것이다. 그는 1996년까지 7번이나 기록을 갱신하며 소수 찾기 최다 기록 보유자가 됐다.

여기 소개한 소수들은 모두 2n－1의 꼴을 갖고 있다. 이런 꼴의 소수를 17세기 프랑스 신부 메르센(1588∼1647)의 이름을 따서 '메르센 소수'라고 한다. 예를 들면 3 = 22－1, 7 = 2³－1, 31 = ${2}^{5}$－1 들이다. 그러나 소수가 모두 메르센 소수는 아니다. 2, 5, 11, 13, 등은 2n－1의 꼴로 나타내지 못한다. 이런 소수를 '비(非) 메르센 소수"라고 한다. 또 p가 소수일 때 2p－1이 소수가 아닐 경우도 있다. 그래서 p가 소수일 때 2p－1의 꼴의 수를 그냥 '메르센 수'라고 부른다.

많은 사람들은 p가 소수일 때 메르센 수(Mp = 2p－1)는 모두 소수일 것이라고 추측했다. 그런데 1536년 2¹¹－1(= 2047)이 23×89로 소인수분해돼 M11이 소수가 아님이 밝혀지면서 큰 소수 찾기 경쟁이 일어났다. 그 와중에 소수로 증명됐던 것이 소수가 아닌 합성수로 밝혀진 예도 허다했다. 1588년 피에트로 카탈디가 소수라고 밝힌 M23, M29, M31, M37 중에서 소수로 살아남은 것은 M31뿐이고 나머지는 소수가 아니라고 밝혀졌다.

메르센 소수를 만든 메르센 역시 같은 실수를 범했다. 그는 1644년 그의 저서 '물리·수학론'에서 p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257일 때 Mp가 소수라고 말했다. 그러나 M67과 M257은 합성수임이 각각 259년과 287년이 지난 1903년과 1931년에 밝혀졌다. 또 p≤257인 지수 중에서 61, 89, 107이 소수임이 1883년, 1911년, 1914년에 발견됐다. 컴퓨터를 쓰지 않고 찾은 가장 큰 소수는 1876년 루카스가 찾아낸 39자리의 수 M127였다.

M127 = 170,141,183,460,469,231,731,687,303,715,884,105,727

컴퓨터를 써서 메르센 소수를 찾는 데 처음으로 성공한 사람은 라팰 로빈슨이다. 그는 1952년에 무려 5개의 메르센 소수 M521, M607, M1279, M2203, M3217을 찾았다. 로빈슨이 찾은 소수는 1876년에 루카스가 찾은 소수보다 4배 이상 자릿수가 뛰었다. M127과 M521 사이에는 더 이상 메르센 소수가 없었다.

최근 최대 소수의 기록을 세운 것들은 모두 메르센 소수다. 그 이유는 메르센 수가 소수인지 아닌지를 쉽게 구별하는 루카스-레머 판정법 때문이다. {Sn}을 S1=4, Sn+1=Sn2-2로 정의된 수열이라고 할 때, p가 홀수이면 메르센 수 Mp=2p-1은 Mp가 Sp-1을 나눌 때만 소수이다. 이것이 루카스-레머 판정법이다.

저스트 포 펀(Just For Fun) 소프트웨어사에 근무하는 조지 월트만은 루카스-레머 판정법을 소형컴퓨터(PC, Mac, Unix)에도 쓰도록 프로그램을 만들어 인터넷(http://www.mersenne.org/prime.htm)에 올려놓았다. 그래서 누구나 이 프로그램을 다운로드 받으면 최대 소수를 찾는데 도전할 수 있다. 이 프로그램으로 찾은 메르센 소수들로는 M1398269(1996년)와 M2976221(1997년)가 있다. CPU 생산업체로 잘 알려진 인텔은 펜티엄 칩들을 출하하기 전에 월트만 프로그램으로 성능을 검사하고 있다. 현재 미국에서는 월트만 프로그램을 이용해 학생들이 수학에 흥미를 갖도록 교육하고 있다.
 

(사진1) 길리스가 발견한 소수^일리노이대 우표 대신 찍는 스탬프에는 길리스가 발견한 소수가 기록돼 있다.

38번째 메르센 소수를 찾아라

6의 약수 중 5보다 작은 수 1, 2, 3을 모두 합치면 6이 된다. 또 28의 약수 중 28보다 작은 수 1, 2, 4, 7, 14를 더하면 28이 된다. 이처럼 자신보다 작은 약수를 모두 합쳤을 때 원래의 수가 되는 수를 완전수(perfect number)라고 한다.

기원전 그리스 시대에 이미 4개의 완전수(6, 28, 496, 8128)가 있다는 것이 알려졌지만, 그 수는 많지 않다. (표1)의 수들은 53자리 미만의 완전수를 나타낸 것이다. "2p-1이 소수이면 2p-1(2p-1)은 완전수다"라는 것은 이미 유클리드의 '원론'에 증명돼 있다. 그런데 18세기 중엽에 오일러가 짝수인 완전수는 모두가 2p-1(2p-1)의 꼴로 나타내지며, 이때 (2p-1)은 소수인 것을 증명했다. 따라서 짝수인 완전수의 개수와 메르센 소수의 개수는 같다.
 

(표2) 최근 발견된 소수와 완전수

여기에 2가지 미해결 문제가 있다. 하나는 과연 홀수인 완전수는 존재하는가 하는 문제고, 다른 하나는 메르센 소수는 무한히 많은가 하는 점이다. 1991년 3백자리 이하의 홀수 중에는 완전수가 없음이 밝혀졌지만, 아직도 홀수인 완전수가 없는지는 알 수 없다. 그리고 이제까지 발견된 메르센 소수의 개수는 완전수의 개수와 같다. (표2)은 최근 발견된 소수와 완전수이다. (표2)에서 마지막 두 지수 2976221과 3021377에 순서를 붙이지 않은 이유는 그 사이에 메르센 소수가 더 있는지 모르기 때문이다.

앞서 인터넷을 올려진 월트만 프로그램을 이용해 처음 찾은 소수는 클락슨이 발견한 M3021377이다. 이 소수는 발견 순서로 보면 37번째에 해당한다. 메르센 소수 찾기 프로그램을 운영하는 IPS(Internet PrimeNet Server의 약자)는 미화 1천달러의 상금을 걸고 38번째(발견 순서로) 메르센 소수를 찾고 있다. 38번째 메르센 소수는 M3021377보다 작을 수도 있다. 만약 38번째 메르센 소수의 자릿수가 1백만자리를 넘으면 1천자리마다 1달러씩 더 준다고 한다. 클락슨이 발견한 소수 M3021377(909, 526의 자릿수를 가짐)를 예로 들면, 그는 9백9달러를 받을 수 있다.
 

과학동아