====== 소수 기록 ======

좀 더 정확히 말하면, "알려진 가장 큰 [[소수]]의 기록". [[소수의무한성|소수가 무한히 많다]]는 건 물론 [[유클리드]] 때부터 증명되었지만, 아주 큰 숫자가 소수임을 증명하는 건 쉽지 않기 때문에 알려진 것보다 더 큰 소수를 찾으려는 노력은 수백년간 이어져 왔다. [[2011년 12월 현재]] 알려진 가장 큰 소수는 2<sup>43112609</sup>-1 = [[http://prime.isthe.com/chongo/tech/math/prime/m43112609/prime-c.html|3 1647 0269 ... 1666 9715 2511]]으로 [[GIMPS]]에 의해 발견되었다.

===== 역사 =====

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

이후 [[컴퓨터]]가 등장할 때까지 이 기록은 매우 서서히 개선되었으며, 1876년 에두아르 뤼카(Édouard Lucas)가 뤼카 판정을 고안해 내 39자리 숫자 2<sup>127</sup>-1가 소수임을 증명함으로써 정점을 찍었다(아마도 이 기록은 손으로 계산한 기록으로서는 현재도 유효할 것이다). 최초의 컴퓨터가 등장한 1951~1952년 사이 이 기록은 687자리까지 치솟았으며, 이후 발견된 모든 소수는 컴퓨터를 사용한 것이다. 또한 뤼카 검사의 개량판인 [[뤼카레머판정]]은 현대의 이진 컴퓨터에서 메르센 소수를 다른 소수에 비해 매우 빠르게((적절한 [[곱셈알고리즘]]을 사용할 경우 $$O(n^2 \log n \log\log n)$$ 시간까지 줄일 수 있다. 이는 일반적인 숫자의 소수 판정에 사용되는 알고리즘(확률적인 방법은 [[레머라빈판정]], [[소수증명]]은 [[AKS]])보다 상수배 내지는 수제곱배 빠른 것이다.)) 찾아 낼 수 있어 메르센 소수는 지속적으로 큰 소수를 찾는 작업의 대상이 되었다. 이 추세는 특히 [[1997년]] 메르센 소수를 찾기 위한 [[그리드컴퓨팅]] 프로젝트인 [[GIMPS]]의 등장으로 가속화되었다.

===== 기록 =====

다음은 [[2011년 12월 현재]] 알려진 가장 큰 소수 20개이다. 실시간 기록은 [[http://primes.utm.edu/primes/search.php?Number=100|The Prime Pages]]를 참고.

^  #  ^  소수  ^  자리수  ^  발견일  ^  종류  ^  발견자  ^
|  1 | 2<sup>43112609</sup>-1 |  12978189 | 2008-08 | [[메르센소수]] (#47+) | [[GIMPS]] |
|  2 | 2<sup>42643801</sup>-1 |  12837064 | 2009-04 | 메르센 소수 (#46+) | GIMPS |
|  3 | 2<sup>37156667</sup>-1 |  11185272 | 2008-09 | 메르센 소수 (#45+) | GIMPS |
|  4 | 2<sup>32582657</sup>-1 |  9808358 | 2006-09 | 메르센 소수 (#44+) | GIMPS |
|  5 | 2<sup>30402457</sup>-1 |  9152052 | 2005-12 | 메르센 소수 (#43+) | GIMPS |
|  6 | 2<sup>25964951</sup>-1 |  7816230 | 2005-02 | 메르센 소수 (#42+) | GIMPS |
|  7 | 2<sup>24036583</sup>-1 |  7235733 | 2004-05 | 메르센 소수 (#41+) | GIMPS |
|  8 | 2<sup>20996011</sup>-1 |  6320430 | 2003-11 | 메르센 소수 (#40) | GIMPS |
|  9 | 2<sup>13466917</sup>-1 |  4053946 | 2001-12 | 메르센 소수 (#39) | GIMPS |
| 10 | 19249×2<sup>13018586</sup>+1 |  3918990 | 2007-05 | [[프로스소수]] | [[Seventeen or Bust]] |
| 11 | 27653×2<sup>9167433</sup>+1 |  2759677 | 2005-06 | 프로스 소수 | Seventeen or Bust |
| 12 | 90527×2<sup>9162167</sup>+1 |  2758093 | 2010-06 | 프로스 소수 | Prime Sierpinski Project |
| 13 | 75898<sup>524288</sup>+1 |  2558647 | 2011-11 | 일반화된 [[페르마소수]] | PrimeGrid |
| 14 | 28433×2<sup>7830457</sup>+1 |  2357207 | 2004-12 | 프로스 소수 | Seventeen or Bust |
| 15 | 3×2<sup>7033641</sup>+1 |  2117338 | 2011-02 | 페르마 수의 인수 | PrimeGrid |
| 16 | 33661×2<sup>7031232</sup>+1 |  2116617 | 2007-10 | 프로스 소수 | Seventeen or Bust |
| 17 | 2<sup>6972593</sup>-1 |  2098960 | 1999-06 | 메르센 소수 (#38) | GIMPS |
| 18 | 6679881×2<sup>6679881</sup>+1 |  2010852 | 2009-08 | [[쿨렌수|쿨렌 소수]] | PrimeGrid |
| 19 | 1582137×2<sup>6328550</sup>+1 |  1905090 | 2009-04 | 쿨렌 소수 | PrimeGrid |
| 20 | 3×2<sup>6090515</sup>-1 |  1833429 | 2010-04 | 3×2<sup>n</sup>-1 | PrimeGrid (321 Search) |

===== 바깥 링크 =====

  * [[The Prime Pages]]
    * [[http://primes.utm.edu/largest.html#largest|알려진 가장 큰 소수 기록]]
    * [[http://primes.utm.edu/notes/by_year.html|연도별 소수 기록 추세]]

{{tag>수학}}