# 卢卡斯-莱默检验法

## 方法

 $s_i =\begin{cases}\;\;\,4 \\s_{i-1}^2-2 \end{cases}$ ，如果 $\displaystyle i = 0$； ，如果 $\displaystyle i > 0$。
.
.
.

$s_{p-2}\equiv0\pmod{M_p};$

## 例子

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

• 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 = \omega^{2^0} + \bar{\omega}^{2^0} = (2 + \sqrt{3}) + (2 - \sqrt{3}) = 4.$
$\begin{array}{lcl}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{array}$

### 充分性

$\begin{array}{rcl} \omega^{2^{p-2}} & = & kM_p - \bar{\omega}^{2^{p-2}} \\ \left(\omega^{2^{p-2}}\right)^2 & = & kM_p\omega^{2^{p-2}} - (\omega\bar{\omega})^{2^{p-2}} \\ \omega^{2^{p-1}} & = & kM_p\omega^{2^{p-2}} - 1.\quad\quad\quad\quad\quad(1) \\ \end{array}$

$(a + b\sqrt{3})(c + d\sqrt{3}) = [(ac + 3bd) \hbox{ mod } q] + [(bc + ad) \hbox{ mod } q]\sqrt{3}$.

### 必要性

$3^{(M_p-1)/2} \equiv -1 \pmod{M_p}$.

$2^{(M_p-1)/2} \equiv 1 \pmod{M_p}$.

$(x+y)^{M_p} \equiv x^{M_p} + y^{M_p} \pmod{M_p}$

（根据费马小定理），以及

$a^{M_p} \equiv a \pmod{M_p}$

$\begin{array}{lcl} (6+\sigma)^{M_p} & = & 6^{M_p} + (2^{M_p})(\sqrt{3}^{M_p}) \\ & = & 6 + 2(3^{(M_p-1)/2})\sqrt{3} \\ & = & 6 + 2(-1)\sqrt{3} \\ & = & 6 - \sigma. \end{array}$

$\begin{array}{lcl} \omega^{(M_p+1)/2} & = & (6 + \sigma)^{M_p+1}/24^{(M_p+1)/2} \\ & = & (6 + \sigma)^{M_p}(6 + \sigma)/(24 \times 24^{(M_p-1)/2}) \\ & = & (6 - \sigma)(6 + \sigma)/(-24) \\ & = & -1. \end{array}$

$24^{(M_p-1)/2} = (2^{(M_p-1)/2})^3(3^{(M_p-1)/2}) = (1)^3(-1) = -1.$

$\begin{array}{rcl} \omega^{(M_p+1)/2}\bar{\omega}^{(M_p+1)/4} & = & -\bar{\omega}^{(M_p+1)/4} \\ \omega^{(M_p+1)/4} + \bar{\omega}^{(M_p+1)/4} & = & 0 \\ \omega^{(2^p-1+1)/4} + \bar{\omega}^{(2^p-1+1)/4} & = & 0 \\ \omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} & = & 0 \\ s_{p-2} & = & 0. \\ \end{array}$

## 注释

1. ^ GIMPS Home Page. Frequently Asked Questions: General Questions: What are Mersenne primes? How are they useful? http://www.mersenne.org/faq.htm#what
2. ^ J. W. Bruce. A Really Trivial Proof of the Lucas-Lehmer Test. The American Mathematical Monthly, Vol.100, No.4, pp.370–371. April 1993.
3. ^ Öystein J. R. Ödseth. A note on primality tests for N = h · 2n − 1. Department of Mathematics, University of Bergen. http://www.uib.no/People/nmaoy/papers/luc.pdf