뤼카 소수판정법

뤼카 소수판정법(Lucas primality test)은 자연수의 소수 여부를 확하는 정리로, 해당 수에서 1을 뺀 값의 소인수들을 모두 알고 있을 때 사용할 수 있다. 에두아르 뤼카가 정리를 세웠으며, 이의 파생된 정리로 포클링턴-레머 소수판정법이 있다.

진술

3 이상의 자연수[math]\displaystyle{ N }[/math]과 서로소인 [math]\displaystyle{ a }[/math]가 존재해서

(페르마의 소정리) [math]\displaystyle{ a^{N-1} \equiv 1 \pmod N }[/math]

을 만족하고, [math]\displaystyle{ N-1 }[/math]의 모든 소인수 [math]\displaystyle{ q }[/math]에 대해

[math]\displaystyle{ a^{\frac{N-1}{q}} \not \equiv 1 \pmod N }[/math]

이면 주어진 자연수는 소수이다.

만약 어떤 [math]\displaystyle{ a }[/math]에 대해 첫째 조건을 만족하지 않거나, 둘째 조건을 만족하는 [math]\displaystyle{ a }[/math]가 존재하지 않는다면 [math]\displaystyle{ N }[/math]은 합성수이다.

증명

필요조건

[math]\displaystyle{ N }[/math]이 소수이면 이에 해당하는 원시근 [math]\displaystyle{ a }[/math]를 찾을 수 있으며, 이때 위수는 [math]\displaystyle{ \operatorname{ord}_N a = N-1 }[/math]이다.

다시 말해 진술의 첫째 식을 만족하며, 덤으로 [math]\displaystyle{ 1\lt q, \frac{N-1}{q} \lt N-1 }[/math]인 모든 소인수 [math]\displaystyle{ q }[/math]에 대해 둘째 식도 만족하게 된다.

충분조건

해당 두 조건식을 만족하면 [math]\displaystyle{ N }[/math]이 소수가 됨을 보인다.

먼저 첫째 식이 맞다고 하면, [math]\displaystyle{ a }[/math]의 위수는 [math]\displaystyle{ \lambda = \operatorname{ord}_N a \mid N-1 }[/math]을 만족한다. 만약 [math]\displaystyle{ N }[/math]이 합성수라면, 오일러의 정리의 합동식인 [math]\displaystyle{ a^{\phi(N)} \equiv 1 \pmod N }[/math]도 성립한다. 이때 [math]\displaystyle{ \lambda \mid \phi(N) \lt N-1 }[/math]이므로 [math]\displaystyle{ N-1=k\lambda, k \geq 2 }[/math]인 자연수 [math]\displaystyle{ k }[/math]가 존재한다.

이제 [math]\displaystyle{ q \mid k, k=qr }[/math]인 소인수를 불러오면 [math]\displaystyle{ N-1=qr\lambda, \lambda \mid \frac{N-1}{q} }[/math]이므로 [math]\displaystyle{ a^{\frac{N-1}{q}} \equiv 1 \pmod N }[/math]이다.

하지만 이는 진술의 가정 중 둘째 조건과 모순이다. 그러므로 [math]\displaystyle{ N }[/math]은 소수이다.

적용 예

[math]\displaystyle{ N=20^4+1=160001 }[/math]은 소수인가? 이 자연수는 뤼카 소수판정법을 적용하기 아주 좋은 예이다.

[math]\displaystyle{ N-1=2^8 \cdot 5^4 }[/math]으로, 소인수는 2와 5 둘 뿐이다. 그러므로 확인해볼 지수는 [math]\displaystyle{ N-1, \frac{N-1}{2}, \frac{N-1}{5} }[/math] 즉 160000, 80000, 32000 세 종류다.

[math]\displaystyle{ a=3 }[/math]으로 놓고 합동식을 확인한다. 먼저 [math]\displaystyle{ 3^{160000} \equiv 1 \pmod N }[/math]이므로 첫째 조건은 통과다.

그 다음 [math]\displaystyle{ 3^{80000} \equiv -1, 3^{32000} \equiv 94120 \pmod N }[/math]이므로 둘째 조건 역시 통과한다. 따라서 주어진 자연수는 소수이다.

기타

소수 여부를 확인하려는 자연수는 언제나 홀수이다. [math]\displaystyle{ N-1 }[/math]은 짝수이므로, 만약 소인수가 단 한 가지라면 그 소인수는 2이며 [math]\displaystyle{ N=2^k+1 }[/math]꼴이 된다. 이것이 소수이기 위한 필요조건으로 지수는 2의 거듭제곱이어야 한다. 즉 [math]\displaystyle{ N=2^{2^n}+1 }[/math] 꼴이 되고, 이는 페르마 수와 같다. 위의 정리를 적용하면 [math]\displaystyle{ a^{N-1}, a^{\frac{N-1}{2}} \mod N }[/math]만 확인하면 된다. 그리고 이 조건을 적절히 다듬으면 페팽 소수판정법이 된다.