卢卡斯-莱默检验法

数学中，卢卡斯-莱默检验法是检验梅森数的素性检验法，是由爱德华·卢卡斯于1878年完善，德里克·亨利·莱默随后于1930年代将其改进。

[编辑] 方法

卢卡斯－莱默检验法原理是这样：令梅森数 M_p = 2^p− 1 作为检验对象（预设p是素数, 否则M_p 就是合数了)。定义一个序列 {s_i} 所有的i ≥ 0

$s_i= \left\{ \begin{matrix} 4,\qquad\ \,&&\mbox{if }i=0;\ \ \, \\ s_{i-1}^2-2&&\mbox{otherwise.} \end{matrix} \right.$

这个序列的开始几项是4, 14, 194, 37634, ... 那么M_p 是素数当且仅当

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

否则, M_p 是合数。数 s_{p − 2} mod M_p 叫做卢卡斯－莱默余数的p。

[编辑] 参见

卢卡斯-莱默素性检验法

来自“http://www.wikilib.com/wiki/%E5%8D%A2%E5%8D%A1%E6%96%AF-%E8%8E%B1%E9%BB%98%E6%A3%80%E9%AA%8C%E6%B3%95”

1个分类: 数论