뤼카-레머 소수판별법

1. 개요

뤼카-레머 소수 판별법은 에두아르 뤼카의 알고리즘을 데릭 레머가 개량한 것으로, 메르센 소수인지 판별하는 방법이다. 이 판별법은 메르센 수 M_p = 2^p − 1 (p는 홀수 소수)에 대해 수열 s_i = s_i-1² − 2 (s₀ = 4)를 정의하고, s_p-2 mod M_p가 0과 동치일 때 M_p가 소수임을 판별한다. 뤼카-레머 소수 판별법은 Prime95와 GIMPS에서 사용되며, 메르센 소수를 찾는 데 기여했다.

2. 역사

에두아르 뤼카의 원래 알고리즘을 데릭 레머가 개량하였다.

3. 판정 방법

메르센 수 M_p = 2^p − 1 (이때 p는 홀수 소수)가 소수인지 판별하는 방법이다. 만약 p가 합성수라면 M_p는 자명한 약수를 가지므로 소수가 아니며, p = 2일 때는 이 판정법이 적용되지 않는다.

뤼카-레머 소수판별법은 다음과 같은 수열 $\backslash \{s\_i\backslash \}$를 이용한다.
:$$
s_i=
\begin{cases}
4 & \text{if }i=0;
\\
s_{i-1}^2-2 & \text{if }i \ge 1.
\end{cases}

이 수열의 첫 항들은 4, 14, 194, 37634, ... 와 같다. (OEIS A003010)

이 수열을 이용하여 메르센 수 M_p의 소수 여부를 판정하는 조건은 다음과 같다.
:$s\_\{p-2\}\backslash equiv0\backslash pmod\{M\_p\}$
즉, 수열의 (p-1)번째 항인 s_p-2를 M_p로 나누었을 때 나머지가 0이면 M_p는 소수이고, 그렇지 않으면 합성수이다. 이때 계산되는 값 $s\_\{p-2\}\; \backslash pmod\{M\_p\}$를 뤼카-레머 나머지라고 부른다.

알고리즘은 다음과 같이 의사 코드로 표현할 수 있다.

// Mp = 2p − 1이 p > 2인 소수에 대해 소수인지 확인
Lucas–Lehmer(p)
    var s = 4
    var M = 2p − 1
    repeat p − 2 times:
        s = ((s × s) − 2) mod M
    if s == 0 return 소수
    else return 합성수

계산 과정에서 각 반복마다 mod M 연산을 수행하는 것이 중요하다. 이렇게 하면 중간 계산 결과값의 크기가 M을 넘지 않게 되어(최대 p 비트 크기), 매우 큰 수가 되는 것을 방지하고 효율적인 계산이 가능하다. 이는 모듈러 거듭제곱에서 사용하는 방식과 유사하다.

수열의 시작 값 $s\_0$는 일반적으로 4를 사용하지만, 다른 값을 사용할 수도 있다. 어떤 시작 값을 사용하든 M_p가 메르센 소수이면 뤼카-레머 나머지는 0이 된다.

3.1. 초기값

메르센 수 M_p = 2^p − 1를 판별할 때 (여기서 p는 홀수 소수), 뤼카-레머 소수판별법은 특정 수열 $s\_i$를 사용한다. 이 수열은 0 이상의 모든 정수 i에 대해 다음과 같이 정의된다.

$s\_0\; =\; 4$
$s\_i\; =\; s\_\{i-1\}^2\; -\; 2\; \backslash quad\; (i\; \backslash ge\; 1)$

이 수열의 첫 몇 항은 4, 14, 194, 37634, ... 와 같다. 판별법의 핵심은 $s\_\{p-2\}$를 M_p로 나눈 나머지가 0인지 확인하는 데 있다. 즉, $s\_\{p-2\}\; \backslash equiv\; 0\; \backslash pmod\{M\_p\}$ 이 성립하면 M_p는 소수이다. 여기서 $s\_\{p-2\}\; \backslash pmod\{M\_p\}$ 값을 뤼카-레머 나머지라고 부른다.

일반적으로 초기값 $s\_0$는 4를 사용하지만, 다른 값을 사용할 수도 있다. 예를 들어 10이나 52와 같은 다른 정수 값을 초기값으로 사용할 수 있다. 이러한 다른 초기값으로 계산된 뤼카-레머 나머지도 M_p가 메르센 소수일 경우에는 여전히 0이 된다. 그러나 수열의 각 항 값은 달라지며, M_p가 합성수일 때 계산되는 0이 아닌 뤼카-레머 나머지 값도 $s\_0\; =\; 4$일 때와는 다른 값을 갖게 된다.

정수 외에 분수 형태의 초기값도 사용될 수 있다. 예를 들어, (2 mod M_p)(3 mod M_p)⁻¹, 간단히 2/3로 표기되는 값을 사용할 수 있다. 이 값은 지수가 p인 웨그스태프 수 (2^p + 1) / 3과 같다.

4, 10, 2/3와 같은 초기값들은 보편적이라고 불리는데, 이는 거의 모든 소수 p에 대해 유효하기 때문이다. 이러한 보편적인 초기값은 무한히 많이 존재한다.

반면, 모든 p에 대해 유효하지 않고 특정 조건을 만족하는 p의 부분 집합에 대해서만 유효한 초기값도 있다. 예를 들어, 초기값 $s\_0\; =\; 3$은 p가 4로 나눈 나머지가 3인 경우 (즉, $p\; \backslash equiv\; 3\; \backslash pmod\; 4$)에만 사용할 수 있다. 이 초기값 3은 과거 손으로 계산하던 시절에 뤼카가 M₁₂₇이 소수임을 증명할 때 사용하기도 했다. 초기값을 3으로 사용할 경우 수열의 첫 몇 항은 3, 7, 47, ... 이 된다.

3.2. 끝에서 두 번째 항의 부호 (레머 기호)

만약 $s\_\{p-2\}\backslash equiv0\backslash pmod\{M\_p\}$이면, 끝에서 두 번째 항은 $s\_\{p-3\}\backslash equiv\backslash pm\; 2^\{(p+1)/2\}\backslash pmod\{M\_p\}$이다. 이 끝에서 두 번째 항의 부호를 레머 기호 ϵ(s₀, p)라고 부른다.

2000년 S.Y. 게브레-에그지아베르(S.Y. Gebre-Egziabher)는 시작 값이 2/3이고 p ≠ 5일 때 부호가 다음과 같음을 증명했다.
:$\backslash epsilon\; (\{2\; \backslash over\; 3\},\backslash \; p)\; =\; (-1)\; ^\; \{p-1\; \backslash over\; 2\}$
즉, ϵ(2/3, p) = +1 이면 p = 1 (mod 4)이고 p ≠ 5이다.

같은 저자는 또한 월트먼(George Woltman)의 추측을 증명했는데, 시작 값이 4와 10일 때 p가 2 또는 5가 아니면 레머 기호는 다음과 같은 관계를 갖는다.
:$\backslash epsilon\; (10,\backslash \; p)\; =\; \backslash epsilon\; (4,\backslash \; p)\; \backslash \; \backslash times\; \backslash \; (-1)\; ^\; \{\{(p+1)(p+3)\}\; \backslash over\; 8\}$
즉, ϵ(4, p) × ϵ(10, p) = 1 이면 p = 5 or 7 (mod 8)이고 p ≠ 2, 5이다.

OEIS 수열 A123271은 각 메르센 소수 M_p에 대한 ϵ(4, p)를 보여준다.

4. 시간 복잡도

뤼카-레머 판별법 알고리즘에서 각 반복마다 비용이 많이 드는 연산은 `s`의 제곱(`s × s`)과 모듈러 연산(`mod M`)이다.

`mod M` 연산, 즉 $M\_p\; =\; 2^p\; -\; 1$에 대한 나머지 연산은 다음과 같은 속성을 이용하여 효율적으로 수행될 수 있다. 임의의 정수 k와 n에 대해,

:$k\; \backslash equiv\; (k\; \backslash bmod\; 2^n)\; +\; \backslash lfloor\; k/2^n\; \backslash rfloor\; \backslash pmod\{2^n\; -\; 1\}.$

이는 k를 $2^n\; -\; 1$로 나눈 나머지는 k의 하위 n 비트와 나머지 상위 비트들의 합을 $2^n\; -\; 1$로 나눈 나머지와 같다는 의미이다. 이 과정을 나머지가 n 비트보다 작아질 때까지 반복하면 나눗셈 없이 나머지를 구할 수 있다. 예를 들어, 916을 $2^5\; -\; 1\; =\; 31$로 나눈 나머지는 다음과 같이 계산할 수 있다. 916은 이진수로 1110010100₂이다.

따라서 916을 31로 나눈 나머지는 17이다.

알고리즘의 각 단계에서 계산되는 `s × s`의 값은 $M\_p^2$보다 작고, 이므로 최대 2p 비트를 가진다. 위의 나머지 계산법을 사용하면, 최대 한 번의 p-비트 덧셈 연산으로 나머지를 구할 수 있으며, 이는 선형 시간 복잡도, 즉 O(p) 안에 수행될 수 있다. (단, 계산 결과가 $2^p\; -\; 1$ 자체가 되는 예외적인 경우가 있으나 이는 쉽게 처리 가능하다.)

따라서 알고리즘의 전체 시간 복잡도는 p-비트 정수 두 개를 곱하는 데 사용되는 곱셈 알고리즘의 효율성에 따라 결정된다.
* 가장 기본적인 초등학교 방식 곱셈 알고리즘은 O(p²)의 시간이 걸린다. 뤼카-레머 판별법은 p-2번 반복하므로, 총 시간 복잡도는 O(p³)이 된다.
* 더 효율적인 쇤하게–슈트라센 알고리즘은 고속 푸리에 변환(FFT)을 이용하여 두 p-비트 정수를 O(p log p log log p) 시간에 곱할 수 있다. 이를 사용하면 뤼카-레머 판별법의 전체 시간 복잡도는 O(p² log p log log p) 또는 Õ(p²)로 줄어든다.
* 현재까지 알려진 가장 빠른 곱셈 알고리즘 중 하나인 퓌러 알고리즘은 두 p-비트 정수를 $p\; \backslash log\; p\backslash \; 2^\{O(\backslash log^*\; p)\}$ 시간에 곱할 수 있다.

다른 소수 판별법과 비교하면 다음과 같다.
* 밀러-라빈 소수 판별법은 가장 널리 쓰이는 확률적 소수 판별법 중 하나로, n자리 수에 대해 FFT 기반 곱셈을 사용하면 O(k n² log n log log n)의 비트 연산 시간이 걸린다. 여기서 k는 테스트 반복 횟수이다. 상수 k에 대해서는 뤼카-레머 판별법과 점근적 시간 복잡도가 비슷하지만, 실제로는 여러 번의 반복 수행 비용 등으로 인해 성능 차이가 발생할 수 있다.
* AKS 소수 판별법은 최초로 발견된 결정론적 다항 시간 소수 판별법이지만, 알려진 가장 효율적인 변형조차도 Õ(n⁶)의 비트 연산 시간이 필요하여 실제로는 매우 느리다.

5. 예시

메르센 소수 M₃ = 2³−1 = 7은 소수이다. 뤼카-레머 소수 판별법은 이를 다음과 같이 검증한다. p = 3이므로 수열 s는 p - 2 = 1번 업데이트된다. 초기값 s₀ = 4로 시작한다.

* $s\_1\; \backslash leftarrow\; (s\_0^2\; -\; 2)\; \backslash pmod\{M\_3\}\; =\; (4^2\; -\; 2)\; \backslash pmod\{7\}\; =\; (16\; -\; 2)\; \backslash pmod\{7\}\; =\; 14\; \backslash pmod\{7\}\; =\; 0$

최종 값 s₁이 0이므로, M₃는 소수라는 결론을 내릴 수 있다.

반면에, M₁₁ = 2¹¹−1 = 2047 = 23 × 89는 소수가 아닌 합성수이다. p = 11이므로 수열 s는 p - 2 = 9번 업데이트된다. 다시, s₀ = 4로 시작한다.

* $s\_1\; \backslash leftarrow\; (4^2\; -\; 2)\; \backslash pmod\{2047\}\; =\; 14$
* $s\_2\; \backslash leftarrow\; (14^2\; -\; 2)\; \backslash pmod\{2047\}\; =\; 194$
* $s\_3\; \backslash leftarrow\; (194^2\; -\; 2)\; \backslash pmod\{2047\}\; =\; 788$
* $s\_4\; \backslash leftarrow\; (788^2\; -\; 2)\; \backslash pmod\{2047\}\; =\; 701$
* $s\_5\; \backslash leftarrow\; (701^2\; -\; 2)\; \backslash pmod\{2047\}\; =\; 119$
* $s\_6\; \backslash leftarrow\; (119^2\; -\; 2)\; \backslash pmod\{2047\}\; =\; 1877$
* $s\_7\; \backslash leftarrow\; (1877^2\; -\; 2)\; \backslash pmod\{2047\}\; =\; 240$
* $s\_8\; \backslash leftarrow\; (240^2\; -\; 2)\; \backslash pmod\{2047\}\; =\; 282$
* $s\_9\; \backslash leftarrow\; (282^2\; -\; 2)\; \backslash pmod\{2047\}\; =\; 1736$

최종 값 s₉ = 1736은 0이 아니므로, M₁₁ = 2047은 소수가 아니라는 결론을 내릴 수 있다. M₁₁ = 2047은 자명하지 않은 인수를 가지고 있지만, 뤼카-레머 소수 판별법은 그 인수들이 무엇인지에 대한 어떠한 정보도 제공하지 않는다.

6. 정확성 증명

이 테스트의 정확성 증명은 레머가 제시한 원래 증명보다 간단하다. 먼저, 수열 $\{\backslash langle\}s\_i\{\backslash rangle\}$를 다음과 같이 정의한다.

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


증명의 목표는 메르센 소수 $M\_p\; =\; 2^p\; -\; 1$ (단, p는 소수)에 대해, $M\_p$가 소수인 것과 $s\_\{p-2\}\; \backslash equiv\; 0\; \backslash pmod\{M\_p\}$인 것이 필요충분조건임을 보이는 것이다.

수열 $\{\backslash langle\}s\_i\{\backslash rangle\}$는 점화 관계이며, 폐쇄 형식 해를 가진다. $\backslash omega\; =\; 2\; +\; \backslash sqrt\{3\}$와 $\backslash bar\{\backslash omega\}\; =\; 2\; -\; \backslash sqrt\{3\}$라고 하면, 수학적 귀납법을 통해 모든 i ≥ 0에 대해 다음과 같은 폐쇄 형식을 유도할 수 있다.

:$s\_i\; =\; \backslash omega^\{2^i\}\; +\; \backslash bar\{\backslash omega\}^\{2^i\}$

이 폐쇄 형식은 증명의 양방향, 즉 충분성($s\_\{p-2\}\; \backslash equiv\; 0\; \backslash pmod\{M\_p\}$이면 $M\_p$는 소수)과 필요성($M\_p$가 소수이면 $s\_\{p-2\}\; \backslash equiv\; 0\; \backslash pmod\{M\_p\}$) 모두에서 핵심적으로 사용된다. 상세한 증명 과정은 아래 하위 섹션에서 다룬다.

6.1. 충분성

이 테스트의 정확성 증명은 데릭 헨리 레머가 제시한 원래 증명보다 간단하다. 다음 정의를 상기해 보자.

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

증명의 목표는 $M\_p$가 소수인 것과 $s\_\{p-2\}\; \backslash equiv\; 0\; \backslash pmod\{M\_p\}$인 것이 필요충분조건임을 보이는 것이다.

수열 $\{\backslash langle\}s\_i\{\backslash rangle\}$는 폐쇄 형식 해를 갖는 점화 관계이다. $\backslash omega\; =\; 2\; +\; \backslash sqrt\{3\}$와 $\backslash bar\{\backslash omega\}\; =\; 2\; -\; \backslash sqrt\{3\}$이라고 하자. 그러면 수학적 귀납법에 의해 모든 i ≥ 0에 대해 $s\_i\; =\; \backslash omega^\{2^i\}\; +\; \backslash bar\{\backslash omega\}^\{2^i\}$가 성립한다.

:$s\_0\; =\; \backslash omega^\{2^0\}\; +\; \backslash bar\{\backslash omega\}^\{2^0\}\; =\; \backslash left(2\; +\; \backslash sqrt\{3\}\backslash right)\; +\; \backslash left(2\; -\; \backslash sqrt\{3\}\backslash right)\; =\; 4$
이고, n > 0에 대해
:$$
\begin{align}
s_n
&= s_{n-1}^2 - 2 \\
&= \left(\omega^{2^{n-1}} + \bar{\omega}^{2^{n-1}}\right)^2 - 2 \\
&= \omega^{2^n} + 2\omega^{2^{n-1}}\bar{\omega}^{2^{n-1}} + \bar{\omega}^{2^n} - 2 \\
&= \omega^{2^n} + \bar{\omega}^{2^n} + 2(\omega\bar{\omega})^{2^{n-1}} - 2.
\end{align}

이때 $\backslash omega\backslash bar\{\backslash omega\}\; =\; \backslash left(2\; +\; \backslash sqrt\{3\}\backslash right)\; \backslash left(2\; -\; \backslash sqrt\{3\}\backslash right)\; =\; 4\; -\; 3\; =\; 1$이므로,
:$s\_n\; =\; \backslash omega^\{2^n\}\; +\; \backslash bar\{\backslash omega\}^\{2^n\}.$
이 폐쇄 형식은 충분성 증명과 필요성 증명 모두에서 사용된다.

이제 $s\_\{p-2\}\; \backslash equiv\; 0\; \backslash pmod\{M\_p\}$라는 조건이 $M\_p$가 소수임을 함의하는 충분조건임을 증명한다. 다음은 J. W. 브루스가 제시하고 제이슨 보이치호프스키가 언급한 군론을 활용한 간결한 증명이다.

$s\_\{p-2\}\; \backslash equiv\; 0\; \backslash pmod\{M\_p\}$라고 가정하자. 그러면 어떤 정수 k에 대해
:$\backslash omega^\{2^\{p-2\}\}\; +\; \backslash bar\{\backslash omega\}^\{2^\{p-2\}\}\; =\; k\; M\_p$
가 성립한다. $\backslash bar\{\backslash omega\}\; =\; \backslash omega^\{-1\}$이므로,
:$\backslash omega^\{2^\{p-2\}\}\; +\; \backslash omega^\{-2^\{p-2\}\}\; =\; k\; M\_p.$
양변에 $\backslash omega^\{2^\{p-2\}\}$를 곱하면
:$\backslash left(\backslash omega^\{2^\{p-2\}\}\backslash right)^2\; +\; 1\; =\; k\; M\_p\; \backslash omega^\{2^\{p-2\}\}$
:$\backslash omega^\{2^\{p-1\}\}\; =\; k\; M\_p\; \backslash omega^\{2^\{p-2\}\}\; -\; 1.\backslash qquad\backslash qquad(1)$

귀류법을 사용하기 위해, M_p가 합성수라고 가정하고, q를 M_p의 가장 작은 소인수라고 하자. 메르센 수 $M\_p\; =\; 2^p\; -\; 1$ (단, p는 홀수 소수)는 항상 홀수이므로, q > 2이다. $\backslash mathbb\{Z\}\_q$를 모듈로 q인 정수의 체라고 하고, $X\; =\; \backslash left\backslash \{a\; +\; b\; \backslash sqrt\{3\}\; \backslash mid\; a,\; b\; \backslash in\; \backslash mathbb\{Z\}\_q\backslash right\backslash \}$라고 하자. X에서의 곱셈은 다음과 같이 정의된다.

:$\backslash left(a\; +\; \backslash sqrt\{3\}\; b\backslash right)\; \backslash left(c\; +\; \backslash sqrt\{3\}\; d\backslash right)\; =\; [(a\; c\; +\; 3\; b\; d)\; \backslash bmod\; q]\; +\; \backslash sqrt\{3\}\; [(a\; d\; +\; b\; c)\; \backslash bmod\; q].$

이 곱셈 연산에 대해 집합 X는 닫혀 있다. 즉, X의 원소들의 곱은 다시 X의 원소가 된다. X의 원소 개수(크기)는 $|X|\; =\; q^2$이다.

q > 2이므로, $\backslash omega\; =\; 2\; +\; \backslash sqrt\{3\}$와 $\backslash bar\{\backslash omega\}\; =\; 2\; -\; \backslash sqrt\{3\}$는 X에 속한다. X의 원소 중 곱셈에 대한 역원을 갖는 원소들의 집합은 군을 형성하며, 이를 X*로 표시하고 그 크기는 $|X^*|$이다. X에서 역원을 갖지 않는 원소는 $0\; =\; 0\; +\; 0\backslash sqrt\{3\}$뿐이므로, $|X^*|\; \backslash leq\; |X|\; -\; 1\; =\; q^2\; -\; 1$이다.

가정에서 $M\_p\; \backslash equiv\; 0\; \backslash pmod\{q\}$이고 $\backslash omega\; \backslash in\; X$이므로, X에서 식 (1)의 우변 첫 항은 0이 된다.
:$k\; M\_p\; \backslash omega^\{2^\{p-2\}\}\; \backslash equiv\; 0\; \backslash pmod\{q\}.$
따라서 식 (1)은 X에서 다음과 같이 된다.
:$\backslash omega^\{2^\{p-1\}\}\; \backslash equiv\; -1\; \backslash pmod\{q\}.$
양변을 제곱하면
:$\backslash omega^\{2^p\}\; \backslash equiv\; (-1)^2\; \backslash equiv\; 1\; \backslash pmod\{q\}.$
이는 $\backslash omega$가 곱셈군 X*에 속하며, 그 차수가 $2^p$를 나눔을 의미한다. 또한 $\backslash omega^\{2^\{p-1\}\}\; \backslash equiv\; -1\; \backslash not\backslash equiv\; 1\; \backslash pmod\{q\}$이므로, $\backslash omega$의 차수는 $2^\{p-1\}$을 나누지 않는다. 따라서 $\backslash omega$의 차수는 정확히 $2^p$이다.

라그랑주 정리에 따르면, 군의 원소의 차수는 군 전체의 크기(위수)를 나누어야 한다. 따라서 $\backslash omega$의 차수인 $2^p$는 군 X*의 크기 $|X^*|$를 나누어야 하고, 특히 $2^p\; \backslash leq\; |X^*|$여야 한다. 위에서 $|X^*|\; \backslash leq\; q^2\; -\; 1$이었으므로,
:
즉, 이다.

하지만 q는 합성수 $M\_p\; =\; 2^p\; -\; 1$의 가장 작은 소인수이다. 합성수 $N$의 가장 작은 소인수 $q$는 항상 $q\; \backslash leq\; \backslash sqrt\{N\}$을 만족하므로,
:$q\; \backslash leq\; \backslash sqrt\{M\_p\}\; \backslash implies\; q^2\; \backslash leq\; M\_p\; =\; 2^p\; -\; 1.$
결과적으로 와 $q^2\; \backslash leq\; 2^p\; -\; 1$라는 두 부등식을 얻는데, 이는 라는 명백한 모순을 발생시킨다.

이 모순은 처음에 M_p가 합성수라고 가정한 것에서 비롯되었다. 따라서 초기 가정은 거짓이며, M_p는 반드시 소수여야 한다.

6.2. 필요성

$M\_p$가 소수라고 가정하고, $s\_\{p-2\}\; \backslash equiv\; 0\; \backslash pmod\{M\_p\}$임을 보이는 것이 목표이다. 다음은 Ӧystein J. Rödseth가 제시한 간략화된 증명이다.

홀수 소수 $p\; >\; 2$에 대해 $M\_p\; =\; 2^p\; -\; 1\; \backslash equiv\; (-1)^p\; -\; 1\; \backslash equiv\; -2\; \backslash equiv\; 1\; \backslash pmod\; 3$이고, $M\_p\; =\; 2^p\; -\; 1\; \backslash equiv\; (-1)\; -\; 1\; \backslash equiv\; -2\; \backslash pmod\; 4$ (단, $p$는 홀수이므로 $p\; \backslash ge\; 3$이면 $2^p$는 8 이상이고 4의 배수), 즉 $M\_p\; \backslash equiv\; 3\; \backslash pmod\; 4$이다. 또한 $p\; \backslash ge\; 3$이면 $2^p$는 8의 배수이므로 $M\_p\; =\; 2^p\; -\; 1\; \backslash equiv\; -1\; \backslash equiv\; 7\; \backslash pmod\; 8$이다. 종합하면, $p>2$인 소수 $p$에 대해 $M\_p\; \backslash equiv\; 7\; \backslash pmod\{12\}$이다. 이차 상호 법칙의 보조 법칙과 르장드르 기호의 성질에 의해 $(3|M\_p)\; =\; -(M\_p|3)$ 이고, $(M\_p|3)\; =\; (1|3)\; =\; 1$이므로 $(3|M\_p)\; =\; -1$이다. 이는 3이 $M\_p$를 법으로 하는 제곱 비잉여임을 의미한다. 오일러의 기준에 따르면, 이는 다음 식과 동치이다.

:$3^\{\backslash frac\{M\_p-1\}\{2\}\}\; \backslash equiv\; -1\; \backslash pmod\{M\_p\}.$

반대로, 2는 $M\_p$를 법으로 하는 제곱 잉여이다. 왜냐하면 $M\_p\; \backslash equiv\; 7\; \backslash pmod\; 8$ 이므로 이차 상호 법칙의 보조 법칙에 의해 $(2|M\_p)=1$이기 때문이다. 오일러의 기준에 따라 다음이 성립한다.

:$2^\{\backslash frac\{M\_p-1\}\{2\}\}\; \backslash equiv\; 1\; \backslash pmod\{M\_p\}.$

위의 두 합동식을 결합하면 다음을 얻는다.

:$24^\{\backslash frac\{M\_p-1\}\{2\}\}\; \backslash equiv\; \backslash left(2^3\; \backslash cdot\; 3\backslash right)^\{\backslash frac\{M\_p-1\}\{2\}\}\; \backslash equiv\; \backslash left(2^\{\backslash frac\{M\_p-1\}\{2\}\}\backslash right)^3\; \backslash left(3^\{\backslash frac\{M\_p-1\}\{2\}\}\backslash right)\; \backslash equiv\; (1)^3(-1)\; \backslash equiv\; -1\; \backslash pmod\{M\_p\}.$

이제 유한체 $\backslash mathbb\{F\}\_\{M\_p^2\}\; =\; \backslash mathbb\{Z\}\_\{M\_p\}[\; \backslash sqrt\{3\}\; ]\; =\; \backslash \{a\; +\; b\backslash sqrt\{3\}\; \backslash mid\; a,\; b\; \backslash in\; \backslash mathbb\{Z\}\_\{M\_p\}\backslash \}$를 생각하자. 이 체에서 연산은 법 $M\_p$에 대해 이루어진다. $\backslash sigma\; =\; 2\backslash sqrt\{3\}$이라고 정의하면, 체 $\backslash mathbb\{F\}\_\{M\_p^2\}$에서 다음이 성립한다.

:$$
\begin{align}
(6+\sigma)^{M_p}
&= 6^{M_p} + \sigma^{M_p} && \text{(유한체에서의 이항정리)}\\
&= 6 + (2\sqrt{3})^{M_p} \\
&= 6 + 2^{M_p} (\sqrt{3})^{M_p} \\
&= 6 + 2 \cdot 3^{\frac{M_p}{2}} && \text{(페르마의 소정리: } a^{M_p} \equiv a \pmod{M_p}) \\
&= 6 + 2 \cdot 3^{\frac{M_p-1}{2}} \sqrt{3} \\
&= 6 + 2 (-1) \sqrt{3} && \text{(위에서 보인 } 3^{\frac{M_p-1}{2}} \equiv -1 \pmod{M_p}) \\
&= 6 - 2\sqrt{3} \\
&= 6 - \sigma.
\end{align}


여기서 $(x+y)^\{M\_p\}\; \backslash equiv\; x^\{M\_p\}\; +\; y^\{M\_p\}\; \backslash pmod\{M\_p\}$인 유한체에서의 이항정리와, 임의의 정수 $a$에 대해 $a^\{M\_p\}\; \backslash equiv\; a\; \backslash pmod\{M\_p\}$인 페르마의 소정리를 사용했다. 또한 $(\backslash sqrt\{3\})^\{M\_p\}\; =\; 3^\{\backslash frac\{M\_p\}\{2\}\}\; =\; 3^\{\backslash frac\{M\_p-1\}\{2\}\}\; \backslash sqrt\{3\}$ 임을 이용했다.

이제 $\backslash omega\; =\; 2\; +\; \backslash sqrt\{3\}$으로 정의하자. (이는 $s\_i$의 폐쇄 형식을 유도할 때 사용된 값과 같다.) $\backslash omega\; =\; \backslash frac\{(6+\backslash sigma)^2\}\{24\}$ 임을 확인하자.
$\backslash frac\{(6+\backslash sigma)^2\}\{24\}\; =\; \backslash frac\{(6+2\backslash sqrt\{3\})^2\}\{24\}\; =\; \backslash frac\{36\; +\; 24\backslash sqrt\{3\}\; +\; 12\}\{24\}\; =\; \backslash frac\{48\; +\; 24\backslash sqrt\{3\}\}\{24\}\; =\; 2\; +\; \backslash sqrt\{3\}\; =\; \backslash omega$.
이 $\backslash omega$를 사용하여 체 $\backslash mathbb\{F\}\_\{M\_p^2\}$에서 $\backslash omega^\{\backslash frac\{M\_p+1\}\{2\}\}$를 계산한다.

:$$
\begin{align}
\omega^{\frac{M_p+1}{2}}
&= \left(\frac{(6+\sigma)^2}{24}\right)^{\frac{M_p+1}{2}} \\
&= \frac{(6+\sigma)^{M_p+1}}{24^{\frac{M_p+1}{2}}} \\
&= \frac{(6+\sigma)(6+\sigma)^{M_p}}{24 \cdot 24^{\frac{M_p-1}{2}}} \\
&= \frac{(6+\sigma)(6-\sigma)}{24 \cdot (-1)} && \text{(위에서 보인 } (6+\sigma)^{M_p} = 6-\sigma \text{ 와 } 24^{\frac{M_p-1}{2}} \equiv -1 \pmod{M_p}) \\
&= \frac{36 - \sigma^2}{-24} \\
&= \frac{36 - (2\sqrt{3})^2}{-24} \\
&= \frac{36 - 12}{-24} \\
&= \frac{24}{-24} \\
&= -1.
\end{align}


이제 $\backslash omega\; \backslash bar\{\backslash omega\}\; =\; (2+\backslash sqrt\{3\})(2-\backslash sqrt\{3\})\; =\; 4-3\; =\; 1$ 이므로 $\backslash bar\{\backslash omega\}\; =\; \backslash omega^\{-1\}$이다. 위에서 얻은 식 $\backslash omega^\{\backslash frac\{M\_p+1\}\{2\}\}\; =\; -1$의 양변에 $\backslash bar\{\backslash omega\}^\{\backslash frac\{M\_p+1\}\{4\}\}$를 곱하면 다음과 같다.

:$$
\begin{align}
\omega^{\frac{M_p+1}{2}} \bar{\omega}^{\frac{M_p+1}{4}} &= -\bar{\omega}^{\frac{M_p+1}{4}} \\
\omega^{\frac{M_p+1}{4}} (\omega^{\frac{M_p+1}{4}} \bar{\omega}^{\frac{M_p+1}{4}}) &= -\bar{\omega}^{\frac{M_p+1}{4}} \\
\omega^{\frac{M_p+1}{4}} (\omega \bar{\omega})^{\frac{M_p+1}{4}} &= -\bar{\omega}^{\frac{M_p+1}{4}} \\
\omega^{\frac{M_p+1}{4}} (1)^{\frac{M_p+1}{4}} &= -\bar{\omega}^{\frac{M_p+1}{4}} \\
\omega^{\frac{M_p+1}{4}} + \bar{\omega}^{\frac{M_p+1}{4}} &= 0
\end{align}

여기서 $M\_p\; =\; 2^p\; -\; 1$ 이므로 $\backslash frac\{M\_p+1\}\{4\}\; =\; \backslash frac\{2^p\}\{4\}\; =\; 2^\{p-2\}$이다. 따라서 다음을 얻는다.
:$\backslash omega^\{2^\{p-2\}\}\; +\; \backslash bar\{\backslash omega\}^\{2^\{p-2\}\}\; =\; 0$

수열 $s\_i$의 폐쇄 형식 해가 $s\_i\; =\; \backslash omega^\{2^i\}\; +\; \backslash bar\{\backslash omega\}^\{2^i\}$ 이므로, 위 식은 $s\_\{p-2\}\; =\; 0$ (체 $\backslash mathbb\{F\}\_\{M\_p^2\}$에서) 임을 의미한다. $s\_\{p-2\}$는 정수들의 연산으로 정의되므로, 이는 $s\_\{p-2\}$가 $M\_p$의 배수임을 뜻한다. 즉,
:$s\_\{p-2\}\; \backslash equiv\; 0\; \backslash pmod\{M\_p\}.$
이것으로 필요성 증명이 완료된다.

7. 응용

뤼카-레머 소수판별법은 Prime95 소프트웨어에 사용되며, 현재까지 알려진 대부분의 메르센 소수는 이 판별법을 통해 발견되었다.

특히, GIMPS(Great Internet Mersenne Prime Search) 프로젝트에서는 큰 소수를 찾는 주요 판별법으로 뤼카-레머 소수판별법을 사용한다. GIMPS는 이 판별법을 활용하여 현재까지 알려진 가장 큰 소수들을 성공적으로 찾아냈다. 이 판별법은 매우 큰 수에 대해서도 합리적인 시간 안에 소수 여부를 판별할 수 있다는 점에서 가치가 높다. 반면, 비슷한 속도를 가진 페팽의 검사는 모든 페르마 수에 적용 가능하지만, 계산상의 한계로 인해 뤼카-레머 소수판별법보다 훨씬 작은 범위의 수에 대해서만 사용할 수 있다.