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

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

역사

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

알고리즘

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

초깃값

• 만약 k의 값이 짝수일 경우, k가 홀수가 될 때까지 k를 2로 나눠 나간다. 여기서 2로 나눠질 때마다 n의 값에 1을 더한다.
• k = 1인 경우에는 s₀ = 4가 된다. 이때 뤼카-레머-리젤 소수판별법은 뤼카-레머 소수판별법과 완전히 똑같아지며, k = 1이면서 n ≡ 3 (mod 4)인 경우 s₀ = 3으로 해도 된다.
• k = 3인 경우, n ≡ 1 (mod 4)인 경우에는 N ≡ 0 (mod 5)가 되어 N의 값이 5인 경우를 제외하면 N이 합성수가 된다. 또한 n ≡ 2 (mod 4)인 경우에는 맨 위의 경우에 해당한다. 따라서 n ≡ 0 또는 3인 경우에만 고려해도 되고, 이 경우에 s₀=5778이 된다.
• k ≡ 1 또는 5 (mod 6)이고 $3\nmid N$인 경우, $s_{0}=(2+{\sqrt {3}})^{k}+(2-{\sqrt {3}})^{k}=\lceil (2+{\sqrt {3}})^{k}\rceil$이다.
• 위의 경우에 모두 해당하지 않는 경우, 다음 방식으로 s₀을 구하면 된다.
  • 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을 이용하여 V_k의 값을 구한다. 이때, s₀=V_k가 된다.

예시

1. 47은 소수

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

• $s_{1}=s_{0}^{2}-2\equiv 44^{2}-2\equiv 1934\equiv 7{\pmod {47}}$
• $s_{2}=s_{1}^{2}-2\equiv 7^{2}-2\equiv 47\equiv 0{\pmod {47}}$

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

2. 2303은 합성수

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

• $V_{2i}=V_{i}^{2}-2$
• $V_{2i+1}=V_{i}V_{i+1}-P$

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

• $V_{0}=2$
• 이 과정에서는 V₁을 계산해야 하지만 V₁=P이므로 V₁=8이 되고, V₂=V₁²-2=62가 된다. 1001에서 1을 지운다.
• 001에서 맨 처음 비트가 0이므로 첫 번째 공식을 사용한다. $V_{2\cdot 1}=V_{2}=V_{1}^{2}-2=62$가 되고, $V_{2+1}=V_{3}=V_{1}V_{2}-8=488$이 된다. 맨 앞의 0을 지운다.
• 01에서 맨 처음 비트가 0이므로 첫 번째 공식을 사용한다. $V_{2\cdot 2}=V_{4}=V_{2}^{2}-2=3842\equiv 1539{\pmod {2303}}$이 되고, $V_{4+1}=V_{5}=V_{2}V_{3}-8=30248\equiv 309{\pmod {2303}}$이 된다. 맨 앞의 0을 지운다.
• 1에서 맨 처음 비트가 1이므로 두 번째 공식을 사용한다. $V_{2\cdot 4+1}=V_{9}=V_{4}V_{5}-8\equiv 1133{\pmod {2303}}$이 된다. 맨 앞의 1을 지운다.

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

• $s_{1}=s_{0}^{2}-2\equiv 1133^{2}-2\equiv 1283687\equiv 916{\pmod {2303}}$
• $s_{2}=s_{1}^{2}-2\equiv 916^{2}-2\equiv 839054\equiv 762{\pmod {2303}}$
• $s_{3}=s_{2}^{2}-2\equiv 762^{2}-2\equiv 580642\equiv 286{\pmod {2303}}$
• $s_{4}=s_{3}^{2}-2\equiv 286^{2}-2\equiv 81794\equiv 1189{\pmod {2303}}$
• $s_{5}=s_{4}^{2}-2\equiv 1189^{2}-2\equiv 1413719\equiv 1980{\pmod {2303}}$
• $s_{6}=s_{5}^{2}-2\equiv 1980^{2}-2\equiv 3920398\equiv 692{\pmod {2303}}$

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

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