뤼카-레머 소수판별법

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

역사

에두아르 뤼카(É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(\mathrm{mod}{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(\mathrm{mod}31)$

$s_2={s_1}^2-2={14}^2-2\equiv 8(\mathrm{mod}31)$

$s_3={s_2}^2-2=8^2-2\equiv 0(\mathrm{mod}31)$

$s_{5-2}=s_3\equiv 0(\mathrm{mod}31)$이므로 $M_5=31$은 소수이다.

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

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

$s_0=4$

$s_1={s_0}^2-2=4^2-2\equiv 14(\mathrm{mod}2047)$

$s_2={s_1}^2-2={14}^2-2\equiv 194(\mathrm{mod}2047)$

$s_3={s_2}^2-2={194}^2-2\equiv 788(\mathrm{mod}2047)$

$s_4={s_3}^2-2={788}^2-2\equiv 701(\mathrm{mod}2047)$

$s_5={s_4}^2-2={701}^2-2\equiv 119(\mathrm{mod}2047)$

$s_6={s_5}^2-2={119}^2-2\equiv 1877(\mathrm{mod}2047)$

$s_7={s_6}^2-2={1877}^2-2\equiv 240(\mathrm{mod}2047)$

$s_8={s_7}^2-2={240}^2-2\equiv 282(\mathrm{mod}2047)$

$s_9={s_8}^2-2={282}^2-2\equiv 1736(\mathrm{mod}2047)$

$s_{11-2}=s_9\equiv 1736\equiv ̸0(\mathrm{mod}2047)$이므로 $M_{11}=2047$은 합성수이다. 실제로 M₁₁=2¹¹-1=2047=23 ⋅ 89로 합성수이다.

이용

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

같이 보기

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

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