뤼카–레머 메르센 소수 판정기

2^p − 1이 소수인지 가리는 방법입니다. s₀ = 4에서 시작해 s를 제곱하고 2를 뺀 뒤 2^p − 1로 나눈 나머지를 취하기를 p−2번 되풀이했을 때, 마지막 값이 0이면 소수이고 아니면 합성수입니다. 확률적 판정이 아니라 확정적 판정이라는 점이 중요합니다.

2^p − 1이라는 모양 덕분입니다. 이 수로 나눈 나머지를 구하는 것이 아주 싸서(2^p ≡ 1이므로 비트를 p칸 밀어 더하면 끝) 큰 수를 수천 번 제곱해도 감당이 됩니다. 그래서 지금까지 알려진 「가장 큰 소수」는 거의 언제나 메르센 소수였습니다.

아닙니다. 이것이 이 주제의 최다 오해입니다. M(11) = 2047 = 23 × 89가 대표적인 반례입니다. 반대 방향은 성립합니다 — p가 합성수면 2^p − 1은 반드시 합성수입니다. 2^ab − 1은 2^a − 1로 나누어떨어지기 때문입니다.

인터넷 메르센 소수 찾기(Great Internet Mersenne Prime Search)의 줄임말로, 1996년부터 자원자들의 컴퓨터를 모아 메르센 소수를 찾는 분산 계산 프로젝트입니다. 뤼카–레머 판정법이 그 계산의 핵심이고, 최근에 발견된 가장 큰 소수들은 모두 여기서 나왔습니다.

메르센 소수 하나가 짝수 완전수 하나와 1대1로 대응합니다. 유클리드–오일러 정리에 따라 모든 짝수 완전수는 2^(p−1)·(2^p − 1) 꼴이고 여기서 2^p − 1이 소수여야 합니다. p = 2, 3, 5, 7이면 각각 6, 28, 496, 8128입니다.

아직 하나도 발견되지 않았고 있는지 없는지도 증명되지 않았습니다. 수학에서 가장 오래된 미해결 문제 가운데 하나입니다. 짝수 쪽은 메르센 소수와의 대응으로 완전히 설명되지만 홀수 쪽은 아무것도 모릅니다.

전송되지 않습니다. 판정은 모두 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.