포클링턴-레머 소수판정법 편집하기

'''포클링턴-레머 소수판정법'''(Pocklington–Lehmer primality test)은 자연수의 [[소수 (정수)|소수]] 여부를 가려내는 방법으로, 헨리 포클링턴(Henry Cabourn Pocklington)과 데릭 레머(Derrick Henry Lehmer)가 정립하였다.

[[뤼카 소수판정법]]과 마찬가지로 어떤 자연수에서 1을 뺀 수의 소인수를 이용하나, 이쪽은 모든 소인수 대신 일부만을 이용한다. 또한 이 정리에는 기본형과 발전형이 있다.

== 기본 정리: 특수한 경우 ==
아래 정리는 소수판정법의 기본형이다.

자연수 <math>N</math>이 주어져 있고 <math>N-1</math>의 가장 큰 소인수 <math>p</math>가 있다. 이 소인수와 서로소인 <math>a</math>가 존재해서 아래 조건을 모두 만족하면 <math>N</math>은 소수이다.

* [[페르마의 소정리]]: <math>a^{N-1} \equiv 1 \pmod N</math>
* <math>p \mid N-1, p > \sqrt{N}-1</math>
* <math>\gcd(a^s-1, N) = 1, s=\frac{N-1}{p}</math>

첫째 조건을 만족하지 못하면 해당 자연수는 합성수이다. 첫째 식을 만족한다는 걸 확인하고, <math>N-1</math>의 가장 큰 소인수가 이 수의 제곱근보다 크면 셋째 조건을 만족하는 <math>a</math>를 찾는다.

=== 증명 ===
[[귀류법]]을 이용한다. <math>N</math>이 소수가 아니라면 <math>q \mid N, q \leq \sqrt{N}</math>인 소인수 <math>q</math>가 존재한다.

가정에 따라 <math>q-1 \leq \sqrt{N}-1 < p</math>이므로 <math>1 \leq q-1 < p</math>이고, <math>p</math>는 소수이므로 <math>p, q-1</math>은 서로소이다. 그러므로 합동식 <math>rp \equiv 1 \pmod{q-1}</math>을 만족하는 모듈러 역수 <math>r</math>이 반드시 존재하고, <math>q-1 \mid rp-1</math>이다.

페르마의 소정리에 의해 <math>a^{q-1} \equiv 1 \Rightarrow a^{rp} \equiv a \pmod q</math>이다.

한편 위 진술의 첫째 조건인 <math>a^{N-1} \equiv 1 \pmod N</math>에서 <math>q \mid N</math>이므로 <math>a^{N-1} \equiv 1 \Rightarrow a^{r(N-1)} \equiv 1 \pmod q</math>도 성립한다. 한편 <math>N-1=sp</math>을 대입하면 <math>a^{r(N-1)} \equiv a^{rsp} \equiv (a^{rp})^s \equiv a^s \equiv 1 \pmod q</math>이다.

그런데 <math>s=\frac{N-1}{p}</math>이므로 <math>q \mid a^{\frac{N-1}{p}}-1</math>이 된다. 그러면 <math>\gcd(a^{\frac{N-1}{p}}-1, N)</math>은 <math>q</math>를 약수로 가지며 1이 아니게 된다. 이는 위 진술의 셋째 조건과 모순이다. 따라서 <math>N</math>은 소수이다.

=== 예시 ===
<math>n=1381973</math>이 소수라는 사실을 안다고 할 때, <math>N=2n+1=2763947</math>도 소수인지 알아보려고 한다. (즉 <math>n</math>이 [[소피 제르맹 소수]]인지를 알아본다)

위 정리에 등장한 변수를 불러온다: <math>N-1=2 \cdot 1381973, p=1381973</math>

* <math>a=2</math>라 하면 <math>a^{N-1} \equiv 1 \pmod N</math>이 성립하므로 첫째 조건은 통과다.
* <math>p > \sqrt{N}-1</math>이므로 둘째 조건도 통과
* <math>s=\frac{N-1}{p}=2, a^s=2^2=4, \gcd(a^s-1, N)=1</math>이므로 셋째 조건도 통과

따라서 <math>N</math>은 소수임을 알 수 있다. 일반적으로 <math>n</math>이 소수이고 <math>2^{2n} \equiv 1 \pmod{2n+1}</math>이면 같은 방법으로 <math>2n+1</math>도 소수이다.

=== 한계점 ===
위 정리는 <math>N-1</math>의 가장 큰 소인수가 <math>\sqrt{N}-1</math>보다 큰 경우에만 쓸 수 있다. 하지만 모든 소인수가 원래 수의 제곱근보다 작은 경우도 상당수 존재하는데, 이 때에는 아래 발전된 정리를 이용해야 한다.

== 발전된 정리: 범위 확장 ==
<math>N-1=AB, \gcd(A, B)=1, A > \sqrt{N}-1</math>인 자연수 <math>A, B</math>가 있다. (두 수는 소수일 필요가 없다) <math>p_i \mid A</math>인 모든 소인수 <math>p_i</math>에 대해 아래 두 조건을 만족하는 <math>a_i</math>가 존재하면 <math>N</math>은 소수이다.

* <math>a_i^{N-1} \equiv 1 \pmod N</math>
* <math>\gcd(a_i^{s_i}-1, N) = 1, s_i=\frac{N-1}{p_i}</math>

이때 <math>a_i</math>는 각 소인수<math>p_i</math>에 대응하는 밑으로, 일정한 값일 필요는 없다. 즉 <math>p_i, p_j \mid A</math>일 때 <math>a_i=a_j</math>일 필요는 없다.

=== 증명 ===
마찬가지로 귀류법을 이용한다. <math>N</math>이 소수가 아니면 <math>q \mid N, q \leq \sqrt{N}</math>인 소인수 <math>q</math>가 존재한다.

그 다음 <math>p \mid A (N-1=AB)</math>인 소인수에 대해 <math>p^m \mid A, p^{m+1}\nmid A</math>인 지수 <math>m</math>이 존재한다. 그 다음 해당 소인수에 대응하는 <math>a</math>에 대해 <math>t=\frac{N-1}{p^m}, b \equiv a^t \pmod q</math>를 지정한다. 그러면 <math>b^{p^m} \equiv a^{N-1} \pmod q</math>이고 가정의 첫째 조건에 의해 <math>b^{p^m} \equiv 1 \pmod q</math>이다.

둘째 조건의 가정에서 <math>\gcd(a^s, N)=1, s=tp^{m-1}</math>이므로 <math>b^{p^{m-1}} \equiv a^{tp^{m-1}} \equiv a_1^s \not \equiv 1 \pmod N</math>, 즉 <math>b^{p^{m-1}} \not \equiv 1 \pmod q</math>이다. 따라서 <math>\operatorname{ord}_q b=p^m</math>이고, <math>q</math>는 소수이므로 <math>p^m \mid q-1</math>이다.

<math>A=\prod_i p_i^{m_i}</math> 꼴로 소인수분해가 될 때, 위 논리에 따라 모든 소인수 <math>p_i</math>에 대해 <math>p_i^{m_i} \mid q-1</math>이 성립하며, <math>A \mid q-1 \Rightarrow A \leq q-1 \leq \sqrt{N}-1</math>임을 알 수 있다.

하지만 이는 가정인 <math>A > \sqrt{N}-1</math>과 모순이다. 따라서 <math>N</math>은 소수이다.

=== 예시 ===
앞서 언급한 <math>n=1381973</math>의 경우 <math>n-1=2^2 \cdot 439 \cdot 787</math>이기에 위 기본 정리를 적용할 수 없었다. 이 경우 발전된 정리를 이용하여 소수 여부를 확인한다.

<math>A=2^2 \cdot 787, B=439</math>라 하면 <math>\gcd(A, B)=1, A>\sqrt{n}-1</math>이고, <math>A</math>의 소인수로 2와 787이 있다.

#<math>p_1=2</math>: <math>a_1=2</math>라 하면 <math>a_1^{n-1} \equiv 1 \pmod n</math>(ⓐ)을 만족한다. 또한 <math>s_1=\frac{n-1}{p_1}=690986, a_1^{s_1} \equiv -1 \pmod n</math>이 되어 <math>\gcd(a_1^{s_1}-1, n)=1</math>이다.
#<math>p_2=787</math>: <math>a_2=2</math>라 하면 첫째 조건은 위의 (ⓐ)식 그대로 나온다. 이어서 <math>s_2=\frac{n-1}{p_2}=1756, a_2^{s_2} \equiv 152935 \pmod n</math>이므로 <math>\gcd(a_2^{s_2}-1, n)=1</math>이다.

따라서 <math>n</math>은 소수임을 알 수 있다.

== 같이 보기 ==
* [[뤼카 소수판정법]]
* [[타원곡선 소수판정법]]: 이 판정법은 위 소수판정법의 기본 정리를 거듭제곱 대신 [[타원곡선]] 버전으로 옮긴 정리라 할 수 있다.

{{각주}}
{{수론 알고리즘}}
[[분류:알고리즘]]