뤼카-레머-리젤 소수판정법

뤼카-레머-리젤 소수판정법(Lucas-Lehmer-Riesel primality test)은 [math]\displaystyle{ N=k\cdot 2^n-1, k\lt 2^n }[/math] 형태의 자연수의 소수 여부를 알아내는 소수판정법이다. 뤼카-레머 소수판정법의 확장판으로, 해당 판정법을 메르센 수에서 범위를 넓힌 것이다. 한스 리젤(Hans Riesel)이 기존 뤼카-레머 방식을 개량하였다.

진술

이 소수판정법에서는 일반화된 뤼카 수열 중 [math]\displaystyle{ V_n(P, 1) }[/math]을 이용한다. 이 수열은 [math]\displaystyle{ V_0=2, V_1=P, V_n=PV_{n-1}-V_{n-2} }[/math]로 정의되며, 본 문서에서는 초기 조건을 어떻게 결정하는 지에 초점을 둔다.

소수 여부를 알아볼 자연수 [math]\displaystyle{ N=k\cdot 2^n-1 }[/math]이 주어지고 [math]\displaystyle{ k }[/math]는 [math]\displaystyle{ 2^n }[/math]보다 작은 홀수이다. 상수 [math]\displaystyle{ P }[/math]는 야코비 기호의 조건으로 [math]\displaystyle{ \left(\frac{P-2}{N} \right)=1, \left(\frac{P+2}{N} \right)=-1 }[/math]을 만족한다. 그 다음 알고리즘에 사용할 수열을 정의한다.

[math]\displaystyle{ r_m=\begin{cases}V_k &\text{if } m=1 \\ r_{m-1}^2-2 &\text{otherwise} \end{cases} }[/math]

이때 [math]\displaystyle{ r_{n-1} \equiv 0 \pmod N }[/math]이면 [math]\displaystyle{ N }[/math]은 소수이고, 그렇지 않으면 합성수이다.

증명

진술과 증명 과정은 다루는 값만 다를 뿐 뤼카-레머 소수판정법과 아주 흡사하다.

먼저 뤼카 수열의 항은 [math]\displaystyle{ V_n(P, 1)=a^n+a^{-n}, a=\frac{P+\sqrt{P^2-4}}{2} }[/math]와 같이 풀 수 있다. 아울러 [math]\displaystyle{ r_1=a^k+a^{-k} }[/math]이고, 진술의 점화관계식을 풀면 [math]\displaystyle{ r_m=a^{2^{m-1}k}+a^{-2^{m-1}k} }[/math]이다. 즉 진술의 합동식에 대입하면 [math]\displaystyle{ a^{2^{n-2}k}+a^{-2^{n-2}k} \equiv 0 \pmod N }[/math](☆)이다.

필요조건

아래 모든 연산은 환 [math]\displaystyle{ X=\{a+b\sqrt{D}|a,b \in \mathbb{Z}/N\mathbb{Z} \} (D=P^2-4) }[/math] 내에서 이루어진다. 즉 [math]\displaystyle{ a+b\sqrt{D} \equiv c+d\sqrt{D} \pmod N }[/math]은 [math]\displaystyle{ a \equiv c, b \equiv d \pmod N }[/math]를 의미한다.

[math]\displaystyle{ N }[/math]이 소수라 가정하고 (☆) 합동식을 이끌어낸다. 진술에서 쓴 야코비 기호는 르장드르 기호가 되며, 오일러의 규준에 의해 [math]\displaystyle{ (P-2)^{\frac{N-1}{2}} \equiv 1, (P+2)^{\frac{N-1}{2}} \equiv -1 \pmod N }[/math]이다.

위 문단의 식을 불러오면 [math]\displaystyle{ 4a=2P+2\sqrt{P^2-4}=(\sqrt{P+2}+\sqrt{P-2})^2 }[/math]이다. 이 식의 양 변을 [math]\displaystyle{ \frac{N+1}{2} }[/math]제곱하면 [math]\displaystyle{ 2^{N+1}a^{\frac{N+1}{2}}=(\sqrt{P+2}+\sqrt{P-2})^{N+1} }[/math]이고, 각 항은 아래와 같이 정리된다.

[math]\displaystyle{ a^{\frac{N+1}{2}}=a^{2^{n-1}k} }[/math]

[math]\displaystyle{ 2^{N+1}=2^{N-1}\cdot 4 \equiv 4 \pmod N }[/math] ←페르마의 소정리

[math]\displaystyle{ (\sqrt{P-2}+\sqrt{P+2})^{N+1}=(\sqrt{P-2}+\sqrt{P+2})^N (\sqrt{P-2}+\sqrt{P+2}) }[/math]

[math]\displaystyle{ (\sqrt{P-2}+\sqrt{P+2})^N=\sum_{j=0}^{N}\binom{N}{j}(\sqrt{P+2})^{j}(\sqrt{P-2})^{N-j} \equiv (\sqrt{P+2})^N+(\sqrt{P-2})^N \pmod N }[/math]

[math]\displaystyle{ (\sqrt{P-2})^N=(P-2)^{\frac{N-1}{2}}\sqrt{P-2} \equiv \sqrt{P-2} \pmod N }[/math]

[math]\displaystyle{ (\sqrt{P+2})^N=(P+2)^{\frac{N-1}{2}}\sqrt{P+2} \equiv -\sqrt{P+2} \pmod N }[/math]

[math]\displaystyle{ (\sqrt{P-2}+\sqrt{P+2})^N \equiv \sqrt{P-2}-\sqrt{P+2} \pmod N }[/math]

[math]\displaystyle{ (\sqrt{P-2}+\sqrt{P+2})^{N+1} \equiv (\sqrt{P-2}+\sqrt{P+2})(\sqrt{P-2}-\sqrt{P+2}) \equiv -4 \pmod N }[/math]

이상 정리된 항들을 원래 식에 대입하면 [math]\displaystyle{ 4a^{2^{n-1}k} \equiv -4 \pmod N }[/math]이다. 양 변을 4로 나누고 [math]\displaystyle{ a^{-2^{n-2}k} }[/math]을 곱하면 [math]\displaystyle{ a^{2^{n-2}k} \equiv -a^{-2^{n-2}k} \pmod N }[/math]이며, 우변을 이항하면 유도하고자 하는 (☆) 합동식이 성립함을 알 수 있다.

충분조건

(☆) 합동식이 성립한다고 가정하고, [math]\displaystyle{ N }[/math]이 소수임을 이끌어낸다.

만약 홀수 [math]\displaystyle{ N }[/math]이 소수가 아니면 [math]\displaystyle{ q \mid N, q(q+2) \leq N }[/math]인 홀수 소인수 [math]\displaystyle{ q }[/math]가 존재한다.

(☆) 합동식을 변형하면 [math]\displaystyle{ a^{2^{n-1}k} \equiv -1 \pmod q }[/math]이다. [math]\displaystyle{ q }[/math]가 원래 수의 약수이므로 합동식의 법을 이렇게 바꿔 쓸 수 있다. 양 변을 제곱하면 [math]\displaystyle{ a^{2^n k} \equiv 1 \pmod q }[/math]이다.

[math]\displaystyle{ \lambda }[/math]를 [math]\displaystyle{ a^{\lambda} \equiv 1 \pmod q }[/math]를 만족하는 최소 차수라고 하면 [math]\displaystyle{ \lambda \mid 2^n k, \lambda \nmid 2^{n-1}k }[/math]이어야 하므로 [math]\displaystyle{ \lambda=2^n k' }[/math]이다. 단, [math]\displaystyle{ k' \mid k }[/math]

한편 [math]\displaystyle{ 2a=P+\sqrt{P^2-4} }[/math]의 양 변을 [math]\displaystyle{ q }[/math]제곱하면 [math]\displaystyle{ (2a)^q \equiv P^q+(P^2-4)^{\frac{q-1}{2}}\sqrt{P^2-4} \pmod q }[/math]이다. 우변의 경우, 진술에서 쓴 야코비 기호 값은 [math]\displaystyle{ P-2, P+2 \nmid N }[/math]을 뜻하고, 이에 따라 [math]\displaystyle{ P^2-4 \nmid q, \left(\frac{P^2-4}{q} \right)= \pm 1 }[/math]을 알 수 있다.

또한 페르마의 소정리에 의해 [math]\displaystyle{ 2^q \equiv 2, P^q \equiv P \pmod q }[/math]이고, 위 식을 정리하면 [math]\displaystyle{ 2a^q \equiv P \pm \sqrt{P^2-4} \pmod q }[/math]이다. 합동식의 우변은 [math]\displaystyle{ 2a^{\pm 1} }[/math]과 같으므로, [math]\displaystyle{ a^{q-1} \equiv 1 \pmod q }[/math] 또는 [math]\displaystyle{ a^{q+1} \equiv 1 \pmod q }[/math]이다.

따라서 [math]\displaystyle{ \lambda \mid q-1 }[/math] 또는 [math]\displaystyle{ \lambda \mid q+1 }[/math]이므로 [math]\displaystyle{ \lambda=2^n k' \leq q+1 }[/math]이며, [math]\displaystyle{ q \geq 2^n k'-1 \geq 2^n-1, q+2 \geq 2^n+1 }[/math]이다.

두 부등식을 곱하면 [math]\displaystyle{ q(q+2) \geq (2^n)^2-1 }[/math]이다. 또, 처음 가정인 [math]\displaystyle{ k\lt 2^n }[/math]을 불러오면 [math]\displaystyle{ q(q+2)\gt k \cdot 2^n-1=N }[/math]이다.

하지만 이는 앞서 가정했던 [math]\displaystyle{ q(q+2) \leq N }[/math]과 모순이다. 그러므로 [math]\displaystyle{ N }[/math]은 소수이다.

참고로 [math]\displaystyle{ k\lt 2^n }[/math]이라는 특수한 조건은 프로트의 정리에서도 귀류법으로 증명할 때 쓰인다.

초깃값 구하기

이번에는 진술에서 언급한 식인 [math]\displaystyle{ \left(\frac{P-2}{N} \right)=1, \left(\frac{P+2}{N} \right)=-1 }[/math]을 만족하는 [math]\displaystyle{ P }[/math]와 초깃값 [math]\displaystyle{ r_1=V_k(P, 1) }[/math]을 구할 차례이다.

[math]\displaystyle{ n=1 }[/math]인 경우 [math]\displaystyle{ k\lt 2^n }[/math]으로부터 [math]\displaystyle{ k=1, N=1 }[/math]만 가능하며 이는 관심의 대상이 아니다. 그러므로 [math]\displaystyle{ n \geq 2 }[/math]라는 전제를 깔고, 그러면 [math]\displaystyle{ N \equiv 3 \pmod 4 }[/math]가 된다. 즉 [math]\displaystyle{ N }[/math]은 제곱수가 아니다.

• [math]\displaystyle{ 3 \nmid k }[/math]인 경우, [math]\displaystyle{ N \equiv 0 \text{ or }1 \pmod 3 }[/math]이다. 3의 배수는 3을 제외하고 모두 합성수이므로, 3으로 나눈 나머지가 1인 경우만을 생각한다. 이 경우 [math]\displaystyle{ P=4 }[/math]로 두면 된다.
  • [math]\displaystyle{ k=1 }[/math]이면 [math]\displaystyle{ N=2^n-1 }[/math]로 메르센 수가 된다. 그리고 이 값을 3으로 나눈 나머지가 1이라면 [math]\displaystyle{ n }[/math]은 홀수이므로 [math]\displaystyle{ n \geq 3 }[/math]이며, [math]\displaystyle{ N \equiv 7 \pmod 8, N \equiv 7 \pmod{24} }[/math]가 되어 [math]\displaystyle{ \left(\frac{2}{N} \right)=1, \left(\frac{6}{N} \right)=-1 }[/math]을 만족한다. 또, [math]\displaystyle{ r_1=V_1(4, 1)=4 }[/math]이며, 이는 곧 뤼카-레머 소수판정법이 된다.
  • [math]\displaystyle{ k \geq 5 }[/math]이면 [math]\displaystyle{ 2^n\gt 5, n \geq 3 }[/math]이므로 바로 위와 똑같이 야코비 기호의 조건을 만족한다. 초깃값은 [math]\displaystyle{ r_1=V_k(4, 1)=(2+\sqrt{3})^k+(2-\sqrt{3})^k }[/math]
• [math]\displaystyle{ k=3 }[/math]인 경우, [math]\displaystyle{ n \equiv 1 \pmod 4 }[/math]이면 [math]\displaystyle{ 2^n \equiv 2 \pmod 5 }[/math]이므로 [math]\displaystyle{ N \equiv 0 \pmod 5 }[/math]이다. 즉 5를 제외하고 모두 합성수이므로, 관심의 대상이 아니다. [math]\displaystyle{ n \equiv 0 \text{ or }3 \pmod 4 }[/math]이면 마찬가지 방법으로 [math]\displaystyle{ N \equiv 2 \text{ or }3 \pmod 5 }[/math]이므로 야코비 기호의 값은 [math]\displaystyle{ \left(\frac{5}{N} \right)=\left(\frac{20}{N} \right)=-1 }[/math]이다. 또, 16은 제곱수이므로 [math]\displaystyle{ \left(\frac{16}{N} \right)=1 }[/math]인데, 두 식을 토대로 [math]\displaystyle{ P=18, r_1=V_3(18, 1)=5778 }[/math]로 두면 된다.
• 그 밖에 [math]\displaystyle{ k\gt 3 }[/math]이거나 [math]\displaystyle{ k=3, n \equiv 2 \pmod 4 }[/math]이면 [math]\displaystyle{ P }[/math]와 그에 대응하는 야코비 기호 식은 또다른 값을 가진다.

기타

이 소수판정법은 큰 쌍둥이 소수를 찾는 데 유용하다. 즉 [math]\displaystyle{ N=k \cdot 2^n \pm 1, k\lt 2^n }[/math]의 형태에서, (+) 부호는 프로트의 정리로, (-)부호는 본 문서의 알고리즘으로 소수 여부를 규명해낸다. 그렇게 해서 두 수 모두 소수가 맞으면 쌍둥이 소수가 된다.