뤼카-레머 소수판별법 문서 원본 보기

{{위키데이터 속성 추적}}
'''뤼카-레머 소수판별법'''은 [[메르센 수]]에 대한 [[소수판별법]]이다.

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

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

0 이상의 모든 i에 대한 수열 <math>S_i</math>는 다음과 같이 정의된다.

<math>s_0 = 4</math>,
<math>s_i = s_{i-1}^2 - 2</math>

이때, 첫 몇 개의 항은 4, 14, 194, 37634, ...이다.
{{OEIS|A003010}}
이때, 다음과 같은 관계식을 만족하는 것과 M<sub>p</sub>가 소수라는 것은 [[동치]]이다.
:<math>s_{p-2}\equiv0\pmod{M_p}</math>

이 때, ''s''<sub>''p''-2</sub> mod ''M''<sub>''p''</sub>를 '''뤼카-레머 나머지'''라고 한다.

== 예시 ==

=== <math>M_5=31</math>은 소수 ===
n=5인 경우, 뤼카-레머 소수판별법을 적용시켜 보면

<math>s_0=4</math>

<math>s_1={s_0}^2-2=4^2-2\equiv14 \pmod{31}</math>

<math>s_2={s_1}^2-2={14}^2-2\equiv8 \pmod{31}</math>

<math>s_3={s_2}^2-2=8^2-2\equiv0 \pmod{31}</math>

<math>s_{5-2}=s_3\equiv0\pmod{31}</math>이므로 <math>M_5=31</math>은 소수이다.
<br />

=== <math>M_{11}=2047</math>은 합성수 ===
n=11인 경우, 뤼카-레머 소수판별법을 적용시켜 보면

<math>      s_0=4</math>

<math>s_1={s_0}^2-2=4^2-2\equiv14 \pmod{2047}</math>

<math>s_2={s_1}^2-2={14}^2-2\equiv194 \pmod{2047}</math>

<math>s_3={s_2}^2-2={194}^2-2\equiv788 \pmod{2047}</math>

<math>s_4={s_3}^2-2={788}^2-2\equiv701\pmod{2047}</math>

<math>s_5={s_4}^2-2={701}^2-2\equiv119\pmod{2047}</math>

<math>s_6={s_5}^2-2={119}^2-2\equiv1877\pmod{2047}</math>

<math>s_7={s_6}^2-2={1877}^2-2\equiv240\pmod{2047}</math>

<math>s_8={s_7}^2-2={240}^2-2\equiv282\pmod{2047}</math>

<math>s_9={s_8}^2-2={282}^2-2\equiv1736\pmod{2047}</math>

<math>s_{11-2}=s_9\equiv1736\not\equiv0\pmod{2047}</math>이므로 <math>M_{11}=2047</math>은 합성수이다. 실제로 M<sub>11</sub>=2<sup>11</sup>-1=2047=23 ⋅ 89로 합성수이다.

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

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

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

[[분류:소수 판별법]]