뤼카–레머–리젤 소수판별법 문서 원본 보기

{{위키데이터 속성 추적}}
'''뤼카-레머-리젤 소수판별법''' (Lucas-Lehmer-Riesel Primality Test)은 어떤 특정한 형태의 자연수 (''N'' = ''k'' ⋅ 2<sup>''n''</sup> − 1, ''k'' < 2<sup>''n''</sup>일 때)에 대해 적용할 수 있는 [[결정론적 알고리즘|결정론적]] [[소수판별법]]이다.

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

== 알고리즘 ==

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

== 초깃값 ==

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

== 예시 ==

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

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

s<sub>4-2</sub>=s<sub>2</sub>≡0 (mod 47)이 되므로 47은 소수가 된다.

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

* <math>V_{2i}=V_i^2-2</math>
* <math>V_{2i+1}=V_iV_{i+1}-P</math>

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

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

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

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

s<sub>8-2</sub>=s<sub>6</sub>이 2303으로 나눴을 때 나머지가 0이 아니므로 (692이다), 2303은 합성수가 된다. 실제로 2303=7<sup>2</sup>⋅47이다.

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

[[분류:소수 판별법]]