포클링턴-레머 소수판정법

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

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

기본 정리: 특수한 경우

아래 정리는 소수판정법의 기본형이다.

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

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

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

증명

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

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

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

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

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

예시

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

위 정리에 등장한 변수를 불러온다: [math]\displaystyle{ N-1=2 \cdot 1381973, p=1381973 }[/math]

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

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

한계점

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

발전된 정리: 범위 확장

[math]\displaystyle{ N-1=AB, \gcd(A, B)=1, A \gt \sqrt{N}-1 }[/math]인 자연수 [math]\displaystyle{ A, B }[/math]가 있다. (두 수는 소수일 필요가 없다) [math]\displaystyle{ p_i \mid A }[/math]인 모든 소인수 [math]\displaystyle{ p_i }[/math]에 대해 아래 두 조건을 만족하는 [math]\displaystyle{ a_i }[/math]가 존재하면 [math]\displaystyle{ N }[/math]은 소수이다.

• [math]\displaystyle{ a_i^{N-1} \equiv 1 \pmod N }[/math]
• [math]\displaystyle{ \gcd(a_i^{s_i}-1, N) = 1, s_i=\frac{N-1}{p_i} }[/math]

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

증명

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

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

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

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

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

예시

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

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

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

따라서 [math]\displaystyle{ n }[/math]은 소수임을 알 수 있다.

같이 보기

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