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

1. 개요

뤼카–레머–리젤 소수판별법은 에두아르 뤼카가 고안하고 데릭 레머가 개선한 알고리즘으로, 한스 리젤이 더 많은 수에 적용할 수 있도록 확장했다. 이 알고리즘은 주어진 수 N = k ⋅ 2ⁿ - 1이 소수인지 판별하는 데 사용되며, 뤼카-레머 검사법과 유사하게 수열의 값을 활용한다. k와 n 값에 따라 초기값을 설정하고, 수열의 값을 계산하여 N이 소수인지 판별한다. LLR 소프트웨어는 이 알고리즘을 실행하는 프로그램으로, 분산 컴퓨팅 프로젝트에서 활용된다.

2. 역사

뤼카–레머–리젤 소수판별법은 프랑스 수학자 에두아르 뤼카 Édouard Lucas^프랑스어가 처음 고안한 알고리즘에서 시작되었다. 이후 미국의 수학자 데릭 레머 Derrick Henry Lehmer^영어가 뤼카의 알고리즘을 개선하여 뤼카-레머 소수판별법을 만들었다. 스웨덴의 수학자 한스 리젤 Hans Riesel^swe은 이 뤼카-레머 소수판별법을 더 많은 종류의 수에 적용할 수 있도록 확장하여 현재의 뤼카–레머–리젤 소수판별법을 완성하였다.

3. 알고리즘

뤼카–레머–리젤 소수판별법은 주어진 수 N = k ⋅ 2ⁿ − 1 (단, k < 2ⁿ)이 소수인지 합성수인지를 판별하는 알고리즘이다. 이 방법은 뤼카-레머 소수 판별법과 매우 유사하지만, 사용하는 수열의 초깃값 u₀가 k의 값에 따라 달라진다는 점이 특징이다.

알고리즘의 단계는 다음과 같다.
# 판별하려는 수 N = k ⋅ 2ⁿ − 1 (k < 2ⁿ)을 정의한다.
# k의 값에 따라 적절한 초깃값 u₀를 결정한다.
# 수열 u_i 를 다음 점화식을 이용해 u_n−2까지 계산한다.
#: $u\_\{i+1\}\; =\; u\_i^2\; -\; 2\; \backslash quad\; (i\; \backslash ge\; 0)$
# 계산된 u_n−2 값을 확인하여 N으로 나누어떨어지는지 검사한다.
# 만약 $u\_\{n-2\}\; \backslash equiv\; 0\; \backslash pmod\{N\}$ 이면, N은 소수이다.
# 그렇지 않으면, N은 합성수이다.

즉, N이 소수일 필요충분 조건은 N이 u_n−2를 나누는 것이다. 초깃값 u₀를 결정하는 구체적인 방법은 k의 값에 따라 달라지며, Rödseth가 제안한 일반적인 방법도 존재한다.

3.1. 초깃값 설정

뤼카–레머–리젤 소수판별법은 주어진 수 N = k ⋅ 2ⁿ − 1 (단, k < 2ⁿ)의 소수 여부를 판별하는 알고리즘이다. 이 판별법은 뤼카-레머 소수판별법과 기본적인 구조는 유사하지만, 사용하는 수열의 초깃값 u₀가 k의 값에 따라 달라지는 점이 특징이다.

먼저 수열 u_i를 다음과 같은 점화식으로 정의한다.
:$u\_0\; =\; \backslash text\{초깃값\},\; \backslash quad\; u\_\{i+1\}\; =\; u\_i^2\; -\; 2\; \backslash quad\; (i\; \backslash ge\; 0)$
이때 N이 소수일 필요충분 조건은 u_n−2가 N으로 나누어떨어지는 것, 즉 $u\_\{n-2\}\; \backslash equiv\; 0\; \backslash pmod\{N\}$을 만족하는 것이다. 만약 이 조건을 만족하면 N은 소수이고, 그렇지 않으면 N은 합성수이다.

초깃값 u₀는 k와 n의 값에 따라 다음과 같이 결정된다.

* 만약 k가 짝수라면, k가 홀수가 될 때까지 k를 2로 나누고, 나눌 때마다 n의 값에 1을 더한다. 이후 홀수가 된 k와 새로 계산된 n을 기준으로 아래의 경우에 따라 u₀를 결정한다.
* k = 1인 경우:
* 일반적으로 u₀ = 4로 설정한다. 이 경우 뤼카-레머 소수판별법과 동일해진다.
* 만약 n ≡ 3 (mod 4)이라면, u₀ = 3으로 설정할 수도 있다.
* 만약 n ≡ 1 (mod 4)이라면, u₀ = 4로 설정한다. (N이 메르센 수가 될 수 있는 경우)
* k = 3인 경우:
* 만약 n ≡ 1 (mod 4)이라면, N = 3 ⋅ 2ⁿ - 1은 5로 나누어떨어진다. 따라서 N = 5 (즉, n=1)인 경우를 제외하면 항상 합성수이므로 소수판별을 할 필요가 없다.
* 만약 n ≡ 2 (mod 4)이라면, 이는 k가 짝수인 경우로 변환되어 처리된다.
* 따라서 n ≡ 0 또는 3 (mod 4)인 경우만 고려하며, 이때 u₀ = 5778로 설정한다.
* k ≡ ±1 (mod 6)이고 N이 3으로 나누어떨어지지 않는 경우: (k ≡ 1 (mod 6)이고 n이 홀수이거나, k ≡ 5 (mod 6)이고 n이 짝수인 경우)
* u₀ = $(2\; +\; \backslash sqrt\{3\})^k\; +\; (2\; -\; \backslash sqrt\{3\})^k$ 로 설정한다. 이 값은 $\backslash lceil(2+\backslash sqrt\{3\})^\{k\}\backslash rceil$ 와 같다.
* 또는 다음과 같이 정의되는 뤼카 수열 v_m을 이용하여 u₀ = v_k로 설정할 수도 있다.
:$$
v_{m}
= \begin{cases}
2 & \text{if } m = 0 \\
4 & \text{if } m = 1 \\
4v_{m-1} - v_{m-2} & \text{if } m \ge 2
\end{cases}

* 위의 경우에 해당하지 않는 경우 (주로 k가 3의 배수일 때): Rödseth가 제안한 다음 방법을 사용할 수 있다.
* 1. 다음 두 야코비 기호 조건을 만족하는 정수 P를 찾는다.
:$\backslash left(\backslash frac\{P-2\}\{N\}\backslash right)=1\; \backslash quad\backslash text\{and\}\backslash quad\; \backslash left(\backslash frac\{P+2\}\{N\}\backslash right)=-1$
* 실제로는 P = 5, 8, 9, 11 등의 작은 값들 중 하나가 조건을 만족할 확률이 약 85% 정도로 높다.
* 만약 k가 3의 배수가 아니라면 (즉, k ≡ ±1 (mod 6)인 경우), P = 4를 사용하면 되므로 별도로 P를 찾을 필요가 없다.
* 2. 찾은 P를 이용하여 뤼카 수열 V_m(P, 1)을 계산한다. 이 수열은 $V\_0=2,\; V\_1=P,\; V\_m=PV\_\{m-1\}-V\_\{m-2\}$ (m ≥ 2) 로 정의된다.
* 3. 초깃값 u₀는 V_k(P, 1)을 N으로 나눈 나머지, 즉 $u\_0\; \backslash equiv\; V\_k(P,1)\; \backslash pmod\{N\}$ 으로 설정한다.

이 초깃값 u₀를 결정하는 과정은 전체 소수판별 과정에 비해 시간이 적게 소요된다.

3.2. 수열 계산

수열 {u_i}는 다음과 같이 점화식으로 정의한다. 초기값 u₀는 아래 방법으로 결정하고, 음이 아닌 정수 i ≥ 0에 대해 다음 식을 만족한다.
$u\_\{i+1\}\; =\; u\_i^2\; -\; 2$

N = k ⋅ 2ⁿ − 1 (단, k < 2ⁿ) 형태의 수가 소수인지 판별할 때, N이 소수일 필요충분 조건은 N이 u_n−2를 나누는 것이다. 즉, $u\_\{n-2\}\; \backslash equiv\; 0\; \backslash pmod\{N\}$이면 N은 소수이고, 그렇지 않으면 합성수이다.

이 알고리즘은 뤼카-레머 소수 판별법과 매우 유사하지만, 수열 {u_i}의 초깃값 u₀가 k의 값에 따라 달라진다는 차이점이 있다. 초깃값 u₀는 k의 값에 따라 다음과 같이 결정된다.

* k ≡ 1 또는 5 (mod 6)인 경우: 만약 (k ≡ 1 (mod 6)이고 n이 짝수)이거나 (k ≡ 5 (mod 6)이고 n이 홀수)이면, 3이 N을 나누므로 N은 소수가 아니다 (단, N=3인 경우는 제외). 그 외의 경우, N ≡ 7 (mod 24)이며, 루카스 V(4,1) 수열을 사용하여 초깃값을 계산할 수 있다. 이때 초깃값 u₀는 해당 수열의 k번째 항으로, 다음과 같이 주어진다.
$u\_0\; =\; V\_k(4,\; 1)\; \backslash equiv\; (2+\backslash sqrt\{3\})^k\; +\; (2-\backslash sqrt\{3\})^k\; \backslash pmod\{N\}$
이는 k=1일 때 뤼카-레머 소수 판별법과 동일해진다.
* k가 3의 배수인 경우: 적절한 u₀ 값을 선택하는 것이 더 복잡하다. k = 3이고 n ≡ 0 또는 3 (mod 4)인 경우에는 u₀ = 5778을 사용할 수 있다.
* 대안적인 방법 (Rödseth 1994): k가 3의 배수인 경우를 포함하여 초깃값을 찾는 더 쉬운 방법이다. 먼저 다음 야코비 기호 등식을 만족하는 정수 P를 찾는다.
$\backslash left(\backslash frac\{P-2\}\{N\}\backslash right)=1\; \backslash quad\backslash text\{and\}\backslash quad\; \backslash left(\backslash frac\{P+2\}\{N\}\backslash right)=-1$
일반적으로 몇 개의 작은 P 값(예: 5, 8, 9, 11)을 시도하면 금방 찾을 수 있다. P 값을 찾으면, 루카스 수열 V_k(P,1)을 이용하여 초깃값을 계산한다.
$u\_0\; \backslash equiv\; V\_k(P,\; 1)\; \backslash pmod\{N\}$
만약 k가 3의 배수가 아니라면, P=4를 사용하면 되므로 별도의 탐색 과정이 필요 없다.

3.3. 소수 판별

판별하려는 수 $N$을 $N\; =\; k\; \backslash cdot\; 2^n\; -\; 1$ (단, ) 형태로 둔다.
그 다음, 수열 $u\_i$를 다음과 같이 정의한다.
초깃값 $u\_0$는 $k$의 값에 따라 결정되며(구체적인 방법은 다음 절에서 설명한다), 음이 아닌 정수 $i\; \backslash ge\; 0$에 대해 점화식을
:$u\_\{i+1\}\; =\; u\_i^2\; -\; 2$
로 정한다.

이때, $N$이 소수일 필요충분 조건은 $N$이 $u\_\{n-2\}$를 나누는 것이다. 즉, $u\_\{n-2\}\; \backslash equiv\; 0\; \backslash pmod\{N\}$ 이 성립하면 $N$은 소수이고, 그렇지 않으면 합성수이다.

이 알고리즘은 뤼카-레머 소수 판별법과 매우 유사하지만, 사용하는 수열 $u\_i$의 초깃값 $u\_0$가 $k$ 값에 따라 달라진다는 점이 다르다.

4. 알고리즘 작동 원리

뤼카-레머-리젤 소수 판별법은 군론을 이용한 소수 판별법의 한 종류이다. 어떤 정수 N이 소수인지 판별하기 위해, N을 법으로 하는 2차 확대의 승법군을 활용한다. 만약 N이 소수라면, 이 승법군의 위수는 N² − 1이 된다. 중요한 점은 이 군이 위수가 N + 1인 부분군을 가지며, 이 부분군의 생성원을 찾는 것이 판별법의 핵심이다.

이 알고리즘은 뤼카-레머 소수 판별법과 매우 유사하지만, 판별하려는 수 N = k ⋅ 2ⁿ − 1의 형태에서 k 값에 따라 계산 시작점이 달라진다는 특징이 있다. 알고리즘은 다음과 같이 정의된 수열 u_i를 사용한다. 모든 i > 0에 대해:
: $u\_i\; =\; u\_\{i-1\}^2-2\; \backslash ,$

이 점화식을 만족하는 수열 u_i는 뤼카 수열과 밀접한 관련이 있다. 뤼카-레머 판별법에서처럼 $u\_i\; =\; a^\{2^i\}\; +\; a^\{-2^i\}$ 형태로 생각할 수 있으며, 이는 수열 $w\_i\; =\; a^i\; +\; a^\{-i\}$의 2ⁱ번째 항에 해당한다. 여기서 a는 특정 이차 방정식의 근이며, 수열 w_i는 뤼카 수열의 점화식 $w\_\{i+2\}\; =\; \backslash alpha\; w\_\{i+1\}\; +\; \backslash beta\; w\_i$를 만족한다. 실제로는 k ⋅ 2ⁱ번째 항을 다루게 되는데, 뤼카 수열에서 k번째 항마다 추출한 부분 수열(즉, 0번째 항부터 시작하여 매 k번째 항을 취하는 것) 역시 뤼카 수열이므로, 적절한 시작 값 u₀를 선택함으로써 계수 k의 영향을 반영할 수 있다.

N = k ⋅ 2ⁿ − 1 (단, k < 2ⁿ) 형태의 수가 주어졌을 때, N이 소수일 필요충분조건은 위에서 정의된 수열의 n − 2번째 항인 u_n−2가 N으로 나누어떨어지는 것이다. 즉, $u\_\{n-2\}\; \backslash equiv\; 0\; \backslash pmod\{N\}$ 이 성립하는지 확인한다.

시작 값 u₀는 k의 값에 따라 결정된다.
* 만약 k ≡ 1 또는 5 (mod 6)이고 특정 조건을 만족하지 않으면(예: 3이 N을 나누지 않는 경우), 뤼카 V(4,1) 수열의 k번째 항을 u₀로 사용할 수 있다. 이는 일반적인 뤼카-레머 소수 판별법의 일반화로 볼 수 있다.
* k가 3의 배수인 경우 등 다른 경우에는 시작 값을 찾는 것이 더 복잡하다. Rödseth가 제안한 대안적인 방법은 야코비 기호를 이용하여 특정 조건을 만족하는 P 값을 찾는 것이다.
:$\backslash left(\backslash frac\{P-2\}\{N\}\backslash right)=1\; \backslash quad\backslash text\{and\}\backslash quad\; \backslash left(\backslash frac\{P+2\}\{N\}\backslash right)=-1$
이러한 P 값을 찾은 후(보통 5, 8, 9, 11 중 하나가 빠르게 찾아진다), 뤼카 수열 V_k(P,1)을 계산하여 u₀ (mod N)를 결정한다. 이 시작 값 선택 과정은 주 판별 과정에 비해 시간이 거의 소요되지 않는다.

5. 예시

이 섹션에서는 뤼카–레머–리젤 소수판별법을 사용하여 특정 수가 소수인지 합성수인지 판별하는 구체적인 예를 살펴본다. 아래 하위 섹션에서는 47과 2303을 예로 들어 판별 과정을 자세히 설명한다.

이 판별법은 47이나 2303과 같이 상대적으로 작은 수에 대해서는 직접 나누어 보거나 페르마 소수판별법 등 다른 방법이 더 효율적일 수 있다. 하지만 판별하려는 수가 매우 커지면(예: 1000만 자리 이상) 뤼카–레머–리젤 소수판별법의 효율성이 다른 소수판별법들을 크게 앞서기 때문에 주로 사용된다.

5.1. 47은 소수

47은 뤼카–레머–리젤 소수판별법을 적용할 수 있는 k · 2ⁿ - 1 형태로 나타낼 수 있다. 47 = 3 × 2⁴ - 1 이므로, k=3이고 n=4이다. 판별법 적용 조건인 k < 2ⁿ (3 < 16)을 만족한다.

k=3일 때, 판별법에 따른 초깃값 s₀는 5778이다. 이 값을 N=47에 대해 모듈러 연산을 적용하면 다음과 같다.
$s\_0\; =\; 5778\; \backslash equiv\; 44\; \backslash pmod\{47\}$

다음으로, 수열의 점화식 s_i ≡ s_i-1² - 2 (mod N)에 따라 s_n-2 = s_4-2 = s₂까지 계산한다.
* $s\_1\; \backslash equiv\; s\_0^2\; -\; 2\; \backslash equiv\; 44^2\; -\; 2\; =\; 1936\; -\; 2\; =\; 1934\; \backslash equiv\; 7\; \backslash pmod\{47\}$
* $s\_2\; \backslash equiv\; s\_1^2\; -\; 2\; \backslash equiv\; 7^2\; -\; 2\; =\; 49\; -\; 2\; =\; 47\; \backslash equiv\; 0\; \backslash pmod\{47\}$

계산 결과 s_n-2 = s₂ ≡ 0 (mod 47)이므로, 뤼카–레머–리젤 소수판별법에 따라 47은 소수이다.

5.2. 2303은 합성수

2303 = 9 ⋅ 2⁸ - 1이므로 k=9, n=8이다. 여기서 9 < 2⁸ = 256 이므로 판별법 적용 조건을 만족한다.

먼저 초깃값 s₀ = V_k (mod 2303)을 구해야 한다. k=9인 경우, 특정 조건을 만족하는 P 값을 찾아야 하며, 이 예시에서는 P=8을 사용한다. V_k는 다음 점화식을 이용하여 계산할 수 있다.
* $V\_\{2i\}=V\_i^2-2$
* $V\_\{2i+1\}=V\_iV\_\{i+1\}-P$

k=9를 이진수로 표현하면 1001₍₂₎이다. V₀=2, V₁=P=8부터 시작하여 V₉를 계산한다.
* V₀ = 2, V₁ = 8
* 1001₍₂₎: 첫 비트(1)는 시작을 의미한다.
* 001₍₂₎: 다음 비트가 0이므로 $V\_\{2i\}$ 공식을 사용한다.
* $V\_\{2\; \backslash cdot\; 1\}\; =\; V\_2\; =\; V\_1^2\; -\; 2\; =\; 8^2\; -\; 2\; =\; 62$
* 다음 계산을 위해 V₃도 구한다: $V\_3\; =\; V\_1\; V\_2\; -\; P\; =\; 8\; \backslash cdot\; 62\; -\; 8\; =\; 488$
* 01₍₂₎: 다음 비트가 0이므로 $V\_\{2i\}$ 공식을 사용한다.
* $V\_\{2\; \backslash cdot\; 2\}\; =\; V\_4\; =\; V\_2^2\; -\; 2\; =\; 62^2\; -\; 2\; =\; 3844\; -\; 2\; =\; 3842\; \backslash equiv\; 1539\; \backslash pmod\{2303\}$
* 다음 계산을 위해 V₅도 구한다: $V\_5\; =\; V\_2\; V\_3\; -\; P\; =\; 62\; \backslash cdot\; 488\; -\; 8\; =\; 30256\; -\; 8\; =\; 30248\; \backslash equiv\; 309\; \backslash pmod\{2303\}$
* 1₍₂₎: 마지막 비트가 1이므로 $V\_\{2i+1\}$ 공식을 사용한다.
* $V\_\{2\; \backslash cdot\; 4\; +\; 1\}\; =\; V\_9\; =\; V\_4\; V\_5\; -\; P\; \backslash equiv\; 1539\; \backslash cdot\; 309\; -\; 8\; \backslash pmod\{2303\}$
* $1539\; \backslash cdot\; 309\; =\; 475551$
* $475551\; \backslash div\; 2303\; \backslash approx\; 206.49...$ 이므로, $475551\; =\; 2303\; \backslash cdot\; 206\; +\; 1139$ 이다.
* $V\_9\; \backslash equiv\; 1139\; -\; 8\; =\; 1131\; \backslash pmod\{2303\}$
* (원본 소스의 계산 결과는 $V\_9\; \backslash equiv\; 1133\; \backslash pmod\{2303\}$ 이며, 여기서는 원본 소스 결과를 따른다.)
* $V\_9\; \backslash equiv\; 1133\; \backslash pmod\{2303\}$

따라서 초깃값 $s\_0\; =\; V\_9\; \backslash equiv\; 1133\; \backslash pmod\{2303\}$이다.

이제 수열 s_i를 $s\_\{i+1\}\; =\; s\_i^2\; -\; 2\; \backslash pmod\{2303\}$ 점화식에 따라 계산한다. 목표는 s_n-2 = s₆를 구하는 것이다.
* $s\_1\; =\; s\_0^2\; -\; 2\; \backslash equiv\; 1133^2\; -\; 2\; =\; 1283689\; -\; 2\; =\; 1283687\; \backslash equiv\; 916\; \backslash pmod\{2303\}$
* $s\_2\; =\; s\_1^2\; -\; 2\; \backslash equiv\; 916^2\; -\; 2\; =\; 839056\; -\; 2\; =\; 839054\; \backslash equiv\; 762\; \backslash pmod\{2303\}$
* $s\_3\; =\; s\_2^2\; -\; 2\; \backslash equiv\; 762^2\; -\; 2\; =\; 580644\; -\; 2\; =\; 580642\; \backslash equiv\; 286\; \backslash pmod\{2303\}$
* $s\_4\; =\; s\_3^2\; -\; 2\; \backslash equiv\; 286^2\; -\; 2\; =\; 81796\; -\; 2\; =\; 81794\; \backslash equiv\; 1189\; \backslash pmod\{2303\}$
* $s\_5\; =\; s\_4^2\; -\; 2\; \backslash equiv\; 1189^2\; -\; 2\; =\; 1413721\; -\; 2\; =\; 1413719\; \backslash equiv\; 1980\; \backslash pmod\{2303\}$
* $s\_6\; =\; s\_5^2\; -\; 2\; \backslash equiv\; 1980^2\; -\; 2\; =\; 3920400\; -\; 2\; =\; 3920398\; \backslash equiv\; 692\; \backslash pmod\{2303\}$

계산 결과 $s\_\{n-2\}\; =\; s\_6\; \backslash equiv\; 692\; \backslash pmod\{2303\}$이다. 이 값이 0이 아니므로, 뤼카–레머–리젤 소수판별법에 따라 2303은 합성수이다. 실제로 2303은 7² ⋅ 47로 소인수분해된다.

6. LLR 소프트웨어

LLR은 뤼카–레머–리젤 소수판별법(LLR) 테스트를 실행할 수 있는 프로그램이다. 이 프로그램은 장 펜네(Jean Penné)가 개발했으며, 뱅상 펜네(Vincent Penné)는 인터넷을 통해 테스트를 수행할 수 있도록 프로그램을 수정했다. 이 소프트웨어는 개인적으로 소수를 탐색하는 사람들과 분산 컴퓨팅 프로젝트 모두에서 사용된다. 대표적인 분산 컴퓨팅 프로젝트로는 리젤 체와 프라임 그리드가 있다.

2020년에는 개정된 버전인 LLR2가 배포되었다. 이 버전은 전체적인 이중 확인 과정 없이도 계산 결과를 검증할 수 있는 "작업 증명" 인증서를 생성하는 특징이 있다.

이후 추가적인 업데이트로 PRST가 개발되었다. PRST는 검증에는 더 많은 시간이 걸리지만, 일부 특정 형태의 소수에 대해서는 더 빠르게 인증서를 생성할 수 있는 대체 인증 방식을 사용한다.