메르센 소수 사냥
거대한 소수를 잡는 그물
2를 거듭제곱한 수에서 1을 빼 보세요. 3, 7, 15, 31, 63, 127이 차례로 나옵니다.
이 중 3, 7, 31, 127은 소수이지만 15와 63은 소수가 아닙니다. 꼴의 수가 언제 소수가 되는지 그 비밀을 풀 수 있을까요?
이야기
?
Public domain · 위키미디어 공용
꼴의 수를 살펴봅시다. , , — 소수가 자주 나옵니다.
프랑스 수도사 마랭 메르센이 17세기에 이 수들을 정리했습니다. 그래서 이런 꼴의 소수를 메르센 소수라 부릅니다.
먼저 알아 둘 것이 있습니다. n이 소수가 아니면 도 소수가 아닙니다. 예를 들어 입니다. 그러나 거꾸로는 참이 아닙니다. n이 소수여도 소수가 아닐 수 있습니다 — .
지금까지 발견된 가장 큰 소수는 언제나 메르센 소수였습니다. 이 꼴은 소수인지 빠르게 판정하는 방법이 있기 때문입니다.
지금 이 순간에도 전 세계 자원자들의 컴퓨터가 함께 새 메르센 소수를 찾고 있습니다. 누구나 참여할 수 있습니다.
마랭 메르센은 17세기 파리의 수도사였습니다. 학술지도 학회도 없던 시절, 그는 데카르트·페르마·파스칼·갈릴레오 사이에서 편지를 받아 옮기고 문제를 전해 주는 일을 했습니다. 누군가 새 결과를 얻으면 메르센에게 편지를 썼고, 그가 유럽 곳곳에 퍼뜨렸습니다. 사람이 인터넷 노릇을 한 것입니다.
세계에서 가장 큰 소수는 모두 메르센 소수입니다. 지금 최대는 4천만 자리가 넘습니다.
수만 대의 컴퓨터가 함께 찾는 GIMPS 프로젝트가 계속 돌고 있고, 그 과정에서 만들어진 빠른 곱셈 방법이 다른 계산에도 쓰입니다.
계단 넷 — 같은 사실을 네 깊이로
2ⁿ−1 을 계산해 소수인지 본다
2를 몇 번 곱하고 1을 빼 봅니다. , , , 은 모두 소수입니다.
지수에 들어간 2, 3, 5, 7이 모두 소수입니다. 지수가 소수일 때만 결과도 소수가 될 가능성이 생깁니다. 손으로 직접 계산하며 소수를 찾아보세요.
2 를 곱하고 1 을 빼 보세요
그런데 p = 11 → 2047 = 23×89 는 소수가 아닙니다.
n 이 소수여야 하는 것
지수 이 합성수 이면 로 인수분해되므로 반드시 합성수가 됩니다. 따라서 이 소수이려면 지수 은 반드시 소수라야 합니다.
그러나 지수가 소수라고 해서 항상 소수인 것은 아닙니다. 처럼 지수가 소수여도 합성수가 되는 예외가 나타납니다.
p 가 소수여야 합니다
그래서 p 가 소수인 것이 꼭 필요하지만 충분하지는 않습니다.
루카스–레머 판정
꼴의 소수를 메르센 소수라 합니다. 고대 유클리드와 오일러는 가 소수일 때 이 짝수 완전수이며, 모든 짝수 완전수가 이 꼴임을 증명했습니다.
메르센 수가 소수인지 판정할 때는 루카스-레머 판정법을 씁니다. 수열 를 계산하여 인지 확인하는 매우 빠른 알고리즘입니다.
루카스–레머 검사
그래서 메르센 소수만 유난히 큰 것이 발견됩니다.
완전수와의 짝
메르센 소수는 오늘날 인류가 알고 있는 가장 거대한 소수들의 기록을 독점하고 있습니다. 전 세계 수십만 대의 컴퓨터를 연결한 분산 컴퓨팅 프로젝트인 GIMPS(Great Internet Mersenne Prime Search)를 통해 탐색됩니다.
메르센 소수가 무한히 존재하는지는 아직 미해결 난제이며, 거대 소수 탐색 기술은 컴퓨터 하드웨어의 오류 검증 및 현대 암호학(RSA 등)의 난수 생성에 핵심적으로 기여합니다.
GIMPS 가 찾은 것
전 세계 자원봉사자들이 컴퓨터를 빌려 주어 찾았습니다 (GIMPS).
풀어 보기
메르센 수와 소인수분해. 이라 하자.
(1) 의 값을 각각 구하고, 소수인 것을 모두 고르시오.
(2) 을 로 인수분해하여 합성수임을 보이시오.
(3) 이 소수임을 이용하여, 짝수 완전수 의 값을 구하시오.
이 합성수이면 도 반드시 합성수입니다. 그래서 지수가 소수인 것만 살펴봅니다.
답과 풀이 보기
(1)
소수는 3, 7, 31 입니다. 는 합성수입니다.
(2) — 합성수입니다.
여기에 규칙이 있습니다. 이 합성수이면 도 반드시 합성수입니다 (, ). 그래서 지수가 소수인 것만 살펴봅니다. 다만 지수가 소수라고 늘 소수는 아닙니다 — 입니다.
(3)
28 의 진약수 — 두 번째 완전수입니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
큰 소수를 찾는 일은 놀이이자 시험대입니다.
- 완전수 — 메르센 소수 하나마다 짝수 완전수 하나가 대응합니다
- 컴퓨터 성능 시험 — 큰 소수 판정은 기계의 계산력을 재는 잣대로 쓰입니다
- 분산 계산 — 여러 사람의 컴퓨터를 모아 하나의 문제를 푸는 방식의 본보기입니다
이어지는 장
2의 거듭제곱에서 1을 뺀 메르센 소수를 하나 찾아낼 때마다 짝수 완전수가 정확히 하나씩 짝을 지어 태어난다는 유클리드와 오일러의 정리가 있습니다 — 제72장에서 메르센 소수 사냥이 완전수의 비밀을 푸는 열쇠가 되는 이유를 알아보세요.
영감을 받은 곳
프랑스의 수도사이자 수학자 마랭 메르센(Marin Mersenne)이 1644년 출간한 저서 『물리수학적 고찰』(Cogitata Physico-Mathematica) 서문에서 2의 거듭제곱에서 1을 뺀 소수 목록을 제시한 기록에서 유래했습니다.