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

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

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

알고리즘 

 입력한 수 (k ⋅ 2n − 1, k < 2n)를 받고, 밑에 나와 있는 초깃값을 구하는 방법을 통해 초깃값 s0을 구한다.
 수열 sn을 다음과 같이 정의한다.
 
 여기서 네모에 들어갈 값, 즉 s0의 값은 초깃값을 구하는 과정을 통해 알 수 있다.
 만약 이라면 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)이고 인 경우, 이다.
 위의 경우에 모두 해당하지 않는 경우, 다음 방식으로 s0을 구하면 된다.
 1. 를 만족하는 정수 P의 값을 구한다. 여기서 괄호 표시는 야코비 기호이며, 만약 3 ∤ k인 경우 P=4를 이용하면 된다. 또한 5, 8, 9, 11 중에 위의 P의 조건을 만족시키는 수가 최소한 하나라도 있을 확률은 85% 정도이다.
 2. 다음과 같은 뤼카 수열을 정의한다.
 
 3. 위에서 구한 값 P와 Q=1을 이용하여 Vk의 값을 구한다. 이때, s0=Vk가 된다.

예시

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

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

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

 
 

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

 
 이 과정에서는 V1을 계산해야 하지만 V1=P이므로 V1=8이 되고, V2=V12-2=62가 된다. 1001에서 1을 지운다.
 001에서 맨 처음 비트가 0이므로 첫 번째 공식을 사용한다. 가 되고, 이 된다. 맨 앞의 0을 지운다.
 01에서 맨 처음 비트가 0이므로 첫 번째 공식을 사용한다. 이 되고, 이 된다. 맨 앞의 0을 지운다.
 1에서 맨 처음 비트가 1이므로 두 번째 공식을 사용한다. 이 된다. 맨 앞의 1을 지운다.

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

 
 
 
 
 
 

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

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