루카스-레머 원시성 검정

수학에서는 루카스가-레머 테스트(LTT)는 메르센 수치에 대한 원시성 테스트다.이 테스트는 원래 에두아르 루카스에 의해 1876년에^[1] 개발되었고 그 후 1930년대에 데릭 헨리 레머에 의해 개선되었다.

시험

더 루카스-레머 테스트는 다음과 같이 동작한다.M_p = 2^p - 1을 p 이상 프라임으로 테스트할 메르센 번호로 설정한다.p는 M보다_p 기하급수적으로 작기 때문에 p의 p의 primality를 trial division과 같은 간단한 알고리즘으로 효율적으로 확인할 수 있다.다음 기준의 모든 i에 대해$$ 시퀀스${\displaystyle }${${\displaystyle {}_{}}$ ${\displaystyle i_{}}$} ${\displaystyle \{s_{i}\}}$을(를) 정의하십시오.

${\displaystyle s_{i}={\case}4&{\text}{if }i=0;\s_{i-1}^{2}-2&{\text{data.}}}\end{case}}$

이 시퀀스의 처음 몇 개 항은 4, 14, 194, 37634, ...이다(OEIS에서 시퀀스 A003010).그렇다면 M은_p 만약의 경우에 한해서만 프라임이다.

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

s_{p − 2} mod M이라는_p 숫자는 루카스-라고 불린다.p.의 레머 잔여물(일부 저자는 s₁ = 4를 동등하게 설정하고 s mod_p−1 M을_p 시험한다).유사 코드에서는 테스트가 다음과 같이 기록될 수 있다.

// Mp = 2p - 1이 p > 2 Lucas–의 프라임인지 판단한다.Lehmer(p) var s = 4 var M = 2p - 1 p - 2회 반복: s = (s × s) - 2) mod M s = 0 = 0이면 PRIME이 합성값을 반환함

수행 중mod M각 반복에서 모든 중간 결과는 최대 p비트(비트의 수가 각 반복의 두 배가 됨)가 되도록 보장한다.모듈형 지수에 동일한 전략이 사용된다.

대체 시작 값

예를 들어, 10, 52 및 기타(OEIS에서 순서 A018844)와 같이 4 이외의₀ 시작 값이 가능하다.M이_p 메르센 프라임이라면 이러한 대체 출발 값으로 계산한 루카스-레머 잔여물은 여전히 0이 된다.그러나 시퀀스의 조건은 다를 것이며, 비프라임 M에_p 대한 0이 아닌 루카스-레머 잔여물은 s₀ = 4일 때 계산된 0이 아닌 값과 다른 숫자 값을 갖는다.

또한 일반적으로 2/3으로 짧게 나타내는 시작 값(2 mod M_p)(3 mod M_p)을 사용할 수도 있다.^−1[2]이 시작 값은 (2^p + 1) /3, 지수 p를 갖는 Wagstaff 번호와 같다.

4, 10, 2/3과 같은 시작 값은 범용적이며, 즉 모든(또는 거의 모든) p에 대해 유효하다.무한히 많은 추가 범용 시작 값이 있다.^[2]그러나 일부 다른 시작 값은 가능한 모든 p의 하위 집합에만 유효하다. 예를 들어 s₀ = 3은 p = 3(모드 4)일 경우 사용할 수 있다.^[3]이₁₂₇ 시작 값은 M 프라임을 증명하는 루카스를 포함해 손 계산의 시대에 적합한 곳에 자주 사용되었다.^[4]수열의 처음 몇 개 항은 3, 7, 47, ...이다. (OEIS에서 순서 A001566).

penultimate 항의 기호

s_p−2 = 0 mod M이면_p penultimate 항은 s = ± 2 mod^(p+1)/2 M이다_p−3p.이 펜ultimate 용어의 부호를 Lehmer 기호 ϵ(s₀, p)라고 한다.

2000년 S.Y. Gebre-Egziabher는 시작 값 2/3과 p ≠ 5에 대해 기호가 다음과 같음을 증명했다.

${\displaystyle \epsilon({2\over 3}\p)=(-1)^{p-1 \over2}}:$

즉, ((2/3, p) = +1 iffp = 1 (mod 4)과 p ≠ 5이다.^[2]

같은 저자는 또한 p가 2나 5가 아닐 때 시작 값 4와 10에 대한 Lehmer 기호가 다음과 관련이 있다는 것을 증명하였다.

${\displaystyle \epsilon (10,\ p)=\epsilon (4,\ p)\\\\\\\\\ \-1)^{{(p+1)(p+3)} \8}}이상 \}$

즉, ϵ(4, p)× ϵ(10, p) = 1 iff p = 5 또는 7 (mod 8)과 p ≠ 2, 5이다.^[2]

OEIS 시퀀스 A123271은 각 메르센 프라임 M에_p 대해 ϵ(4, p)을 나타낸다.

시간 복잡성

위에 쓰여진 알고리즘에서는 각 반복 동안 두 개의 값비싼 연산이 있다: 곱하기.s × s, 그리고mod M작전그mod M운영은 다음을 관찰함으로써 표준 이진 컴퓨터에서 특히 효율적으로 만들어질 수 있다.

${\displaystyle k\equiv(k\,{\bmod {\,}2^{n}+\lfloor k/2^{n}\pmod {2^{n}-1}.}$

이것은 k의 n 비트와 k의 나머지 비트가 k modulo 2-1과ⁿ 동등하다고 말한다.이 동등성은 최대 n비트가 남을 때까지 반복해서 사용할 수 있다.이렇게 하여 k를 메르센 번호 2-1로ⁿ 나눈 후의 나머지는 분할을 사용하지 않고 계산한다.예를 들어,

916모드 2-15	=	1110010100모드2 2-15
	=	(916 mod 25) + int(916 ÷ 25) mod 2-15
	=	(101002 + 111002) 모드 2-15
	=	110000모드2 2-15
	=	(100002 + 12) 모드 2-15
	=	10001모드2 2-15
	=	100012
	=	17.

더구나 그 이후로는s × s이² 간단한 기술은^2p M < 2를 절대 초과하지 않을 것이다. 이 기술은 선형 시간 내에 수행될 수 있는 최대 1 p-bit 추가(그리고 p번째 비트에서 첫 번째 비트로 이동)로 수렴된다.이 알고리즘은 아주 작은 예외적인 경우를 가지고 있다.0의 정확한 값이 아닌 계수의 배수에 대해 2-1을ⁿ 산출한다.그러나 이 경우는 탐지하고 고치기 쉽다.

계수를 벗어나면 알고리즘의 점증적 복잡성은 각 단계에서 제곱에 사용되는 곱셈 알고리즘에만 의존한다.곱셈을 위한 간단한 "등급 학교" 알고리즘은 p-비트 숫자를 제곱하기 위해 O(p²) 비트 레벨 또는 단어 레벨 연산을 요구한다.O(p) 횟수가 이렇게 되기 때문에 총 시간 복잡도는 O(p³)이다.보다 효율적인 곱셈 알고리즘은 고속 푸리에 변환에 기반한 Shönhage-Strassen 알고리즘이다.P비트 숫자를 제곱하기 위해서는 O(p log p log p) 시간만 필요하다.이것은 복잡성을 O(p log p log p) 또는 õ(p²)로² 감소시킨다.^[5]훨씬 더 효율적인 곱셈 알고리즘인 총통의 알고리즘은 $p{\displaystyle }$ ${\displaystyle \log }$ ${\displaystyle }$ ${\displaystyle p}$ ${\displaystyle 2^{}}$ ${\displaystyle \text{O}{\mathrm{}}^{}}$( ${\displaystyle {{\log }^{}}^{}}$ ${\displaystyle {{}^{}}^{}}$ p$){\$p\$log$ p\$2^{O(\log ^{*}p)}}}}}$시간만$$ 있으면 2개의 p비트 숫자를 곱할 수 있다.

이에 비해 일반 정수에 대한 가장 효율적인 무작위 원시성 시험인 Miller-Rabin 원시성 시험은 N자리 숫자에 대한 FFT 곱셈을 사용한 O(k² n log n log n) 비트 연산을 요구한다. 여기서 k는 반복 횟수이며 오류율과 관련이 있다.상수 k의 경우, 이것은 루카스-레머 테스트와 동일한 복잡도 등급에 있다.그러나 실제로 많은 반복 작업과 다른 차이점들을 수행하는 비용은 밀러-라빈에게 더 나쁜 성능으로 이어진다.임의의 n자리 숫자에 대한 가장 효율적인 결정론적 원시성 시험인 AKS 원시성 시험은 가장 잘 알려진 변종에서 ((n⁶) 비트 연산이 필요하며 상대적으로 작은 값에도 매우 느리다.

예

메르센 번호₃ M = 2-1³ = 7이 황금이다.더 루카스-레머 테스트는 이를 다음과 같이 검증한다.초기 s는 4로 설정되었다가 3-2 = 1회 업데이트된다.

• s ← ((4 × 4) − 2) mod 7 = 0.

s의 최종 값이 0이기 때문에 결론은 M이₃ prime이라는 것이다.

반면 M₁₁ = 2047 = 23 × 89는 프라임이 아니다.다시, s는 4로 설정되었지만 이제 11-2 = 9번 업데이트된다.

• s ← ((4 × 4) − 2) mod 2047 = 14
• s ← (14 × 14) - 2) mod 2047 = 194
• s ← ((194 × 194) − 2) mod 2047 = 788
• s ← ((788 × 788) − 2) mod 2047 = 701
• s ← (701 × 701) - 2) mod 2047 = 119
• s ← ((119 × 119) − 2) mod 2047 = 1877
• s ← ((1877 × 1877) − 2) mod 2047 = 240
• s ← ((240 × 240) − 2) mod 2047 = 282
• s ← ((282 × 282) − 2) mod 2047 = 1736

s의 최종 값이 0이 아니기 때문에 결론은 M₁₁ = 2047이 prime이 아니라는 것이다.M₁₁ = 2047은 비경쟁적 요인이 있지만 루카스-은레머 테스트는 그것들이 무엇일지에 대한 어떤 징후도 주지 않는다.

정확성 증명

여기에 제시된 이 테스트의 정확성 증명은 르메르가 제시한 원본 증명보다 간단하다.정의 불러오기

${\displaystyle s_{i}={\case}4&{\text}{if }i=0;\s_{i-1}^{2}-2&{\text{data.}}}\end{case}}$

목표는_p if s ${\displaystyle p_{}}$- ${\displaystyle 2}$ ${\displaystyle {}_{}}$ 0${\displaystyle }$(${\displaystyle \mathrm{mod}}$ ${\displaystyle M_{}}$ p${\displaystyle {}_{}}$)${\displaystyle }$. ${\displaystyle s_{p-2}\equiv$ 0${\pmod{M_{p}}}}}.$$}$

$⟨{\displaystyle }$ ${\displaystyle s{}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$ ${\$ 순서는 폐쇄형 솔루션과의 재발 관계다.Let ${\displaystyle \omega =2+{\sqrt {3}}}$ and ${\displaystyle {\bar {\omega }}=2-{\sqrt {3}}}$. It then follows by induction that ${\displaystyle s_{i}=\omega ^{2^{i}}+{\bar {\omega }}^{2^{i}}}$ for all i:

${\displaystyle s_{0}=\omega^{0}}+{2^{0}}}+{2^{0}}}}}}}}{{\mega}}}}}}}}=4}$

그리고

${\displaystyle {\begin{aligned}s_{n}&=s_{n-1}^{2}-2\\&=\left(\omega ^{2^{n-1}}+{\bar {\omega }}^{2^{n-1}}\right)^{2}-2\\&=\omega ^{2^{n}}+{\bar {\omega }}^{2^{n}}+2(\omega {\bar {\omega }})^{2^{n-1}}-2\\&=\omega ^{2^{n}}+{\bar {\omega }}^{2^{n}}.\end{정렬}}}$

마지막 단계는${\displaystyle \stackrel{}{}\Omega \mathrm{}}$ ${\displaystyle \Omega \stackrel{}{}}$ = ${\displaystyle (2\mathrm{}}$+ ${\displaystyle 3}$)${\displaystyle }$= 1${\displaystyle \omega{\bar}}}}}=\좌측(2+{\sqrt{3}\오른쪽)\좌측(2-{\sqrt{3}}}\$우측$)=1$을 사용한다$.$$}}$ 이$$ 폐쇄형식은 충분성의 증명과 필요성의 증명에 모두 사용된다.

자급률

$목표$는 s ${\displaystyle p_{}}$- ${\displaystyle 2_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle 0}$(${\displaystyle \mathrm{mod}}$ ${\displaystyle M_{}}$ $){\$이(가) M p ${\${p$}}}}}}$이 ${\displaystyle {프라임임}_{}}$을 함축하고$$ 있음을 보여주는 것이다.다음은 J. W. Bruce가^[6] Jason Wojciechowski에 의해 관계된 초등 집단 이론을 악용한 직접적인 증거다.^[7]

$s{\displaystyle {}_{}}$ ${\displaystyle p_{}}$- ${\displaystyle 2_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle 0}$(${\displaystyle \mathrm{모드}}$ ${\displaystyle M_{}}$ p${\displaystyle {}_{}}$)${\displaystyle }$. ${\displaystyle s_{p-2}\equiv 0{\pmod{M_{p}}}$을(를) 가정해 보십시오.

${\displaystyle \omega^{2^{p-2}}+{\bar{\omega}}}^{2^{p-2}}=kM_{p}}}}}}}$

일부 정수 k에 대해, 그래서

${\displaystyle \omega ^{2^{p-2}=kM_{p}-{\bar {\omega }^{2^{p-2}}.}$

$\Omega {\displaystyle {}^{}}$ 2 ${\displaystyle {p^{}}^{}}$- ${\displaystyle {2^{}}^{}}$ ${\$배 곱하기$$:

${\displaystyle \left(\omega^{2^{p-2}}\오른쪽)^{2}=kM_{p}\omega^{p-2}}-(\omega{\bar{\omega}}})^{2^{p-2}}}.}$

그러므로,

${\displaystyle \omega^{2^{p-1}=kM_{p}\omega^{2^{p-22}}-1.\qquad \qquad (1)}$

모순의 경우, M이_p 복합적이라고 가정하고, q를 M의_p 가장 작은 주요 요인이 되도록 한다.메르센 수치는 홀수여서 q > 2 입니다.Informally,^{[note 1]} let ${\displaystyle \mathbb {Z} _{q}}$ be the integers modulo q, and let ${\displaystyle X=\left\{a+b{\sqrt {3}}\mid a,b\in \mathbb {Z} _{q}\right\}.}$ Multiplication in ${\displaystyle X}$ is defined as

${\displaystyle \left(a+{\sqrt{3}b\right)\좌(c+{\sqrt{3}d\right)=[(ac+3bd)]\,{\bmod{\q]+{3}}}[(ad+bc)\bmod {,},}.}$

분명히, 이 곱셈은 닫혀 있다. 즉, X에서 나온 숫자의 산물은 그 자체로 X이다.X의 크기는 ${\displaystyle X}$. ${\displaystyle$ X $.}$로 표시된다.

q > 2 이후로는 $\Omega {\displaystyle }$ ${\displaystyle \omega }$과${\displaystyle \stackrel{}{}}\Omega {\displaystyle \stackrel{}{}}$ ${\$이(가) X에 있는$$ 것으로 이어진다.^{[note 2]}The subset of elements in X with inverses forms a group, which is denoted by X* and has size ${\displaystyle X^{*} .}$ One element in X that does not have an inverse is 0, so ${\displaystyle X^{*} \leq X -1=q^{2}-1.}$

${\displaystyle \mathrm{이제}}$ $M{\displaystyle {}_{}}$ ${\displaystyle p_{}}$ ${\displaystyle {}_{}}$ 0${\displaystyle }$( ${\displaystyle \mathrm{mod}}$ ${\displaystyle q}$) ${\$ 및$$ $\Omega {\displaystyle }$ ${\displaystyle X}$ ${\displaystyle \omega \in$ X$\},$ 그래서

${\displaystyle kM_{p}\omega^{2^{p-2}=0}$

X로, 그 다음 등식 (1)로,

${\displaystyle \omega^{2^{p-1}=-1}$

X로, 그리고 양쪽을 쪼개는 것은

${\displaystyle \omega^{2^{p}=1.}$

따라서 $\Omega {\displaystyle }$ ${\displaystyle \omega}$은(는) X*에 위치하며$$ 역 $\Omega {\displaystyle {}^{}}$ ${\displaystyle {{2p}^{}}^{}}$ ${\displaystyle {{}^{}}^{}{1}^{}}$. ${\displaystyle \omega ^{2^{p}-1}.}$게다가$$ $\Omega {\displaystyle }${\$displaystyle \omega$}의 순서는$.$ {\$displaystytylease 2^{p}$로 나뉜다.$}}$ 그러나$$ $\Omega {\displaystyle {}^{}}$ 2 ${\displaystyle \mathrm{p}{{}^{}}^{}}$-$$${\displaystyle {1^{}}^{}{p^{}}^{}}$ 1 ${\$$displaystyle$ $\omega ^{2^{p-1}\neq$ 1$\}$ 따라서 순서는$$ ${\displaystyle {정확히}^{}}$ 2${\displaystyle {}^{}}$${\displaystyle {\mathrm{p}}^{}}$. ${\displaystyle$ 2$^{p-1}.$$}$

원소의 순서는 기껏해야 그룹의 순서(크기)가 되므로,

$\displaystyle 2^{p}\leq X^{*} \leq q^{2}-1<q^{2}.}$

그러나 q는 복합 $M{\displaystyle {}_{}}$ ${\displaystyle p_{}}$ ${\$의 가장 작은 주 요인이다$.$

${\displaystyle q^{2}\leq M_{p}=2^{p}-1.}$

이렇게 하면 모순이 < - 1 ${\displaystyle$ 2$^{p}<2^{p}-1$ 따라서 ${\displaystyle {Mp}_{}}$ ${\$이(가) 프라임이다$$.

필요성

다른 방향에서는, $M{\displaystyle {}_{}}$ ${\displaystyle p_{}}${\$displaystyle M_{p}$의 원초성이 ${\displaystyle s_{}}$ $p{\displaystyle {}_{}}$ - ${\displaystyle 2_{}}$ ${\displaystyle 0}$ ${\displaystyle (\mathrm{모드}}$ M ${\displaystyle p_{}}$ $){\$을 함축하고$$ 있음을 보여주는 것이 목적이다$.$다음의 간단한 증거는 외스테인 J. 뢰데스에 의한 것이다.^[8]

Since ${\displaystyle 2^{p}-1\equiv 7{\pmod {12}}}$ for odd ${\displaystyle p>1}$, it follows from properties of the Legendre symbol that ${\displaystyle (3 M_{p})=-1.}$ This means that 3 is a quadratic nonresidue modulo ${\displaystyle M_{p}.$$}$ 오일러의 기준으로 볼$$ 때, 이것은

${\displaystyle 3^{\frac {M_{p}-1}{2}}:\equiv -1{\pmod{M_{p}}}.}$

In contrast, 2 is a quadratic residue modulo ${\displaystyle M_{p}}$ since ${\displaystyle 2^{p}\equiv 1{\pmod {M_{p}}}}$ and so ${\displaystyle 2\equiv 2^{p+1}=\left(2^{\frac {p+1}{2}}\right)^{2}{\pmod {M_{p}}}.}$ This ti오일러의 기준은

${\displaystyle 2^{\frac {M_{p}-1}{2}}\\equiv 1{\pmod{M_{p}}}.}$

이 두 동등성 관계의 산출물을 결합하는 것

${\displaystyle 24^{\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}}}.}$

Let ${\displaystyle \sigma =2{\sqrt {3}}}$, and define X as before as the ring ${\displaystyle X=\{a+b{\sqrt {3}}\mid a,b\in \mathbb {Z} _{M_{p}}\}.}$$$ 그리고 나서 링 X에서, 그것은 그 뒤를 따른다.

${\displaystyle {\begin{aligned}(6+\sigma )^{M_{p}}&=6^{M_{p}}+\left(2^{M_{p}}\right)\left({\sqrt {3}}^{M_{p}}\right)\\&=6+2\left(3^{\frac {M_{p}-1}{2}}\right){\sqrt {3}}\\&=6+2(-1){\sqrt {3}}\\&=6-\sigma ,\end{aligned}}}$

제1차 평등은 유한한 분야에서 이항 정리를 사용하는데, 이항 정리는 다음과 같다.

${\$$M_{p}}\equiv x^{M_{p}}+y^{M_{p}}{\pmod{M_{p$

그리고 제2의 평등은 페르마의 작은 정리를 사용하는데, 그것은 다음과 같다.

${\displaystyle a^{M_{p}}\equiv a{\pmod{M_{p}}}}}}$

모든 정수 a에 대해The value of ${\displaystyle \sigma }$ was chosen so that ${\displaystyle \omega ={\frac {(6+\sigma )^{2}}{24}}.}$ Consequently, this can be used to compute ${\displaystyle \omega ^{\frac {M_{p}+1}{2}}}$ in the ring X as

${\displaystyle {\begin{aigned}\omega^{\frac {M_{p}+1}{2}}}}&={\frac{(6+\sigma )^{M_{p}+1}:{24^{\frac{M_{p}+1}{2}}}}\\&={\frac {(6+\sigma )}^{M_{p}{{p}}{24\cdot 24^{\m_{p}-1}}\2}}\&={\frac{6+\sigma ){-24\&=1}{-}{-24\=1}}}{{{{{-}-}}}}}-}}}-}\end{정렬}}}$

남은 것은 이 방정식의 양쪽 면에${\displaystyle {\stackrel{}{}\Omega }^{\frac{{}_{}}{}}}$ M${\displaystyle {\frac{{}_{}{p}_{}}{}}^{}}$ + ${\displaystyle {\frac{1}{}}^{}}$ ${\displaystyle {\frac{\mathrm{}}{}}^{}}$ ${\${\$bar {\omega }^{\frac {M_{p}+1}{4$}를 곱하는 것뿐이다.$}}}},$${\displaystyle \Omega \stackrel{}{}}$= ${\displaystyle 1}$ ${\displaystyle \omega{\bar {\omega}=$1}을$($를) 사용하십시오$$.

${\displaystyle {\begin{aigned}\omega^{\frac {M_{p}+1}{2}}}{\bar {\omega}^{\frac {M_{p}+1}{4}-{4}=-{\bar {\obea}}^{\frac {M_{p}+1}{4}{4}}}}\\오메가^{\frac {M_{p}+1}{4}}}}+{\bar {\omega}^{\frac {M_{p}+1}{4}}}}&=0\\\오메가 ^{\frac {2^{p}-1+1}{4}}}+{\bar {\omega}^{\frac {2^{p}-1+1}{4}}}}&=0\\\오메가^{2^{p-2}}+{\bar {\omega}}^{2^{p-2}}&=0\s_{p-2}&=0.\end{정렬}}}$

$s{\displaystyle {}_{}}$ ${\displaystyle p_{}}$- ${\displaystyle 2_{}}$ ${\$은 X에서 0이므로$$ 0 modulo ${\displaystyle M_{}}$ ${\displaystyle M_{p}$이기도 하다.$}$

적용들

더 루카스-레머 테스트는 그레이트 인터넷 메르센 프라임 서치(GIMPS)가 대형 프리마임을 찾기 위해 사용하는 주요 프라이마리티 테스트 중 하나이다.이 검색은 현재까지 알려진 가장 큰 프리타임 중 많은 부분을 찾아내는 데 성공했다.^[9]이 테스트는 아마도 많은 수의 매우 많은 수의 매우 많은 수의 원시성을 적절한 시간 내에 테스트할 수 있기 때문에 가치 있는 것으로 간주된다.이와는 대조적으로, 페르마 숫자에 대한 동등하게 빠른 Pépin의 테스트는 계산 한계에 도달하기 전에 훨씬 더 작은 수의 매우 큰 숫자 집합에만 사용할 수 있다.

참고 항목

• 메르센의 추측
• 루카스-레머-리젤 시험

메모들

참조

• Crandall, Richard; Pomerance, Carl (2001), "Section 4.2.1: The Lucas–Lehmer test", Prime Numbers: A Computational Perspective (1st ed.), Berlin: Springer, p. 167–170, ISBN 0-387-94777-9

외부 링크

• Weisstein, Eric W. "Lucas–Lehmer test". MathWorld.
• 김프스(The Great Internet Merssenne Prime Search)
• 루카스의 증거Lehmer-Rix 검정(페르마트 수)
• 루카스-레머 테스트위키