메르센 소수, GIMPS

그저께 오랜만에 GIMPS가 불현듯 떠올랐다. 그에 대한 글을 써보기로 했다.

 

GIMPS는 Great Internet Mersenne Prime Search의 약자로, 큰 소수를 찾는 프로젝트라고 할 수 있다.

 

 

흔히 엄청나게 큰 수가 소수인지를 판별하는 것은 매우 어렵다.

가장 평범한 방법이 제곱근 이하의 소수들로 나누어보는 것일 것이고.. 이는 1해 정도의 숫자만 가도 상당히 버겁다.

AKS 알고리즘을 사용하면 다항 시간 내에 판별이 가능하다고는 하지만, 그마저도 큰 수에 대해서는 상당히 오래 걸릴 것이다...

 

하지만, '특정 형태의 소수'에 대해서는 굉장히 빠른 시간 내에 소수임을 판별할 수 있는 알고리즘이 존재한다.

그 형태중 대표적인 것 중 하나가 메르센 소수이다.

 

메르센 소수는 2^p - 1 형태를 가지는 소수로, 3, 7, 31, 127 등이 있겠다..

특이한 점은 이 때 p도 소수여야 한다는 것이다.

p = 2, 3, 5, 7일 때 2^p - 1은 각각 3, 7, 31, 127로 소수이므로 p가 소수면 2^p - 1도 항상 소수라고 생각할 수 있지만, 2^11 - 1 = 2047 = 23 * 89로 이는 성립하지 않는다.

 

메르센 소수가 무한히 많이 존재하는지, 그 규칙이 있는지 등은 아직까지도 알려지지 않았다.

 

현재까지 50개의 메르센 소수가 발견되었는데, 딱 봐도 별 규칙이 있어 보이지는 않는다.

 

메르센 소수의 특별한 성질 중 하나로, 메르센 소수와 완전수(자신을 제외한 약수의 합이 자기 자신)가 한 쌍으로 같이 논다는 것이다.

m이 메르센 소수이면, m * (m + 1) / 2가 완전수라는 것을 보이기는 그리 어렵지 않다. 모든 짝수 완전수는 다 이 형태이며, 홀수 완전수는 아직 발견되지 않았다고 한다. 참으로 아름답다.

 

이런 메르센 소수를 찾는 프로젝트가 바로 GIMPS이다. 워낙 많은 연산량이 필요하니 될 성 싶은 후보 p를 하나씩 할당받고, 컴퓨터를 쭉 돌렸을 때 메르센 소수로 판명되면 소수의 발견자로 기록되는 것이다. 메르센 소수가 워낙 넘사벽으로 크기 때문에, 방에서 가만히 앉아서 머리도 안 쓰고 '세계에서 가장 큰 소수'를 발견한 사람으로 기록될 수 있는 것이다. 상당한 운빨망겜이라고 볼 수 있다.

 

내가 한창 이거를 열심히 할 때가 2015년도였던 것 같은데, 당시에 5700만에 메르센 소수가 존재한 뒤 7000만까지 거의 검사가 될 동안 메르센 소수가 나오지 않고 있었다. 나올 때가 된 것 같아서, 한국인 최초의 메르센 소수 발견자가 될 수 있는 기회인 동시에 학교를 홍보할 수 있는 기회다 싶어서 학술정보관 컴퓨터 등을 이용해 상당히 열심히 돌렸다. 전기세에 대해서는 상당히 죄송하다(...) 사실 그리 엄청나게 많이 나오지는 않았지 싶다.

 

학술정보관 정보검색대 cpu가 정보검색대 주제에 Intel Xeon E3-1225였고, 그런 정보검색대가 3층에만 8대 정도 놀고 있었다. 가끔씩 시간이 날 때, 프로그램을 실행시켜주었다.

그리고 2016년 1월에 p = 74207281짜리 메르센 소수가 발견되자 바로 접었다. 대략 내가 7000~7500만 범위에서 놀고 있었고, 그 범위에 LL을 돌려야 하는 소수가 10만 개 정도 있었으고, 내가 25개 정도 돌렸으니 0.025%의 확률로 나도 역사에 남을 수 있었다(...)

 

아무쪼록, GIMPS라는, 세계에서 가장 큰 소수를 찾겠다는 프로젝트는 상당히 흥미로웠고 그래서 나름 그렇게 열중했던 것 같다.

 

지금 생각해보면, 단순히 이렇게 큰 소수를 찾는게 무슨 의미가 있나 싶기는 하다. 역시 하루 빨리 리만 가설이 증명되어야 할 것 같다.

약간 세계적으로 전기도 아깝고 하니 p = 1억 정도까지만 돌리면 좋겠는데, 10억까지 돌릴 속셈인가 보다. 대단한 사람들이다..

하기야 비트코인 채굴하는 데에 드는 전기랑 비교하면... ㅋㅋ

 

최근에 갑자기 기억이 나서 내역을 살펴보니, 대부분 컴퓨터에서는 전멸했고 컴퓨터 한 대에서 2018년 5월까지 꾸준하게 돌아가고 있었다..

 

지금까지 돌린 총 양이 27637GHz-days다. 1GHz-day는 펜티엄 뭐시기였나? 1GHz인 특정 cpu로 하루동안 돌린 연산량을 기준으로 삼은 것이다. 100년에 해당하는 36500GHz-days를 채우고 싶은 마음이 있었으나 지금 추가로 10000GHz-day를 채울 자신은 안난다. 저 남아있는 컴퓨터 한 대에서 꾸준히 돌아간다면 가능하지 않을까..

Trial factoring은 13,288개를, LL은 총 108개를 돌렸다. 엄청나게 많은 것이다.

 

지금부터는 GIMPS를 돌리는 데에 사용되는 알고리즘을 살펴보자.

 

http://jeonggyun.tistory.com/139

 

 

 

/* 200508 내용추가 */

5월 3일 22시 43분에 p = 56,720,431에 대한 Double Checking이 끝남에 따라 목표했던 36500GHz-days(=100GHz-years)를 달성하게 되었다.

1GHz-day는 1GHz Core 2 Duo CPU의 한 개의 코어에서 하루를 돌렸을 때, 이론적으로 낼 수 있는 computing power라고 한다. 해당 코어로 100년을 돌려야 달성할 수 있는 분량까지 달성하였다.

 

현재 진행되고 있는 것까지만 마무리되면, 이제 메르센 소수에 대한 관심은 끌 듯 하다.

 

어떤 수가 매우 큰 소수인지, 정확히 n번째 메르센 소수가 맞는지를 판단하기 위해 이렇게 많은 computation cost를 들이고 있지만 사실은 이게 크게 의미있는 일은 아니다. 마치 원주율 소수점 아래 50조 자리를 구하는 것이 기계의 performance를 과시하는 것 외에 큰 의미가 없는 것처럼. 이를 구할 수 있는 알고리즘이 존재한다는 사실이 더 중요하다.

 

메르센 소수를 판별할 수 있는 PRP알고리즘이라는 것이 대세로 떠오르는 모양세인데, 이 부분에 대해서는 추후에 한 번 공부를 해 보고 싶다. 공부할 게 많아서 좋다.