이것은 문서의 이전 버전입니다!


소수 기록

좀 더 정확히 말하면, "알려진 가장 큰 소수의 기록". 소수가 무한히 많다는 건 물론 유클리드 때부터 증명되었지만, 아주 큰 숫자가 소수임을 증명하는 건 쉽지 않기 때문에 알려진 것보다 더 큰 소수를 찾으려는 노력은 수백년간 이어져 왔다. 2011년 12월 현재 알려진 가장 큰 소수는 243112609-1 = 3 1647 0269 ... 1666 9715 2511으로 GIMPS에 의해 발견되었다.

역사

처음으로 알려진 큰 소수는 그 기준을 어떻게 잡느냐에 따라 크게 갈리지만, 정확한 증명을 내놓은 시점으로 따지면 오일러가 1772년에 231-1 = 2147483647이 소수임을 증명한 것이 처음이다(이 숫자는 1588년에도 Pietro Cataldi가 큰 소수의 목록에 포함시킨 적이 있었지만, Cataldi는 완벽한 증명을 내 놓진 못 했으며 다른 숫자들에 대해서는 틀리기도 했다). 여기서 볼 수 있듯 예나 지금이나 소수 기록에서 가장 자주 등장하는 숫자는 Mn = 2n-1 형태의 메르센수로, 한 때는 n이 소수이기만 하면1) Mn이 항상 소수일 거라는 추측도 있었으나 틀린 것으로 밝혀졌다. 페르마는 16세기에 3보다 큰 메르센수 Mn이 가질 수 있는 소인수는 2kn+1 꼴임을 증명했는데, 오일러는 이 결과를 사용하여 비교적 적은 수의 나눗셈(이 경우 많아 봐야 747회)만으로 소수성을 증명해 낼 수 있었다.

이후 컴퓨터가 등장할 때까지 이 기록은 매우 서서히 개선되었으며, 1876년 에두아르 뤼카(Édouard Lucas)가 뤼카 판정을 고안해 내 39자리 숫자 2127-1가 소수임을 증명함으로써 정점을 찍었다(아마도 이 기록은 손으로 계산한 기록으로서는 현재도 유효할 것이다). 최초의 컴퓨터가 등장한 1951~1952년 사이 이 기록은 687자리까지 치솟았으며, 이후 발견된 모든 소수는 컴퓨터를 사용한 것이다. 또한 뤼카 검사의 개량판인 뤼카레머판정은 현대의 이진 컴퓨터에서 메르센 소수를 다른 소수에 비해 매우 빠르게2) 찾아 낼 수 있어 메르센 소수는 지속적으로 큰 소수를 찾는 작업의 대상이 되었다. 이 추세는 특히 1997년 메르센 소수를 찾기 위한 그리드컴퓨팅 프로젝트인 GIMPS의 등장으로 가속화되었다.

기록

다음은 2011년 12월 현재 알려진 가장 큰 소수 20개이다. 실시간 기록은 The Prime Pages를 참고.

# 소수 자리수 발견일 종류 발견자
1 243112609-1 12978189 2008-08 메르센소수 (#47+) GIMPS
2 242643801-1 12837064 2009-04 메르센 소수 (#46+) GIMPS
3 237156667-1 11185272 2008-09 메르센 소수 (#45+) GIMPS
4 232582657-1 9808358 2006-09 메르센 소수 (#44+) GIMPS
5 230402457-1 9152052 2005-12 메르센 소수 (#43+) GIMPS
6 225964951-1 7816230 2005-02 메르센 소수 (#42+) GIMPS
7 224036583-1 7235733 2004-05 메르센 소수 (#41+) GIMPS
8 220996011-1 6320430 2003-11 메르센 소수 (#40) GIMPS
9 213466917-1 4053946 2001-12 메르센 소수 (#39) GIMPS
10 19249×213018586+1 3918990 2007-05 프로스소수 Seventeen or Bust
11 27653×29167433+1 2759677 2005-06 프로스 소수 Seventeen or Bust
12 90527×29162167+1 2758093 2010-06 프로스 소수 Prime Sierpinski Project
13 75898524288+1 2558647 2011-11 일반화된 페르마소수 PrimeGrid
14 28433×27830457+1 2357207 2004-12 프로스 소수 Seventeen or Bust
15 3×27033641+1 2117338 2011-02 페르마 소수의 인수 PrimeGrid
16 33661×27031232+1 2116617 2007-10 프로스 소수 Seventeen or Bust
17 26972593-1 2098960 1999-06 메르센 소수 (#38) GIMPS
18 6679881×26679881+1 2010852 2009-08 쿨렌 소수 PrimeGrid
19 1582137×26328550+1 1905090 2009-04 쿨렌 소수 PrimeGrid
20 3×26090515-1 1833429 2010-04 3×2n-1 PrimeGrid (321 Search)

바깥 링크

1) 2pq-1은 2p-1과 2q-1로 나눌 수 있기 때문에 n이 합성수일 경우(즉, p와 q 모두 1보다 크면) 2n-1은 항상 합성수이다.
2) 적절한 곱셈알고리즘을 사용할 경우 O(n^2 \log n \log\log n) 시간까지 줄일 수 있다. 이는 일반적인 숫자의 소수 판정에 사용되는 알고리즘(확률적인 방법은 레머라빈판정, 소수 증명AKS)보다 상수배 내지는 수제곱배 빠른 것이다.

도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-12-26 05:51 | 작성자 lifthrasiir