맨위로가기

뤼카-레머 소수판별법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

뤼카-레머 소수 판별법은 에두아르 뤼카의 알고리즘을 데릭 레머가 개량한 것으로, 메르센 소수인지 판별하는 방법이다. 이 판별법은 메르센 수 Mp = 2p − 1 (p는 홀수 소수)에 대해 수열 si = si-12 − 2 (s0 = 4)를 정의하고, sp-2 mod Mp가 0과 동치일 때 Mp가 소수임을 판별한다. 뤼카-레머 소수 판별법은 Prime95와 GIMPS에서 사용되며, 메르센 소수를 찾는 데 기여했다.

더 읽어볼만한 페이지

  • 소수 판별법 - 에라토스테네스의 체
    에라토스테네스의 체는 주어진 범위에서 소수를 효율적으로 찾는 알고리즘으로, 특정 구간 내의 모든 수를 나열한 후 가장 작은 소수의 배수들을 제거하는 과정을 반복하여 소수만을 남기는 방식으로 작동하며, 다양한 변형과 최적화 기법이 존재하고, O(n \log \log n)의 시간 복잡도를 가진다.
  • 소수 판별법 - 밀러-라빈 소수판별법
    밀러-라빈 소수판별법은 페르마 소정리를 기반으로 주어진 수가 소수인지 판별하는 확률적 알고리즘으로, 합성수를 소수로 잘못 판별할 가능성이 있지만 검사를 반복할수록 정확도가 높아지며, 일반화 리만 가설이 참일 경우 결정론적 알고리즘으로 전환될 수 있다.
뤼카-레머 소수판별법

2. 역사

에두아르 뤼카의 원래 알고리즘을 데릭 레머가 개량하였다.

3. 판정 방법

메르센 수 Mp = 2p − 1 (이때 p는 홀수 소수)가 소수인지 판별하는 방법이다. 만약 p가 합성수라면 Mp는 자명한 약수를 가지므로 소수가 아니며, p = 2일 때는 이 판정법이 적용되지 않는다.

뤼카-레머 소수판별법은 다음과 같은 수열 \{s_i\}를 이용한다.

:

s_i=

\begin{cases}

4 & \text{if }i=0;

\\

s_{i-1}^2-2 & \text{if }i \ge 1.

\end{cases}



이 수열의 첫 항들은 4, 14, 194, 37634, ... 와 같다. (OEIS A003010)

이 수열을 이용하여 메르센 수 Mp의 소수 여부를 판정하는 조건은 다음과 같다.

:s_{p-2}\equiv0\pmod{M_p}

즉, 수열의 (p-1)번째 항인 sp-2를 Mp로 나누었을 때 나머지가 0이면 Mp는 소수이고, 그렇지 않으면 합성수이다. 이때 계산되는 값 s_{p-2} \pmod{M_p}를 '''뤼카-레머 나머지'''라고 부른다.

알고리즘은 다음과 같이 의사 코드로 표현할 수 있다.



// ''M''''p'' = 2''p'' − 1이 ''p'' > 2인 소수에 대해 소수인지 확인

'''Lucas–Lehmer'''(p)

    '''var''' s = 4

    '''var''' M = 2''p'' − 1

    '''repeat''' p − 2 times:

        s = ((s × s) − 2) mod M

    '''if''' s == 0 '''return''' 소수

    '''else''' '''return''' 합성수



계산 과정에서 각 반복마다 mod M 연산을 수행하는 것이 중요하다. 이렇게 하면 중간 계산 결과값의 크기가 M을 넘지 않게 되어(최대 ''p'' 비트 크기), 매우 큰 수가 되는 것을 방지하고 효율적인 계산이 가능하다. 이는 모듈러 거듭제곱에서 사용하는 방식과 유사하다.

수열의 시작 값 s_0는 일반적으로 4를 사용하지만, 다른 값을 사용할 수도 있다.[2] 어떤 시작 값을 사용하든 Mp가 메르센 소수이면 뤼카-레머 나머지는 0이 된다.

3. 1. 초기값

메르센 수 Mp = 2p − 1를 판별할 때 (여기서 p는 홀수 소수), 뤼카-레머 소수판별법은 특정 수열 s_i를 사용한다. 이 수열은 0 이상의 모든 정수 i에 대해 다음과 같이 정의된다.

s_0 = 4

s_i = s_{i-1}^2 - 2 \quad (i \ge 1)

이 수열의 첫 몇 항은 4, 14, 194, 37634, ... 와 같다. 판별법의 핵심은 s_{p-2}를 Mp로 나눈 나머지가 0인지 확인하는 데 있다. 즉, s_{p-2} \equiv 0 \pmod{M_p} 이 성립하면 Mp는 소수이다. 여기서 s_{p-2} \pmod{M_p} 값을 '''뤼카-레머 나머지'''라고 부른다.

일반적으로 초기값 s_0는 4를 사용하지만, 다른 값을 사용할 수도 있다. 예를 들어 10이나 52와 같은 다른 정수 값을 초기값으로 사용할 수 있다.[2] 이러한 다른 초기값으로 계산된 뤼카-레머 나머지도 Mp가 메르센 소수일 경우에는 여전히 0이 된다. 그러나 수열의 각 항 값은 달라지며, Mp가 합성수일 때 계산되는 0이 아닌 뤼카-레머 나머지 값도 s_0 = 4일 때와는 다른 값을 갖게 된다.

정수 외에 분수 형태의 초기값도 사용될 수 있다. 예를 들어, (2 mod Mp)(3 mod Mp)−1, 간단히 2/3로 표기되는 값을 사용할 수 있다.[2] 이 값은 지수가 p인 웨그스태프 수 (2p + 1) / 3과 같다.

4, 10, 2/3와 같은 초기값들은 보편적이라고 불리는데, 이는 거의 모든 소수 p에 대해 유효하기 때문이다. 이러한 보편적인 초기값은 무한히 많이 존재한다.[2]

반면, 모든 p에 대해 유효하지 않고 특정 조건을 만족하는 p의 부분 집합에 대해서만 유효한 초기값도 있다. 예를 들어, 초기값 s_0 = 3은 p가 4로 나눈 나머지가 3인 경우 (즉, p \equiv 3 \pmod 4)에만 사용할 수 있다.[3] 이 초기값 3은 과거 손으로 계산하던 시절에 뤼카가 M127이 소수임을 증명할 때 사용하기도 했다.[4] 초기값을 3으로 사용할 경우 수열의 첫 몇 항은 3, 7, 47, ... 이 된다.

3. 2. 끝에서 두 번째 항의 부호 (레머 기호)

만약 s_{p-2}\equiv0\pmod{M_p}이면, 끝에서 두 번째 항은 s_{p-3}\equiv\pm 2^{(p+1)/2}\pmod{M_p}이다. 이 끝에서 두 번째 항의 부호를 '''레머 기호''' ϵ(''s''0, ''p'')라고 부른다.

2000년 S.Y. 게브레-에그지아베르(S.Y. Gebre-Egziabher)는 시작 값이 2/3이고 ''p'' ≠ 5일 때 부호가 다음과 같음을 증명했다.

:\epsilon ({2 \over 3},\ p) = (-1) ^ {p-1 \over 2}

즉, ϵ(2/3, ''p'') = +1 이면 ''p'' = 1 (mod 4)이고 p ≠ 5이다.

같은 저자는 또한 월트먼(George Woltman)의 추측을 증명했는데, 시작 값이 4와 10일 때 ''p''가 2 또는 5가 아니면 레머 기호는 다음과 같은 관계를 갖는다.

:\epsilon (10,\ p) = \epsilon (4,\ p) \ \times \ (-1) ^ {{(p+1)(p+3)} \over 8}

즉, ϵ(4, ''p'') × ϵ(10, ''p'') = 1 이면 ''p'' = 5 or 7 (mod 8)이고 p ≠ 2, 5이다.

OEIS 수열 A123271은 각 메르센 소수 ''M''''p''에 대한 ϵ(4, ''p'')를 보여준다.

4. 시간 복잡도

뤼카-레머 판별법 알고리즘에서 각 반복마다 비용이 많이 드는 연산은 `s`의 제곱(`s × s`)과 모듈러 연산(`mod M`)이다.[6]

`mod M` 연산, 즉 M_p = 2^p - 1에 대한 나머지 연산은 다음과 같은 속성을 이용하여 효율적으로 수행될 수 있다. 임의의 정수 ''k''와 ''n''에 대해,

:k \equiv (k \bmod 2^n) + \lfloor k/2^n \rfloor \pmod{2^n - 1}.

이는 ''k''를 2^n - 1로 나눈 나머지는 ''k''의 하위 ''n'' 비트와 나머지 상위 비트들의 합을 2^n - 1로 나눈 나머지와 같다는 의미이다. 이 과정을 나머지가 ''n'' 비트보다 작아질 때까지 반복하면 나눗셈 없이 나머지를 구할 수 있다. 예를 들어, 916을 2^5 - 1 = 31로 나눈 나머지는 다음과 같이 계산할 수 있다. 916은 이진수로 11100101002이다.

단계연산결과 (이진수)결과 (십진수)
1(1110010100 \bmod 2^5) + \lfloor 1110010100 / 2^5 \rfloor \pmod{31}10100_2 + 11100_220 + 28 = 48
2(110000 \bmod 2^5) + \lfloor 110000 / 2^5 \rfloor \pmod{31}10000_2 + 1_216 + 1 = 17



따라서 916을 31로 나눈 나머지는 17이다.

알고리즘의 각 단계에서 계산되는 `s × s`의 값은 M_p^2보다 작고, M_p^2 < (2^p)^2 = 2^{2p}이므로 최대 2''p'' 비트를 가진다. 위의 나머지 계산법을 사용하면, 최대 한 번의 ''p''-비트 덧셈 연산으로 나머지를 구할 수 있으며, 이는 선형 시간 복잡도, 즉 O(p) 안에 수행될 수 있다. (단, 계산 결과가 2^p - 1 자체가 되는 예외적인 경우가 있으나 이는 쉽게 처리 가능하다.)[6]

따라서 알고리즘의 전체 시간 복잡도는 ''p''-비트 정수 두 개를 곱하는 데 사용되는 곱셈 알고리즘의 효율성에 따라 결정된다.


  • 가장 기본적인 초등학교 방식 곱셈 알고리즘은 O(''p''2)의 시간이 걸린다. 뤼카-레머 판별법은 ''p''-2번 반복하므로, 총 시간 복잡도는 O(''p''3)이 된다.[6]
  • 더 효율적인 쇤하게–슈트라센 알고리즘은 고속 푸리에 변환(FFT)을 이용하여 두 ''p''-비트 정수를 O(''p'' log ''p'' log log ''p'') 시간에 곱할 수 있다. 이를 사용하면 뤼카-레머 판별법의 전체 시간 복잡도는 O(''p''2 log ''p'' log log ''p'') 또는 Õ(p2)로 줄어든다.[6]
  • 현재까지 알려진 가장 빠른 곱셈 알고리즘 중 하나인 퓌러 알고리즘은 두 ''p''-비트 정수를 p \log p\ 2^{O(\log^* p)} 시간에 곱할 수 있다.[6]


다른 소수 판별법과 비교하면 다음과 같다.

  • 밀러-라빈 소수 판별법은 가장 널리 쓰이는 확률적 소수 판별법 중 하나로, ''n''자리 수에 대해 FFT 기반 곱셈을 사용하면 O(''k'' ''n''2 log ''n'' log log ''n'')의 비트 연산 시간이 걸린다. 여기서 ''k''는 테스트 반복 횟수이다. 상수 ''k''에 대해서는 뤼카-레머 판별법과 점근적 시간 복잡도가 비슷하지만, 실제로는 여러 번의 반복 수행 비용 등으로 인해 성능 차이가 발생할 수 있다.[6]
  • AKS 소수 판별법은 최초로 발견된 결정론적 다항 시간 소수 판별법이지만, 알려진 가장 효율적인 변형조차도 Õ(n6)의 비트 연산 시간이 필요하여 실제로는 매우 느리다.[6]

5. 예시

메르센 소수 M3 = 23−1 = 7은 소수이다. 뤼카-레머 소수 판별법은 이를 다음과 같이 검증한다. ''p'' = 3이므로 수열 ''s''는 ''p'' - 2 = 1번 업데이트된다. 초기값 ''s''0 = 4로 시작한다.


  • s_1 \leftarrow (s_0^2 - 2) \pmod{M_3} = (4^2 - 2) \pmod{7} = (16 - 2) \pmod{7} = 14 \pmod{7} = 0


최종 값 ''s''1이 0이므로, M3는 소수라는 결론을 내릴 수 있다.

반면에, M11 = 211−1 = 2047 = 23 × 89는 소수가 아닌 합성수이다. ''p'' = 11이므로 수열 ''s''는 ''p'' - 2 = 9번 업데이트된다. 다시, ''s''0 = 4로 시작한다.

  • s_1 \leftarrow (4^2 - 2) \pmod{2047} = 14
  • s_2 \leftarrow (14^2 - 2) \pmod{2047} = 194
  • s_3 \leftarrow (194^2 - 2) \pmod{2047} = 788
  • s_4 \leftarrow (788^2 - 2) \pmod{2047} = 701
  • s_5 \leftarrow (701^2 - 2) \pmod{2047} = 119
  • s_6 \leftarrow (119^2 - 2) \pmod{2047} = 1877
  • s_7 \leftarrow (1877^2 - 2) \pmod{2047} = 240
  • s_8 \leftarrow (240^2 - 2) \pmod{2047} = 282
  • s_9 \leftarrow (282^2 - 2) \pmod{2047} = 1736


최종 값 ''s''9 = 1736은 0이 아니므로, M11 = 2047은 소수가 아니라는 결론을 내릴 수 있다. M11 = 2047은 자명하지 않은 인수를 가지고 있지만, 뤼카-레머 소수 판별법은 그 인수들이 무엇인지에 대한 어떠한 정보도 제공하지 않는다.

6. 정확성 증명

이 테스트의 정확성 증명은 레머가 제시한 원래 증명보다 간단하다. 먼저, 수열 {\langle}s_i{\rangle}를 다음과 같이 정의한다.

:

s_i=

\begin{cases}

4 & \text{if }i=0;\\

s_{i-1}^2-2 & \text{otherwise.}

\end{cases}



증명의 목표는 메르센 소수 M_p = 2^p - 1 (단, ''p''는 소수)에 대해, M_p가 소수인 것과 s_{p-2} \equiv 0 \pmod{M_p}인 것이 필요충분조건임을 보이는 것이다.

수열 {\langle}s_i{\rangle}는 점화 관계이며, 폐쇄 형식 해를 가진다. \omega = 2 + \sqrt{3}와 \bar{\omega} = 2 - \sqrt{3}라고 하면, 수학적 귀납법을 통해 모든 ''i'' ≥ 0에 대해 다음과 같은 폐쇄 형식을 유도할 수 있다.

:s_i = \omega^{2^i} + \bar{\omega}^{2^i}

이 폐쇄 형식은 증명의 양방향, 즉 충분성(s_{p-2} \equiv 0 \pmod{M_p}이면 M_p는 소수)과 필요성(M_p가 소수이면 s_{p-2} \equiv 0 \pmod{M_p}) 모두에서 핵심적으로 사용된다. 상세한 증명 과정은 아래 하위 섹션에서 다룬다.

6. 1. 충분성

이 테스트의 정확성 증명은 데릭 헨리 레머가 제시한 원래 증명보다 간단하다. 다음 정의를 상기해 보자.

:

s_i=

\begin{cases}

4 & \text{if }i=0;\\

s_{i-1}^2-2 & \text{otherwise.}

\end{cases}



증명의 목표는 M_p가 소수인 것과 s_{p-2} \equiv 0 \pmod{M_p}인 것이 필요충분조건임을 보이는 것이다.

수열 {\langle}s_i{\rangle}는 폐쇄 형식 해를 갖는 점화 관계이다. \omega = 2 + \sqrt{3}와 \bar{\omega} = 2 - \sqrt{3}이라고 하자. 그러면 수학적 귀납법에 의해 모든 ''i'' ≥ 0에 대해 s_i = \omega^{2^i} + \bar{\omega}^{2^i}가 성립한다.

:s_0 = \omega^{2^0} + \bar{\omega}^{2^0} = \left(2 + \sqrt{3}\right) + \left(2 - \sqrt{3}\right) = 4

이고, ''n'' > 0에 대해

:

\begin{align}

s_n

&= s_{n-1}^2 - 2 \\

&= \left(\omega^{2^{n-1}} + \bar{\omega}^{2^{n-1}}\right)^2 - 2 \\

&= \omega^{2^n} + 2\omega^{2^{n-1}}\bar{\omega}^{2^{n-1}} + \bar{\omega}^{2^n} - 2 \\

&= \omega^{2^n} + \bar{\omega}^{2^n} + 2(\omega\bar{\omega})^{2^{n-1}} - 2.

\end{align}



이때 \omega\bar{\omega} = \left(2 + \sqrt{3}\right) \left(2 - \sqrt{3}\right) = 4 - 3 = 1이므로,

:s_n = \omega^{2^n} + \bar{\omega}^{2^n}.

이 폐쇄 형식은 충분성 증명과 필요성 증명 모두에서 사용된다.

이제 s_{p-2} \equiv 0 \pmod{M_p}라는 조건이 M_p가 소수임을 함의하는 충분조건임을 증명한다. 다음은 J. W. 브루스[7]가 제시하고 제이슨 보이치호프스키[8]가 언급한 군론을 활용한 간결한 증명이다.

s_{p-2} \equiv 0 \pmod{M_p}라고 가정하자. 그러면 어떤 정수 ''k''에 대해

:\omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} = k M_p

가 성립한다. \bar{\omega} = \omega^{-1}이므로,

:\omega^{2^{p-2}} + \omega^{-2^{p-2}} = k M_p.

양변에 \omega^{2^{p-2}}를 곱하면

:\left(\omega^{2^{p-2}}\right)^2 + 1 = k M_p \omega^{2^{p-2}}

:\omega^{2^{p-1}} = k M_p \omega^{2^{p-2}} - 1.\qquad\qquad(1)

귀류법을 사용하기 위해, ''M''''p''가 합성수라고 가정하고, ''q''를 ''M''''p''의 가장 작은 소인수라고 하자. 메르센 수 M_p = 2^p - 1 (단, ''p''는 홀수 소수)는 항상 홀수이므로, ''q'' > 2이다. \mathbb{Z}_q를 모듈로 ''q''인 정수의 체라고 하고, X = \left\{a + b \sqrt{3} \mid a, b \in \mathbb{Z}_q\right\}라고 하자. ''X''에서의 곱셈은 다음과 같이 정의된다.

:\left(a + \sqrt{3} b\right) \left(c + \sqrt{3} d\right) = [(a c + 3 b d) \bmod q] + \sqrt{3} [(a d + b c) \bmod q].[9]

이 곱셈 연산에 대해 집합 ''X''는 닫혀 있다. 즉, ''X''의 원소들의 곱은 다시 ''X''의 원소가 된다. ''X''의 원소 개수(크기)는 |X| = q^2이다.

''q'' > 2이므로, \omega = 2 + \sqrt{3}와 \bar{\omega} = 2 - \sqrt{3}는 ''X''에 속한다.[10] ''X''의 원소 중 곱셈에 대한 역원을 갖는 원소들의 집합은 군을 형성하며, 이를 ''X''*로 표시하고 그 크기는 |X^*|이다. ''X''에서 역원을 갖지 않는 원소는 0 = 0 + 0\sqrt{3}뿐이므로, |X^*| \leq |X| - 1 = q^2 - 1이다.

가정에서 M_p \equiv 0 \pmod{q}이고 \omega \in X이므로, ''X''에서 식 (1)의 우변 첫 항은 0이 된다.

:k M_p \omega^{2^{p-2}} \equiv 0 \pmod{q}.

따라서 식 (1)은 ''X''에서 다음과 같이 된다.

:\omega^{2^{p-1}} \equiv -1 \pmod{q}.

양변을 제곱하면

:\omega^{2^p} \equiv (-1)^2 \equiv 1 \pmod{q}.

이는 \omega가 곱셈군 ''X''*에 속하며, 그 차수가 2^p를 나눔을 의미한다. 또한 \omega^{2^{p-1}} \equiv -1 \not\equiv 1 \pmod{q}이므로, \omega의 차수는 2^{p-1}을 나누지 않는다. 따라서 \omega의 차수는 정확히 2^p이다.

라그랑주 정리에 따르면, 군의 원소의 차수는 군 전체의 크기(위수)를 나누어야 한다. 따라서 \omega의 차수인 2^p는 군 ''X''*의 크기 |X^*|를 나누어야 하고, 특히 2^p \leq |X^*|여야 한다. 위에서 |X^*| \leq q^2 - 1이었으므로,

:2^p \leq |X^*| \leq q^2 - 1 < q^2.

즉, 2^p < q^2이다.

하지만 ''q''는 합성수 M_p = 2^p - 1의 가장 작은 소인수이다. 합성수 N의 가장 작은 소인수 q는 항상 q \leq \sqrt{N}을 만족하므로,

:q \leq \sqrt{M_p} \implies q^2 \leq M_p = 2^p - 1.

결과적으로 2^p < q^2와 q^2 \leq 2^p - 1라는 두 부등식을 얻는데, 이는 2^p < 2^p - 1라는 명백한 모순을 발생시킨다.

이 모순은 처음에 ''M''''p''가 합성수라고 가정한 것에서 비롯되었다. 따라서 초기 가정은 거짓이며, ''M''''p''는 반드시 소수여야 한다.

6. 2. 필요성

M_p가 소수라고 가정하고, s_{p-2} \equiv 0 \pmod{M_p}임을 보이는 것이 목표이다. 다음은 Ӧystein J. Rödseth가 제시한 간략화된 증명이다.[11]

홀수 소수 p > 2에 대해 M_p = 2^p - 1 \equiv (-1)^p - 1 \equiv -2 \equiv 1 \pmod 3이고, M_p = 2^p - 1 \equiv (-1) - 1 \equiv -2 \pmod 4 (단, p는 홀수이므로 p \ge 3이면 2^p는 8 이상이고 4의 배수), 즉 M_p \equiv 3 \pmod 4이다. 또한 p \ge 3이면 2^p는 8의 배수이므로 M_p = 2^p - 1 \equiv -1 \equiv 7 \pmod 8이다. 종합하면, p>2인 소수 p에 대해 M_p \equiv 7 \pmod{12}이다. 이차 상호 법칙의 보조 법칙과 르장드르 기호의 성질에 의해 (3|M_p) = -(M_p|3) 이고, (M_p|3) = (1|3) = 1이므로 (3|M_p) = -1이다. 이는 3이 M_p를 법으로 하는 제곱 비잉여임을 의미한다. 오일러의 기준에 따르면, 이는 다음 식과 동치이다.

:3^{\frac{M_p-1}{2}} \equiv -1 \pmod{M_p}.

반대로, 2는 M_p를 법으로 하는 제곱 잉여이다. 왜냐하면 M_p \equiv 7 \pmod 8 이므로 이차 상호 법칙의 보조 법칙에 의해 (2|M_p)=1이기 때문이다. 오일러의 기준에 따라 다음이 성립한다.

:2^{\frac{M_p-1}{2}} \equiv 1 \pmod{M_p}.

위의 두 합동식을 결합하면 다음을 얻는다.

:24^{\frac{M_p-1}{2}} \equiv \left(2^3 \cdot 3\right)^{\frac{M_p-1}{2}} \equiv \left(2^{\frac{M_p-1}{2}}\right)^3 \left(3^{\frac{M_p-1}{2}}\right) \equiv (1)^3(-1) \equiv -1 \pmod{M_p}.

이제 유한체 \mathbb{F}_{M_p^2} = \mathbb{Z}_{M_p}[ \sqrt{3} ] = \{a + b\sqrt{3} \mid a, b \in \mathbb{Z}_{M_p}\}를 생각하자. 이 체에서 연산은 법 M_p에 대해 이루어진다. \sigma = 2\sqrt{3}이라고 정의하면, 체 \mathbb{F}_{M_p^2}에서 다음이 성립한다.

:

\begin{align}

(6+\sigma)^{M_p}

&= 6^{M_p} + \sigma^{M_p} && \text{(유한체에서의 이항정리)}\\

&= 6 + (2\sqrt{3})^{M_p} \\

&= 6 + 2^{M_p} (\sqrt{3})^{M_p} \\

&= 6 + 2 \cdot 3^{\frac{M_p}{2}} && \text{(페르마의 소정리: } a^{M_p} \equiv a \pmod{M_p}) \\

&= 6 + 2 \cdot 3^{\frac{M_p-1}{2}} \sqrt{3} \\

&= 6 + 2 (-1) \sqrt{3} && \text{(위에서 보인 } 3^{\frac{M_p-1}{2}} \equiv -1 \pmod{M_p}) \\

&= 6 - 2\sqrt{3} \\

&= 6 - \sigma.

\end{align}



여기서 (x+y)^{M_p} \equiv x^{M_p} + y^{M_p} \pmod{M_p}인 유한체에서의 이항정리와, 임의의 정수 a에 대해 a^{M_p} \equiv a \pmod{M_p}인 페르마의 소정리를 사용했다. 또한 (\sqrt{3})^{M_p} = 3^{\frac{M_p}{2}} = 3^{\frac{M_p-1}{2}} \sqrt{3} 임을 이용했다.

이제 \omega = 2 + \sqrt{3}으로 정의하자. (이는 s_i의 폐쇄 형식을 유도할 때 사용된 값과 같다.) \omega = \frac{(6+\sigma)^2}{24} 임을 확인하자.

\frac{(6+\sigma)^2}{24} = \frac{(6+2\sqrt{3})^2}{24} = \frac{36 + 24\sqrt{3} + 12}{24} = \frac{48 + 24\sqrt{3}}{24} = 2 + \sqrt{3} = \omega.

이 \omega를 사용하여 체 \mathbb{F}_{M_p^2}에서 \omega^{\frac{M_p+1}{2}}를 계산한다.

:

\begin{align}

\omega^{\frac{M_p+1}{2}}

&= \left(\frac{(6+\sigma)^2}{24}\right)^{\frac{M_p+1}{2}} \\

&= \frac{(6+\sigma)^{M_p+1}}{24^{\frac{M_p+1}{2}}} \\

&= \frac{(6+\sigma)(6+\sigma)^{M_p}}{24 \cdot 24^{\frac{M_p-1}{2}}} \\

&= \frac{(6+\sigma)(6-\sigma)}{24 \cdot (-1)} && \text{(위에서 보인 } (6+\sigma)^{M_p} = 6-\sigma \text{ 와 } 24^{\frac{M_p-1}{2}} \equiv -1 \pmod{M_p}) \\

&= \frac{36 - \sigma^2}{-24} \\

&= \frac{36 - (2\sqrt{3})^2}{-24} \\

&= \frac{36 - 12}{-24} \\

&= \frac{24}{-24} \\

&= -1.

\end{align}



이제 \omega \bar{\omega} = (2+\sqrt{3})(2-\sqrt{3}) = 4-3 = 1 이므로 \bar{\omega} = \omega^{-1}이다. 위에서 얻은 식 \omega^{\frac{M_p+1}{2}} = -1의 양변에 \bar{\omega}^{\frac{M_p+1}{4}}를 곱하면 다음과 같다.

:

\begin{align}

\omega^{\frac{M_p+1}{2}} \bar{\omega}^{\frac{M_p+1}{4}} &= -\bar{\omega}^{\frac{M_p+1}{4}} \\

\omega^{\frac{M_p+1}{4}} (\omega^{\frac{M_p+1}{4}} \bar{\omega}^{\frac{M_p+1}{4}}) &= -\bar{\omega}^{\frac{M_p+1}{4}} \\

\omega^{\frac{M_p+1}{4}} (\omega \bar{\omega})^{\frac{M_p+1}{4}} &= -\bar{\omega}^{\frac{M_p+1}{4}} \\

\omega^{\frac{M_p+1}{4}} (1)^{\frac{M_p+1}{4}} &= -\bar{\omega}^{\frac{M_p+1}{4}} \\

\omega^{\frac{M_p+1}{4}} + \bar{\omega}^{\frac{M_p+1}{4}} &= 0

\end{align}



여기서 M_p = 2^p - 1 이므로 \frac{M_p+1}{4} = \frac{2^p}{4} = 2^{p-2}이다. 따라서 다음을 얻는다.

:\omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} = 0

수열 s_i의 폐쇄 형식 해가 s_i = \omega^{2^i} + \bar{\omega}^{2^i} 이므로, 위 식은 s_{p-2} = 0 (체 \mathbb{F}_{M_p^2}에서) 임을 의미한다. s_{p-2}는 정수들의 연산으로 정의되므로, 이는 s_{p-2}가 M_p의 배수임을 뜻한다. 즉,

:s_{p-2} \equiv 0 \pmod{M_p}.

이것으로 필요성 증명이 완료된다.

7. 응용

뤼카-레머 소수판별법은 Prime95 소프트웨어에 사용되며, 현재까지 알려진 대부분의 메르센 소수는 이 판별법을 통해 발견되었다.

특히, GIMPS(Great Internet Mersenne Prime Search) 프로젝트에서는 큰 소수를 찾는 주요 판별법으로 뤼카-레머 소수판별법을 사용한다. GIMPS는 이 판별법을 활용하여 현재까지 알려진 가장 큰 소수들을 성공적으로 찾아냈다.[12] 이 판별법은 매우 큰 수에 대해서도 합리적인 시간 안에 소수 여부를 판별할 수 있다는 점에서 가치가 높다. 반면, 비슷한 속도를 가진 페팽의 검사는 모든 페르마 수에 적용 가능하지만, 계산상의 한계로 인해 뤼카-레머 소수판별법보다 훨씬 작은 범위의 수에 대해서만 사용할 수 있다.

참조

[1] 학술지 Note on the Lucas–Lehmer Test https://www.irishmat[...] Irish Mathematical Society
[2] Doctoral thesis Mersenne primes and class field theory https://openaccess.l[...] 2018-12-17
[3] 학술지 Mersenne and Fermat numbers 1954
[4] 기술 보고서 Mersenne numbers https://core.ac.uk/d[...] 2018-12-17
[5] 학회자료 Woltman's conjecture on the Lucas-Lehmer test http://dagstuhl.suns[...] 2024-10-16
[6] Citation A New Mersenne Prime
[7] 학술지 A Really Trivial Proof of the Lucas–Lehmer Test
[8] 웹사이트 Mersenne Primes, An Introduction and Overview https://web.archive.[...] 2003
[9] 문서
[10] 문서
[11] 학술지 A note on primality tests for N=h·2^n−1 http://folk.uib.no/n[...] 1994
[12] 웹사이트 The "Top Ten" Record Primes http://primes.utm.ed[...]


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com