GIMPS(The Great Internet Mersenne Prime Search)는 메르센 소수를 찾는 온라인 프로젝트이다. Prime95와 같은 프로그램으로 전 세계의 컴퓨터 상에서 계산을 돌리는 분산 컴퓨팅 방식을 이용한다. 소프트웨어가 깔린 모든 컴퓨터는 GIMPS의 서버와 연동하여 계산 과제를 받고, 해당 미션을 완수할 때마다 결과를 서버에 제출한다.
1996년에 설립하여 현재까지도 소수 찾기가 진행 중이다. 간혹 신문이나 인터넷에서 "알려진 가장 큰 소수 발견"이라는 제목의 기사를 접했다면, 99%가 이 프로젝트에서 나온 것이라 보면 된다.
발견한 소수[편집 | 원본 편집]
이 프로젝트가 시작되기 전까지 발견된 메르센 소수는 총 34개였다. 여기에 2022년 8월 15일까지 17개를 추가로 발견하여 51개까지 확인되었다. 자세한 기록은 GIMPS Milestones Report에서 확인할 수 있다.
| 순번 | 메르센 소수 | 발견 일시 | 날짜 간격 | 발견자 | CPU | 순번 공인[1] |
|---|---|---|---|---|---|---|
| 35 | [math]\displaystyle{ M_{1398269} }[/math] | 1996년 11월 13일 | +71일[2] | Joel Armengaud | 90 MHz Pentium PC | 1998년 12월 18일 |
| 36 | [math]\displaystyle{ M_{2976221} }[/math] | 1997년 8월 24일 | +284일 | Gordon Spence | 100 MHz Pentium PC | 2000년 5월 19일 |
| 37 | [math]\displaystyle{ M_{3021377} }[/math] | 1998년 1월 27일 | +156일 | Roland Clarkson | 200 MHz Pentium PC | 2000년 5월 19일 |
| 38 | [math]\displaystyle{ M_{6972593} }[/math] | 1999년 6월 1일 | +490일 | Nayan Hajratwala | 350 MHz Pentium Ⅱ IBM Aptiva | 2003년 2월 2일 |
| 39 | [math]\displaystyle{ M_{13466917} }[/math] | 2001년 11월 14일 | +897일 | Michael Cameron | 800 MHz Athlon Thunderbird | 2006년 7월 10일 |
| 40 | [math]\displaystyle{ M_{20996011} }[/math] | 2003년 11월 17일 | +733일 | Michael Shafer | 2 GHz Dell Dimension | 2010년 7월 11일 |
| 41 | [math]\displaystyle{ M_{24036583} }[/math] | 2004년 5월 15일 | +180일 | Josh Findley | 2.4 GHz Pentium 4 PC | 2011년 12월 1일 |
| 42 | [math]\displaystyle{ M_{25964951} }[/math] | 2005년 2월 18일 | +279일 | Martin Nowak | 2.4 GHz Pentium 4 PC | 2012년 12월 20일 |
| 43 | [math]\displaystyle{ M_{30402457} }[/math] | 2005년 12월 15일 | +300일 | Curtis Cooper & Steven Boone |
2 GHz Pentium 4 PC | 2014년 2월 23일 |
| 44 | [math]\displaystyle{ M_{32582657} }[/math] | 2006년 9월 4일 | +263일 | Curtis Cooper & Steven Boone |
3 GHz Pentium 4 PC | 2014년 11월 8일 |
| 47[3] | [math]\displaystyle{ M_{43112609} }[/math] | 2008년 8월 23일 | +719일 | Edson Smith | Dell Optiplex 745 | 2018년 4월 8일 |
| 45 | [math]\displaystyle{ M_{37156667} }[/math] | 2008년 9월 6일 | +14일[4] | Hans-Michael Elvenich | 2.83 GHz Core 2 Duo PC | 2016년 9월 2일 |
| 46 | [math]\displaystyle{ M_{42643801} }[/math] | 2009년 6월 4일 | +271일 | Odd M. Strindmo | 3 GHz Core 2 PC | 2018년 2월 22일 |
| 48 | [math]\displaystyle{ M_{57885161} }[/math] | 2013년 1월 25일 | +1331일 | Curtis Cooper | Intel Core2 Duo E8400 @ 3.00GHz | 2021년 10월 6일 |
| 49? | [math]\displaystyle{ M_{74207281} }[/math] | 2016년 1월 7일 | +1077일 | Curtis Cooper | Intel i7-4790 @ 3.60GHz | 비공식 순번[5] |
| 50? | [math]\displaystyle{ M_{77232917} }[/math] | 2017년 12월 26일 | +719일 | Jon Pace | Intel i5-6600 @ 3.30GHz | 비공식 순번 |
| 51? | [math]\displaystyle{ M_{82589933} }[/math] | 2018년 12월 7일 | +346일 | Patrick Laroche | Intel i5-4590T @ 2.0GHz | 비공식 순번 |
시간이 지나면서 컴퓨터의 성능은 거듭 향상되어서 계산 속도도 그만큼 빨라졌다. 반면 메르센 소수의 지수 간격은 수가 커질수록 급격히 벌어지는 데다, 메르센 수 하나의 소수 여부를 검사하는데 필요한 계산량은 지수의 제곱에 비례한다. 이러한 요소로 인해 메르센 소수의 발견 날짜 간격은 대체로 늘어나고 있으며, 특히 CPU의 4 GHz의 벽과 같은 하드웨어 관련 변수도 프로젝트 진행 속도를 크게 좌우한다.
진행 과정[편집 | 원본 편집]
먼저 메르센 수 [math]\displaystyle{ M_p=2^p-1 }[/math]이 소수가 되기 위한 필요조건은 지수인 [math]\displaystyle{ p }[/math]가 소수라는 것이다. 따라서 메르센 소수를 찾기 위한 후보는 곧 지수로 올릴 '소수 목록'이다. 이제 여기서 소수가 아닌 것들을 노가다로 소거해 나간다. 자세한 내용은 Mathematics and Research Strategy 참고.
직접 나누기[편집 | 원본 편집]
특정 메르센 수 내에서 작은 소인수가 존재하는지 여부를 알아낸다. 약수와 관련한 중요한 성질을 활용한다. 아래 성질의 증명은 메르센 소수 문서를 참고.
[math]\displaystyle{ q }[/math]가 [math]\displaystyle{ M_p }[/math]의 소인수일 때, [math]\displaystyle{ q \equiv 1 \pmod{2p} }[/math] 및 [math]\displaystyle{ q \equiv \pm1 \pmod{8} }[/math]가 성립한다.
따라서 굳이 모든 소수들로 나누어 떨어짐 여부를 확인하지 않아도 되며, 위의 조건을 만족하는 소수들만을 추려서 테스트를 시행한다.
만약 어떤 소수 [math]\displaystyle{ q }[/math]가 [math]\displaystyle{ M_p }[/math]의 약수인지를 알고 싶다면, 통상 나눗셈으로 확인할 수 있지만 좀 더 간편한 방법이 있다. 원래라면 [math]\displaystyle{ M_p=2^p-1 }[/math]의 값을 입력하고자 [math]\displaystyle{ p }[/math]비트의 변수를 지정해야 하지만, 실제로는 [math]\displaystyle{ \lceil \log_{2}q \rceil }[/math]비트만으로 검사가 된다.
[math]\displaystyle{ q \mid M_p \Leftrightarrow 2^p \equiv 1 \pmod{q} }[/math]임을 이용하고, 모듈러산술로 2의 거듭제곱을 시행한다. 이를테면 233이 [math]\displaystyle{ M_29 }[/math]의 약수인지를 알고자 한다면, 아래와 같이 검사한다.
29를 이진법으로 전개하면 비트는 '11101'과 같이 써진다. 맨 왼쪽부터 차례대로 비트를 받고 연산을 시행한다. 비트가 1이면 제곱하고 비트를 한 자리 민 뒤 233으로 나눈 나머지를 셈한다. 비트가 0이면 제곱만 하고 233으로 나눈 나머지를 셈한다.
초깃값: 1 비트: 1 || (1*1<<1)%233 = 2 비트: 1 || (2*2<<1)%233 = 8 비트: 1 || (8*8<<1)%233 = 128 비트: 0 || (128*128)%233 = 74 비트: 1 || (74*74<<1)%233 = 1
이렇게 해서 최종 결과가 1이 나오면 [math]\displaystyle{ 2^{29} \equiv 1 \pmod{233} }[/math] 즉 [math]\displaystyle{ 233 \mid M_{29} }[/math]를 의미하며, [math]\displaystyle{ M_{29} }[/math]는 합성수라는 사실을 알 수 있다.
만약 이 단계에서 소인수를 하나라도 발견한다면, 그 수는 합성수임이 판명나므로 메르센 소수 후보에서 탈락한다. 물론 이 검사를 무한정 시도하지는 않고, 보통은 [math]\displaystyle{ 2^{75} }[/math] 부근까지 확인한다. 이 기준선은 지수가 올라감에 따라 같이 커진다. 대략 60% 정도가 이 첫 단계에서 걸러진다.
[math]\displaystyle{ p-1 }[/math] 소인수분해[편집 | 원본 편집]
이와 관련한 내용은 폴라드 p-1 소인수분해법에서 볼 수 있습니다.위의 직접 나누기 단계를 통과한 후보들은 이제 다른 방식으로 소인수를 찾아낸다. 여기서는 폴라드 p-1 소인수분해법을 이용하는데, 메르센 수의 특수성을 이용하여 셈법을 조금 변형한다. 자세한 계산은 해당 문서 참고.
페르마의 소정리에 따르면 어떤 소수 [math]\displaystyle{ q }[/math]와 서로소인 자연수 [math]\displaystyle{ a }[/math]에 대해 [math]\displaystyle{ a^{q-1} \equiv 1 \pmod{q} }[/math]가 성립한다. 이를 다시 표현하면, 만일 이 소수가 메르센 수 [math]\displaystyle{ M_p }[/math]의 약수라면 [math]\displaystyle{ q \mid \gcd(a^{K(q-1)}-1, M_p) }[/math]가 되어서 소인수를 찾을 수 있게 된다. 그리고 여기서 비자명한 약수가 나온 수는 마찬가지로 소수 후보에서 탈락한다. (남은 후보 중 5% 정도가 또 걸러진다)
참고로 바로 위 문단에서 언급했듯이 [math]\displaystyle{ q \mid M_p \Rightarrow 2p \mid q-1 }[/math]이라는 사실을 알고 있다. 따라서 [math]\displaystyle{ a=3^{2p} }[/math]로 잡고 시작하면 좀 더 수월하게 소인수를 찾을 수 있다.
소수 여부 판정[편집 | 원본 편집]
이와 관련한 내용은 뤼카-레머 소수판정법에서 볼 수 있습니다.앞서 살펴본 직접 나누기 및 p-1 소인수분해 단계는 후보를 소거하는 데 필요한 연산량이 상대적으로 적어서 이들을 먼저 시행하는 것이다.
위의 검사를 거치고도 탈락하지 않았다면, 이제 큰 수에 대해 소수 여부를 빠르게 가려내는 검사를 시행한다. 바로 뤼카-레머 소수판정법이다. 그런데 여기서 '빠르게'라는 것은 매우 큰 소수를 '사람이 감당할 수 있는 시간 내로' 알아낼 수 있다는 뜻이며, 실제로는 CPU를 하루종일 돌려도 일주일 이상 기다리기를 각오해야 한다. 그것도 검사 대상 하나당. 더구나 [math]\displaystyle{ k\cdot10^6 \lt p \lt (k+1)10^6 }[/math] 구간마다 검사 대상이 대략 2만 개씩이나 되며, 분산 컴퓨팅으로 시스템을 마련한 것도 이 때문이다.
실제로는 이 검사를 두 번 거친다. 한 사용자가 A 컴퓨터에서 특정 메르센 수를 검사하고 결과를 제출한 후, 나중에 다른 사용자가 B 컴퓨터에서 같은 수를 똑같이 테스트한다. 그렇게 서로 다른 컴퓨터에서 뤼카-레머 소수판정법의 계산 결과가 똑같이 나오면, 그 결과는 올바르게 계산되었다(verified)고 판정하고 검사를 마친다. 초검과 재검이 완료된 경우: 해당 링크의 표에서 LL 항목의 'Residue' 항목이 바로 검사 결과의 마지막 64비트를 표시한 것이며, 이것이 일치해야 베리파이가 된다.
만약 초검과 재검이 불일치하면, 또다른 사용자가 C 컴퓨터에서 삼검을 시행하고 결과를 대조한다. 그렇게 해서 일치하는 두 결과가 있으면 이것이 검증된 결과이고, 나머지 하나는 오류(bad)로 판정한다. 어떤 경우 사검까지 가서야 검사가 완료된 적도 있다.
따라서 컴퓨터가 하드웨어 오류를 일으키지 않아야 삼검 없이 재검으로 검사를 완료할 수 있다. 물론 소수 판정을 내리는데 연산량이 굉장히 많은 만큼 언제든지 돌발 변수가 발생할 수 있기에, Prime95에서는 오류 발생을 최대한 피하고자 중간 결과(체크포인트)를 백업하고 야코비 오류 검사(Jacobi error checking)를 종종 시행한다. 이 오류 검사는 뤼카-레머 소수판정법 문서에 소개되어 있다.
대체된 소수판정법[편집 | 원본 편집]
2018년부터는 페르마 유력 소수 여부를 검사하는 방법을 도입하였다. 간단히 말해서 어떤 메르센 수[math]\displaystyle{ M_p }[/math]에 대해 페르마의 소정리의 합동식, 즉 [math]\displaystyle{ 3^{M_p-1} \equiv 1 \pmod{M_p} }[/math]를 만족하는지를 검사하는 것이다. [math]\displaystyle{ M_p+1=2^p }[/math]이므로, 합동식을 변형하면 [math]\displaystyle{ 3^{2^p} \equiv 9 \pmod{M_p} }[/math]이다.
위 식이 성립한다고 해서 해당 메르센 수가 소수라는 보장은 없다. 정확히는 위 합동식은 필요조건일 뿐 충분조건은 아니다. 그런데도 이걸 도입하는 이유는 더 강력한 오류 검사 방법인 게르비츠 오류 검사가 있기 때문이다. (해당 방법은 2017년 8월에 로베르트 게르비츠(Robert Gerbicz)가 고안하였다) 뤼카-레머 소수판정법의 야코비 오류 검사보다 하드웨어 오류를 더 확실하게 잡아낼 수 있고, 그에 따라 검사 횟수를 2회로 굳힐 수 있다.
그러다가 2020년 9월, Prime95 버전 30.3부터는 페르마 유력 소수 검사법에 증명파일(PRP proof file)을 첨부하는 방식으로 바뀌었다. 이 증명파일은 해당 컴퓨터가 "오류 없이 정확하게 계산했다"는 사실을 인증하는 데이터 파일이다. 먼저 A 컴퓨터의 초검 결과를 GIMPS에 제출한 후, 이 컴퓨터가 하드디스크에 저장해둔 증명파일은 B 컴퓨터로 전송한다. 그러면 이 파일을 받은 타 사용자는 검산을 실시하는데, 이때 초검을 그대로 반복하는 것보다 계산량이 1% 수준으로 감소한다. 사실상 검사 횟수를 기존 2회에서 1회로 단축하는 셈이며, 이로써 프로젝트를 좀 더 수월하게 진행할 수 있게 되었다. 따라서 현재는 이 검사법을 선호 및 채택하고 있다.
증명파일을 포함한 검사 예: 여기서는 'Residue'가 적혀 있는 항목이 LL 대신 PRP라고 적혀 있다. 해당 사용자가 초검을 실시하고, 아래 'History' 내역 중 "CERT | PRP Certification"이라 적여 있는 것이 증명파일을 사용한 검산 기록이다. 이 검산을 완료하고 나면 PRP 항목에는 재검 없이 초검으로만 베리파이가 되었다고 적힌 걸 확인할 수 있다.
기타[편집 | 원본 편집]
대체된 소수판정법을 시작한 후, 뤼카-레머 소수판정법은 2021년 4월 부로 더 이상 초검에 쓰지 않는다. Work Distribution Map 페이지에서 "Status LL/PRP"라고 적힌 열은 뤼카-레머 방식으로 (2020년 이전까지) 초검만 하고 재검은 완료하지 않은 메르센 수를 의미한다. 현재는 뤼카-레머 테스트를 대략 [math]\displaystyle{ M_p (6\times10^7 \lt p \lt 10^8) }[/math] 범위에서 재검하는 데에만 쓰고 있으며, 해당 열의 남은 개수가 모두 사라지면 이 검사는 끝날 예정이다.
소수 찾기가 GIMPS의 메인 프로젝트이지만 실제로는 다른 자잘한 미션도 있다.
- ECM: 주로 작은 메르센 수에 대해 소인수를 찾는다.
- p-1 소인수분해: 앞서 소개한 소인수분해는 소수 후보를 걸러낼 목적으로 시행하지만 ECM과 마찬가지로 작은 메르센 수를 대상으로도 쓴다.
- 여인수 PRP: 이는 어떤 메르센 수에서 발견된 소인수로 나눈 값이 소수인지를 알아보는 것이다. 위의 증명파일을 포함한 유력 소수 검사와 같은 방법을 쓴다.
같이 보기[편집 | 원본 편집]
- Prime95
- 메르센 소수
- Mersenne Forum: GIMPS 참여자 및 Prime95 개발진 등이 모여서 논의하는 곳이다.
- mersenne.ca: 메르센 수 관련 데이터 베이스를 모은 곳으로, GIMPS에서 계산 결과를 받으면 이곳에서도 정보를 갱신한다. 상단 오른쪽의 ≡ 표시를 누르면 여러 가지 메뉴가 나온다.
- Prime Grid: 메르센 소수 외 여러 형태의 소수에 대해 찾아볼 수 있다.