메르센 소수 (Mersenne Prime)

메르센 소수(Mersenne prime)는 M_n = 2ⁿ − 1 꼴, 즉 2의 거듭제곱보다 1 작은 소수입니다. 17세기에 이 수들을 연구하고 1644년 목록을 발표한 프랑스 최소형제회 수도사 마랭 메르센의 이름을 땄습니다. 3, 7, 31, 127이 처음 몇 개의 메르센 소수입니다.

자세히 알아보기

2ⁿ − 1이 소수이려면 n이 반드시 소수여야 합니다. n = ab로 쪼개지면 2^a − 1이 2ⁿ − 1을 나누기 때문입니다. 그러나 역은 성립하지 않습니다. n = 11은 소수이지만 2¹¹ − 1 = 2047 = 23 × 89는 합성수입니다.

메르센 수는 뤼카-레머 판정법이라는 매우 효율적인 소수 판정법이 있어서, 알려진 가장 큰 소수들은 대부분 메르센 소수입니다. 분산 컴퓨팅 프로젝트 GIMPS가 수십 년째 탐색 중이며, 2024년 10월에는 GPU를 활용한 루크 듀랜트가 2¹³⁶,279,841 − 1(41,024,320자리)을 발견해 알려진 52번째 메르센 소수가 되었습니다. 메르센 소수는 완전수와도 연결되어, 2ⁿ⁻¹(2ⁿ − 1)은 2ⁿ − 1이 소수일 때 짝수 완전수가 됩니다.

블록체인·암호화폐에서는

흔한 오해와 달리 RSA 같은 공개 키 암호의 키를 메르센 소수로 만들지는 않습니다. RSA 소수는 무작위로 골라야 하며, 특별한 형태의 소수는 오히려 위험할 수 있습니다. 실제로 쓰이는 곳은 다음과 같습니다.

• 빠른 나머지 연산: 2ⁿ − 1이나 그와 비슷한 '유사 메르센 소수'를 법으로 쓰면 나머지 연산을 시프트와 덧셈으로 처리할 수 있습니다. Curve25519·Ed25519의 2²⁵⁵ − 19, Poly1305의 2¹³⁰ − 5, 비트코인 secp256k1의 2²⁵⁶ − 2³² − 977이 이런 이유로 선택된 특수 형태 소수입니다(엄밀한 메르센 소수는 아님).
• 메르센 트위스터: 널리 쓰이는 의사난수 생성기 MT19937은 주기가 메르센 소수 2¹⁹⁹³⁷ − 1입니다. 그러나 출력 624개만 관찰하면 내부 상태를 복원할 수 있어 암호용으로 쓰면 안 됩니다. 2023년 공개된 'Milk Sad' 사건(CVE-2023-39910)에서는 Libbitcoin Explorer(bx) 3.x의 bx seed 명령이 시스템 시간으로 초기화한 메르센 트위스터(내부 엔트로피 32비트)로 지갑 시드를 만든 탓에 2023년 6~7월 자금이 탈취되었습니다.

쉽게 말하면

메르센 소수는 이진수로 쓰면 1만 줄줄이 이어진 소수입니다. 2⁵ − 1 = 31은 이진수로 11111입니다.

예시

n = 2, 3, 5, 7이면 3, 7, 31, 127로 모두 소수입니다. n = 11은 2047 = 23 × 89로 소수가 아닙니다.