뤼카–레머–리젤 소수판별법

**뤼카-레머-리젤 소수판별법** (Lucas-Lehmer-Riesel Primality Test)은 어떤 특정한 형태의 자연수 (*N* = *k* ⋅ 2*n* − 1, *k* *n*일 때)에 대해 적용할 수 있는 결정론적 소수판별법이다.

## 역사
에두아르 뤼카 (Édouard Lucas)의 원래 알고리즘을 데릭 레머 (Derrick Henry Lehmer)가 개량한 알고리즘인 뤼카-레머 소수판별법을 더 많은 수들에 대해 적용할 수 있도록 수학자 한스 리젤 (Hans Riesel)이 한번 더 개량한 알고리즘이다.

## 알고리즘

# 입력한 수 (*k* ⋅ 2*n* − 1, *k* *n*)를 받고, 밑에 나와 있는 초깃값을 구하는 방법을 통해 초깃값 s0을 구한다.
# 수열 sn을 다음과 같이 정의한다.
## s_0=\Box, s_n=s_{n-1}^2-2
## 여기서 네모에 들어갈 값, 즉 s0의 값은 초깃값을 구하는 과정을 통해 알 수 있다.
# 만약 s_{n-2}\equiv0\pmod{N}이라면 N은 소수가 된다. 아닌 경우, N은 합성수가 된다.

## 초깃값

* 만약 k의 값이 짝수일 경우, k가 홀수가 될 때까지 k를 2로 나눠 나간다. 여기서 2로 나눠질 때마다 n의 값에 1을 더한다.
* k = 1인 경우에는 s0 = 4가 된다. 이때 뤼카-레머-리젤 소수판별법은 뤼카-레머 소수판별법과 완전히 똑같아지며, k = 1이면서 n ≡ 3 (mod 4)인 경우 s0 = 3으로 해도 된다.
* k = 3인 경우, n ≡ 1 (mod 4)인 경우에는 N ≡ 0 (mod 5)가 되어 N의 값이 5인 경우를 제외하면 N이 합성수가 된다. 또한 n ≡ 2 (mod 4)인 경우에는 맨 위의 경우에 해당한다. 따라서 n ≡ 0 또는 3인 경우에만 고려해도 되고, 이 경우에 s0=5778이 된다.
* k ≡ 1 또는 5 (mod 6)이고 3\nmid N인 경우, s_0=(2+\sqrt3)^{k}+(2-\sqrt3)^{k}=\lceil(2+\sqrt3)^{k}\rceil이다.
* 위의 경우에 모두 해당하지 않는 경우, 다음 방식으로 s0을 구하면 된다.
** 1. \left ( \frac{P-2}{N} \right )=1, \left ( \frac{P+2}{N} \right )=-1를 만족하는 정수 P의 값을 구한다. 여기서 괄호 표시는 야코비 기호이며, 만약 3 ∤ k인 경우 P=4를 이용하면 된다. 또한 5, 8, 9, 11 중에 위의 P의 조건을 만족시키는 수가 최소한 하나라도 있을 확률은 85% 정도이다.
** 2. 다음과 같은 뤼카 수열을 정의한다.
*** V_0=2, V_1=P, V_k=PV_{k-1}-QV_{k-2}
** 3. 위에서 구한 값 P와 Q=1을 이용하여 Vk의 값을 구한다. 이때, s0=Vk가 된다.

## 예시

### 1. 47은 소수
47=3 ⋅ 24 - 1이므로 k=3, n=4이다. 여기서 34이므로 조건을 만족하고, k=3인 경우 초깃값은 s0=5778≡44 (mod 47)이 된다. 다음으로, 수열 sn의 정의를 따라 sn-2=s2를 계산해 준다.

*s_1=s_0^2-2\equiv44^2-2\equiv1934\equiv7\pmod{47}
*s_2=s_1^2-2\equiv7^2-2\equiv47\equiv0\pmod{47}

s4-2=s2≡0 (mod 47)이 되므로 47은 소수가 된다.

### 2. 2303은 합성수
2303 = 9 ⋅ 28 - 1이므로 k=9, n=8이다. 여기서 98이므로 조건을 만족하고, k=9인 경우는 앞 문단 맨 밑쪽에 나온 방법으로 초깃값을 정해야 한다. P=5, 8, 9, 11 중  조건을 만족하는 값을 찾으면 P=8이고 (\left ( \frac{6}{2303} \right )=1이고 \left ( \frac{10}{2303} \right )=-1이다), Vk의 값을 구할 때에는 다음 두 효율적인 공식을 보통 많이 사용한다.

* V_{2i}=V_i^2-2
* V_{2i+1}=V_iV_{i+1}-P

이 공식을 이용할 때에는 먼저 V0으로 시작하고, k를 이진수 형태로 바꾼다. 만약 맨 처음 비트를 제외하고 1이 있는 비트가 있으면 Vi를 계산한 후 Vi+1도 계산해 주어야 한다. 이 예시의 경우 맨 앞의 1을 제외하고 1이 한 군데 더 있으므로 (1001에서 맨 뒷쪽에 있다) 모든 과정에서 Vi를 계산하는 동시에 Vi+1도 계산해 주어야 한다.이 예시의 경우, k=9는 이진수로 바꾸면 1001(2)가 된다. 여기서 맨 앞쪽 비트에 0이 나오면 Vi에 대해 (Vi+1이 아니다) 첫 번째 공식을 사용하고, 1이 나온 경우에는 두 번째 공식을 사용한 후 (여기서도 마찬가지로 Vi에 대해서만 계산한다. Vi+1은 그대로 둔다) 맨 앞쪽의 비트를 지우고 이 과정을 모든 비트에 대해 반복하면 된다.

* V_0=2
* 이 과정에서는 V1을 계산해야 하지만 V1=P이므로 V1=8이 되고, V2=V12-2=62가 된다. 1001에서 1을 지운다.
* 001에서 맨 처음 비트가 0이므로 첫 번째 공식을 사용한다. V_{2\cdot1}=V_2=V_1^2-2=62가 되고, V_{2+1}=V_3=V_1V_2-8=488이 된다. 맨 앞의 0을 지운다.
* 01에서 맨 처음 비트가 0이므로 첫 번째 공식을 사용한다. V_{2\cdot2}=V_4=V_2^2-2=3842\equiv1539\pmod{2303}이 되고, V_{4+1}=V_5=V_2V_3-8=30248\equiv309\pmod{2303}이 된다. 맨 앞의 0을 지운다.
* 1에서 맨 처음 비트가 1이므로 두 번째 공식을 사용한다. V_{2\cdot4+1}=V_9=V_4V_5-8\equiv1133\pmod{2303}이 된다. 맨 앞의 1을 지운다.

따라서 s_0=V_k=V_9\equiv1133\pmod{2303}이 된다. 여기서 초깃값을 찾는 과정이 복잡해 보일 수 있으나, 실제로 아주 큰 수를 소수판별할 때에는 주 과정에 비해 계산 시간을 거의 무시할 수 있을 정도로 간단해지게 된다. 이제 이 초깃값을 가지고 알고리즘 문단의 2번째 과정을 계산한다.

* s_1=s_0^2-2\equiv1133^2-2\equiv1283687\equiv916\pmod{2303}
* s_2=s_1^2-2\equiv916^2-2\equiv839054\equiv762\pmod{2303}
* s_3=s_2^2-2\equiv762^2-2\equiv580642\equiv286\pmod{2303}
* s_4=s_3^2-2\equiv286^2-2\equiv81794\equiv1189\pmod{2303}
* s_5=s_4^2-2\equiv1189^2-2\equiv1413719\equiv1980\pmod{2303}
* s_6=s_5^2-2\equiv1980^2-2\equiv3920398\equiv692\pmod{2303}

s8-2=s6이 2303으로 나눴을 때 나머지가 0이 아니므로 (692이다), 2303은 합성수가 된다. 실제로 2303=72⋅47이다.

실제로 이렇게 작은 수들에 대해서는 이 소수판별법은 매우 빠르지 않기 때문에 직접 나눠 보면서 확인하는 방법이나 페르마의 소정리를 이용한 소수판별법이 많이 쓰인다. 하지만 테스트할 수가 1000만 자리가 넘어가는 경우에서는 이 소수판별법의 효율이 다른 소수판별법들을 크게 뛰어넘기 때문에 이 소수판별법을 주로 사용한다.

분류:소수 판별법