뤼카-레머 소수판별법

뤼카-레머 소수판별법은 메르센 수에 대한 소수판별법이다.

역사

에두아르 뤼카(Édouard Lucas)의 원래 알고리즘을 데릭 레머(Derrick Henry Lehmer)가 개량하였다.

판정 방법

메르센 수 M_p = 2^p − 1를 생각하자. 이때, p는 홀수 소수로 한다 (만약 p가 소수가 아닐 경우, M_p는 자명한 약수를 가진다. 그리고 이 판정법은 p = 2일 때에는 성립하지 않는다).

0 이상의 모든 i에 대한 수열 $S_{i}$는 다음과 같이 정의된다.

$s_{0}=4$, $s_{i}=s_{i-1}^{2}-2$

이때, 첫 몇 개의 항은 4, 14, 194, 37634, ...이다. (OEIS의 수열 A003010) 이때, 다음과 같은 관계식을 만족하는 것과 M_p가 소수라는 것은 동치이다.

$s_{p-2}\equiv 0{\pmod {M_{p}}}$

이 때, s_p-2 mod M_p를 뤼카-레머 나머지라고 한다.

예시

$M_{5}=31$은 소수

n=5인 경우, 뤼카-레머 소수판별법을 적용시켜 보면

$s_{0}=4$

$s_{1}={s_{0}}^{2}-2=4^{2}-2\equiv 14{\pmod {31}}$

$s_{2}={s_{1}}^{2}-2={14}^{2}-2\equiv 8{\pmod {31}}$

$s_{3}={s_{2}}^{2}-2=8^{2}-2\equiv 0{\pmod {31}}$

$s_{5-2}=s_{3}\equiv 0{\pmod {31}}$이므로 $M_{5}=31$은 소수이다.

$M_{11}=2047$은 합성수

n=11인 경우, 뤼카-레머 소수판별법을 적용시켜 보면

$s_{0}=4$

$s_{1}={s_{0}}^{2}-2=4^{2}-2\equiv 14{\pmod {2047}}$

$s_{2}={s_{1}}^{2}-2={14}^{2}-2\equiv 194{\pmod {2047}}$

$s_{3}={s_{2}}^{2}-2={194}^{2}-2\equiv 788{\pmod {2047}}$

$s_{4}={s_{3}}^{2}-2={788}^{2}-2\equiv 701{\pmod {2047}}$

$s_{5}={s_{4}}^{2}-2={701}^{2}-2\equiv 119{\pmod {2047}}$

$s_{6}={s_{5}}^{2}-2={119}^{2}-2\equiv 1877{\pmod {2047}}$

$s_{7}={s_{6}}^{2}-2={1877}^{2}-2\equiv 240{\pmod {2047}}$

$s_{8}={s_{7}}^{2}-2={240}^{2}-2\equiv 282{\pmod {2047}}$

$s_{9}={s_{8}}^{2}-2={282}^{2}-2\equiv 1736{\pmod {2047}}$

$s_{11-2}=s_{9}\equiv 1736\not \equiv 0{\pmod {2047}}$이므로 $M_{11}=2047$은 합성수이다. 실제로 M₁₁=2¹¹-1=2047=23 ⋅ 89로 합성수이다.

이용

뤼카-레머 소수판별법은 Prime95에 사용되며, 대부분의 메르센 소수들은 뤼카-레머 소수판별법으로 인해 알려지게 되었다.

같이 보기

뤼카-레머-리젤 소수판별법: 뤼카-레머 소수판별법과 비슷하지만 초깃값을 다르게 함으로써 더 많은 수들에 대해 적용할 수 있게 개량한 소수판별법이다.

페팽 소수판별법: 뤼카-레머 소수판별법은 2^p − 1 꼴의 수들에 대해 적용할 수 있는 소수판별법이고, 페팽 소수판별법은 2^{2^n}+1 꼴의 수에 대해서 적용할 수 있는 소 수판별법이다.