루카스–레머 소수판별법

루카스-레머 소수판별법은 메르센 수에 대한 소수판별법으로, 루카스와 레머에 의해 개발되었다.

판정 방법

메르센 수 M_p = 2^p − 1를 생각하자. 이 때, p는 홀수 소수로 한다(소수가 아닐 경우, 자명한 약수를 가진다. 그리고 이 판정법은 p = 2일 때에는 유효하지 않다.). 0 이상의 모든 i에 대한 수열{s_i}는 다음과 같이 정의된다.

$s_i= \begin{cases} 4 & \text{if }i=0; \\ s_{i-1}^2-2 & \text{otherwise.} \end{cases}$

첫 몇개의 항은 4, 14, 194, 37634, ... 이다. (OEIS의 수열 A003010) 이 때, 다음과 같은 관계식을 만족하는 것과 M_p가 소수라는 것은 동치이다.

$s_{p-2}\equiv0\pmod{M_p}$

이 때, s_p-2 mod M_p를 루카스-레머 나머지라고 한다.