알려진 가장 큰 소수

이 문서는 역대 알려진 가장 큰 소수와 시기별 기록에 대해 다룬다.

소수의 개수는 무한하기에 자연수 집합에서 "가장 큰 소수"라는 개념은 존재하지 않는다. 다만 알려진 가장 큰 소수, 즉 인간이 발견한 영역 내에서 가장 큰 소수를 논하는 것은 의미가 있다.

2022년 9월 28일 기준 알려진 가장 큰 소수는 [math]\displaystyle{ 2^{82589933}-1 }[/math]로, 메르센 소수이다.

상세

현재로서는 소수를 생성하는 공식이 존재하지 않는다. 가령 제곱수의 경우 개수가 무한하다는 사실을 알고 있고, [math]\displaystyle{ f(n)=n^2 }[/math]에 아무 자연수나 대입하면 제곱수를 무한정 얻어낼 수 있기에 수학에서는 "알려진 가장 큰 제곱수"와 같은 주제는 전혀 관심의 대상이 아니다. 반면 소수의 경우 모든 자연수에 대해 [math]\displaystyle{ p(n) }[/math]이 소수가 되는 어떤 '닫힌 형태의 식'이 알려져 있지 않다.

다만 특정 자연수가 소수 후보인지 여부를 가리는 소수판정법이 있고, 백만~천만 자리의 자연수는 일반 컴퓨터로 비교적 간단한 소수판정법을 실행할 때 하루 내로 기다리면 결과를 얻어낼 수 있다. 물론 자릿수가 늘어날수록 소수 또는 소수 후보로 올라설 확률은 희박해지고, 소요시간도 급격히 늘어난다. 이는 달리 말하면 큰 소수 찾기 프로젝트는 소위 '보물 찾기 게임'이 되는 셈이다. 괜히 GIMPS와 같은 소수 찾기 프로젝트에서 수천 달러 이상의 상금을 거는 것이 아니다.

이렇게 큰 수 영역에서는 소수를 전수조사하지 않는다. 즉 어떤 거대한 소수가 발견되었다 해도 그것이 몇 번째 소수인지, 그 수와 이웃한 다른 소수가 얼마인지는 관심거리가 아니다. 물론 쌍둥이 소수나 세쌍둥이 소수를 찾을 때에는 이웃한 소수에 대해서도 테스트를 진행하기도 한다.

소수판정법은 크게 소수이기 위한 필요조건을 조사하는 방법, 특수한 자연수의 소수 여부를 빠르고 확실하게 가려내는 방법, 일반적인 자연수의 소수 여부를 입증하는 방법이 있다.

• 첫째 방법은 페르마의 소정리, 즉 합동식 [math]\displaystyle{ a^{N-1} \equiv 1 \pmod N }[/math]의 성립 여부를 가리는 방법이 있다. [math]\displaystyle{ N }[/math]이 소수이면 해당 합동식은 만족하지만, 그 역은 성립하지 않는다. 때문에 이 판정 기준은 필요조건이라서 이것만으로는 소수임을 확정할 수 없다. 다만 식이 거짓이면 합성수임은 확실하고, 이 판정법은 시간을 크게 잡아먹지 않기에 소수 후보를 소거하는 용도로는 유용하게 쓰인다.
• 둘째 방법은 뤼카-레머 소수판정법과 같이 특수한 자연수(메르센 수)를 대상으로 소수 여부를 가리는 방법이다. (메르센 수+1)이 2의 거듭제곱이라는 특수성을 적극 활용하여, 판정 조건을 적절히 다듬으면 위 첫째 방법과 비슷한 시간을 요구하면서 필요조건을 필요충분조건으로 굳힐 수 있다. 그 밖에 [math]\displaystyle{ k \cdot 2^n \pm 1 (\text{ odd }k\lt 2^n) }[/math] 형태의 자연수는 프로트의 정리 및 뤼카-레머-리젤 소수판정법으로 소수 여부를 확정할 수 있다.
• 셋째 방법은 모든 자연수에 적용되는 결정론적 알고리즘으로, 대표적으로 타원곡선 소수판정법이 있다. 범용성이 매우 좋지만 이쪽은 같은 크기의 자연수라도 위 두 방법보다는 시간이 훨씬 오래 걸린다. 현존하는 컴퓨터의 역량으로는 1만 자리 규모의 자연수까지 테스트할 수 있고, 2022년 9월까지 이 방법으로 밝혀낸 가장 큰 소수는 6만 자리를 넘지 않는다.

백만 자리 이상의 큰 영역에서 소수를 찾는다면 둘째 방법을 주로 이용한다. 실제로 이 영역에서 알려진 소수들은 바로 위에 서술한 바와 같이 2의 거듭제곱을 끼는 모양이 많다.

기록 경신 역사

중세 이전에는 자연수의 소수 여부를 가리는 방법으로 직접 나누기와 에라토스테네스의 체밖에 없었다. 즉 어떤 자연수의 제곱근 이하의 모든 소수들로 나눗셈을 시험하는 것이 유일한 길이었다. 1588년까지 알려진 가장 큰 소수는 피에트로 카탈디가 밝혀낸 수인 524287이다. 이는 메르센 소수의 일종으로 [math]\displaystyle{ M_{19}=2^{19}-1 }[/math]과 같다.

하지만 원초적인 직접 나누기 방법은 순전히 노가다이다. 수가 커질수록 나눗셈을 시행할 소수 개수도 많아지므로, 백만 이상으로 넘어가면 사람 손으로 풀기 힘들어진다.

그러다가 레온하르트 오일러는 페르마의 소정리로 특수한 자연수에 대해 직접 나누기 알고리즘의 효율을 크게 향상시켰다. 가령 페르마 수 [math]\displaystyle{ F_5=2^{32}+1 }[/math]의 모든 약수는 반드시 [math]\displaystyle{ 64k+1 }[/math]의 형태를 띠고, 메르센 수 [math]\displaystyle{ M_{31}=2^{31}-1 }[/math]의 모든 약수는 [math]\displaystyle{ 62k+1 }[/math] 꼴을 한다. (이유는 각 문서의 성질 문단 참고) 이 사실을 알고 있으면 약수 후보를 상당수 미리 걸러내어 나눗셈 횟수를 크게 단축할 수 있다. 오일러는 전자는 [math]\displaystyle{ F_5=641 \cdot 6700417 }[/math]임을 1732년에 밝혀냈다. 그리고 큰 약수인 6700417이 소수라는 사실도 어렵지 않게 입증할 수 있다. 후자의 경우, [math]\displaystyle{ M_{31} }[/math]이 소수임을 1772년에 증명함으로써 최고기록은 10자리를 넘어섰다.

이렇게 나누기 횟수를 단축한 직접 나누기 방법은 [math]\displaystyle{ a^b+1 }[/math] 꼴의 자연수에다 적용할 수 있다. 하지만 그렇다 해도 15자리 이상으로 넘어가면 이 방법도 속수무책이 된다.

그러다가 1876년 에두아르 뤼카는 직접 나누기 대신 뤼카 수열을 이용한 새로운 소수판정법을 제시했다. [math]\displaystyle{ p }[/math]가 4로 나눈 나머지가 3인 소수일 때, 뤼카 수 [math]\displaystyle{ L_{2^p} }[/math]이 [math]\displaystyle{ M_p=2^p-1 }[/math]로 나누어 떨어지면 [math]\displaystyle{ M_p }[/math]는 소수라는 것이다. 이 정리를 이용해 39자리 수인 [math]\displaystyle{ M_{127} }[/math]이 소수임을 증명하였고, 역대 가장 큰 소수로 갈아치워졌다.

이후, 페리에(Aimé Ferrier)는 1951년 44자리 수인 [math]\displaystyle{ \frac{2^{148}+1}{17} }[/math]이 소수임을 밝혀냈다. 포클링턴-레머 소수판정법을 활용하여 기계식 계산기로 밝혀낸 이 소수는 컴퓨터의 도움 없이 찾은 마지막 최고기록이다.

같은 해 제프리 밀러(Jeffrey Charles Percy Miller)와 데이비드 휠러(David John Wheeler)는 컴퓨터로 79자리 수인 [math]\displaystyle{ 180\cdot(M_{127})^2+1 }[/math]이 소수임을 밝혀냈다.

1952년부터는 메르센 소수가 최고기록 행진을 이어나갔다. 뤼카-레머 소수판정법으로 큰 메르센 수를 빠른 시간 내에 찾아낼 수 있기 때문. 물론 1989년에 발견된 [math]\displaystyle{ 391581\cdot 2^{216193}-1 }[/math]은 메르센 소수가 아닌 최고기록이나, 이후에는 메르센 소수들이 가장 큰 소수 자리를 계속 지켜나갔다.

1996년 이후 메르센 소수는 GIMPS에서 프로젝트를 담당하고 있다. [math]\displaystyle{ M_{1398269} }[/math]부터 [math]\displaystyle{ M_{82589933} }[/math]까지 소수를 총 17개 찾아냈으며, 현재 가장 큰 소수는 24862048 자리이고 2018년 12월 7일에 발견되었다.

같이 보기

• 메르센 소수
• GIMPS