차이점
이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.
|
소수기록 [2010-12-05 20:48] lifthrasiir 새로 만듦 |
소수기록 [2011-12-26 05:52] (현재) lifthrasiir 페르마 "소수"에 인수가 있던가?; 오타 수정. |
||
|---|---|---|---|
| 줄 1: | 줄 1: | ||
| ====== 소수 기록 ====== | ====== 소수 기록 ====== | ||
| - | 좀 더 정확히 말하면, "알려진 가장 큰 [[소수]]의 기록". [[소수의무한성|소수가 무한히 많다]]는 건 물론 [[유클리드]] 때부터 증명되었지만, 아주 큰 숫자가 소수임을 증명하는 건 쉽지 않기 때문에 알려진 것보다 더 큰 소수를 찾으려는 노력은 수백년간 이어져 왔다. 2010년 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]]에 의해 발견되었다. | + | 좀 더 정확히 말하면, "알려진 가장 큰 [[소수]]의 기록". [[소수의무한성|소수가 무한히 많다]]는 건 물론 [[유클리드]] 때부터 증명되었지만, 아주 큰 숫자가 소수임을 증명하는 건 쉽지 않기 때문에 알려진 것보다 더 큰 소수를 찾으려는 노력은 수백년간 이어져 왔다. [[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회)만으로 소수성을 증명해 낼 수 있었다. | + | 처음으로 알려진 큰 소수는 그 기준을 어떻게 잡느냐에 따라 크게 갈리지만, 정확한 증명을 내놓은 시점으로 따지면 [[오일러]]가 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]]의 등장으로 가속화되었다. | 이후 [[컴퓨터]]가 등장할 때까지 이 기록은 매우 서서히 개선되었으며, 1876년 에두아르 뤼카(Édouard Lucas)가 뤼카 판정을 고안해 내 39자리 숫자 2<sup>127</sup>-1가 소수임을 증명함으로써 정점을 찍었다(아마도 이 기록은 손으로 계산한 기록으로서는 현재도 유효할 것이다). 최초의 컴퓨터가 등장한 1951~1952년 사이 이 기록은 687자리까지 치솟았으며, 이후 발견된 모든 소수는 컴퓨터를 사용한 것이다. 또한 뤼카 검사의 개량판인 [[뤼카레머판정]]은 현대의 이진 컴퓨터에서 메르센 소수를 다른 소수에 비해 매우 빠르게((적절한 [[곱셈알고리즘]]을 사용할 경우 $$O(n^2 \log n \log\log n)$$ 시간까지 줄일 수 있다. 이는 일반적인 숫자의 소수 판정에 사용되는 알고리즘(확률적인 방법은 [[레머라빈판정]], [[소수증명]]은 [[AKS]])보다 상수배 내지는 수제곱배 빠른 것이다.)) 찾아 낼 수 있어 메르센 소수는 지속적으로 큰 소수를 찾는 작업의 대상이 되었다. 이 추세는 특히 [[1997년]] 메르센 소수를 찾기 위한 [[그리드컴퓨팅]] 프로젝트인 [[GIMPS]]의 등장으로 가속화되었다. | ||
| 줄 11: | 줄 11: | ||
| ===== 기록 ===== | ===== 기록 ===== | ||
| - | 다음은 2010년 12월 현재 알려진 가장 큰 소수 20개이다. 실시간 기록은 [[http://primes.utm.edu/primes/search.php?Number=100|The Prime Pages]]를 참고. | + | 다음은 [[2011년 12월 현재]] 알려진 가장 큰 소수 20개이다. 실시간 기록은 [[http://primes.utm.edu/primes/search.php?Number=100|The Prime Pages]]를 참고. |
| ^ # ^ 소수 ^ 자리수 ^ 발견일 ^ 종류 ^ 발견자 ^ | ^ # ^ 소수 ^ 자리수 ^ 발견일 ^ 종류 ^ 발견자 ^ | ||
| 줄 26: | 줄 26: | ||
| | 11 | 27653×2<sup>9167433</sup>+1 | 2759677 | 2005-06 | 프로스 소수 | 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 | | | 12 | 90527×2<sup>9162167</sup>+1 | 2758093 | 2010-06 | 프로스 소수 | Prime Sierpinski Project | | ||
| - | | 13 | 28433×2<sup>7830457</sup>+1 | 2357207 | 2004-12 | 프로스 소수 | Seventeen or Bust | | + | | 13 | 75898<sup>524288</sup>+1 | 2558647 | 2011-11 | 일반화된 [[페르마소수]] | PrimeGrid | |
| - | | 14 | 33661×2<sup>7031232</sup>+1 | 2116617 | 2007-10 | 프로스 소수 | Seventeen or Bust | | + | | 14 | 28433×2<sup>7830457</sup>+1 | 2357207 | 2004-12 | 프로스 소수 | Seventeen or Bust | |
| - | | 15 | 2<sup>6972593</sup>-1 | 2098960 | 1999-06 | 메르센 소수 (#38) | GIMPS | | + | | 15 | 3×2<sup>7033641</sup>+1 | 2117338 | 2011-02 | 페르마 수의 인수 | PrimeGrid | |
| - | | 16 | 6679881×2<sup>6679881</sup>+1 | 2010852 | 2009-08 | [[쿨렌수|쿨렌 소수]] | PrimeGrid | | + | | 16 | 33661×2<sup>7031232</sup>+1 | 2116617 | 2007-10 | 프로스 소수 | Seventeen or Bust | |
| - | | 17 | 1582137×2<sup>6328550</sup>+1 | 1905090 | 2009-04 | 쿨렌 소수 | PrimeGrid | | + | | 17 | 2<sup>6972593</sup>-1 | 2098960 | 1999-06 | 메르센 소수 (#38) | GIMPS | |
| - | | 18 | 3×2<sup>6090515</sup>-1 | 1833429 | 2010-04 | 3×2<sup>n</sup>-1 | PrimeGrid (321 Search) | | + | | 18 | 6679881×2<sup>6679881</sup>+1 | 2010852 | 2009-08 | [[쿨렌수|쿨렌 소수]] | PrimeGrid | |
| - | | 19 | 258317×2<sup>5450519</sup>+1 | 1640776 | 2008-06 | | PrimeGrid\\ Prime Sierpinski Project | | + | | 19 | 1582137×2<sup>6328550</sup>+1 | 1905090 | 2009-04 | 쿨렌 소수 | PrimeGrid | |
| - | | 20 | 3×2<sup>5082306</sup>+1 | 1529928 | 2009-04 | | PrimeGrid | | + | | 20 | 3×2<sup>6090515</sup>-1 | 1833429 | 2010-04 | 3×2<sup>n</sup>-1 | PrimeGrid (321 Search) | |
| ===== 바깥 링크 ===== | ===== 바깥 링크 ===== | ||
저작권자 © 1999–2012 강 성훈. 저작권을 약간 가집니다. | 풉;이 뭐냐고요?