976378538515947는 소수일까? 펜과 종이만으로 그 답을 찾기는 어렵다. 소수는 오직 1과 자기 자신으로만 나눠지는 수로, 큰 수가 소수인지 알아보기 위해선 2, 3, 5, … 등 더 큰 소수로 계속해서 나눠봐야 하기 때문이다. 따라서 수가 커질수록 소수 찾기가 매우 어려워 수학자들은 소수에 일정한 규칙이 있는지 알아내고자 했다.

최근 ‘메르센 소수’를 찾아내기 위해 협력하는 국제적인 프로그램인 GIMPS(Great Internet Mersenne Prime Search) 프로젝트가 6년 만에 가장 큰 소수를 찾아냈다. 이번에 발견된 소수는 2의 1억 3627만 9841제곱에서 1을 뺀 수로, 전체 자릿수만 4102만 4320에 달한다.

메르센 수는 2의 n제곱에서 1을 뺀 형태(2ⁿ-1)다. 그 중 소수인 것을 메르센 소수라고 한다. 모든 메르센 수가 소수는 아니지만, 지수(n)가 소수일 때 그 메르센 수가 소수일 가능성이 높다.

메르센 소수 탐색에는 루카스-레머 테스트라는 검증 방법이 사용된다. 이 방법은 규칙성을 기반으로 하여 빠르고 정확한 소수 검증을 가능하게 한다. 특히 큰 수를 신속하게 검증할 수 있다는 장점 덕분에 가장 큰 소수를 찾기 쉽다.

GIMPS에서 사용하는 소프트웨어도 루카스-레머 알고리즘을 사용한다. GIMPS 소프트웨어는 1996년 이후 52개의 메르센 소수를 찾아내면서 메르센 소수 탐색의 중심 역할을 하고 있다.

오늘날 큰 소수 찾기엔 수학자뿐만 아니라 일반인들도 함께한다. 전 세계 자원봉사자들은 GIMPS 소프트웨어를 자신의 컴퓨터에 설치한 다음 유휴 계산 자원을 활용해 소수 탐색에 기여했다. 이번에 가장 큰 메르센 소수를 발견한 사람도 전 엔비디아 직원 루크 듀런트다. 그는 2023년부터 수천 개의 GPU 서버를 통해 GIMPS의 소수 탐색에 기여했으며, 그 결과로 2024년 10월 11일, 가장 큰 소수를 확인했다.

GIMPS는 참여 독려차 상금도 걸어놨다. GIMPS 공동 창립자인 조지 볼트만은 1997년 뉴욕타임즈에서 이 프로그램을 “수학 애호가들의 오락거리”라고 설명하며, “많은 이들이 이 프로그램에 매료되고 있다”고 밝혔다. 자, 집에 컴퓨터가 있다면 GIMPS에 참여해보자. 세상에서 가장 큰 소수를 찾을 다음 주인공은 당신일지도 모른다.

갈수록 더 빨리 발견되는 메르센 소수

▲Shutterstock

나선형으로 뻗어나가는 수 사이에 소수를 흰 점으로 표현해 소수의 불규칙성을 나타낸 그림이다.

▲Blaise Pascal(W)

메르센 소수를 발견한 마랭 메르센.

용어 설명

유휴 계산 자원 : 사용되지 않는 컴퓨터의 처리 능력이나 메모리 등 활용 가능한 자원.

d라이브러리