Test de Lucas-Lehmer

Archiu:LucasTheorieDesFonctions1878.png

Fragment en francés del Test de Lucas-Lehmer.

En matemàtiques, la prova de Lucas-Lehmer és una prova que servix per a determinar si un determinat número de Mersenne M_p és primer. El test va ser desenrollat per Edouard Lucas en 1878 i subsecuentemente millorat per Derrick Henry Lehmer en la década de 1930.

El test

La prova de Lucas-Lehmer consistix en lo següent: siga M_p = 2^p− 1 el número de Mersenne a testear en p primer impar. Definixca's la successió {s_i} per a tot i ≥ 0 segons:

$s_i=\{\begin{array}{ccc}4,& & \text{si }i=0;\\ s_{i-1}^2-2& & \text{en caso contrario.}\end{array}$

Els primers térmens d'esta successió són 4, 14, 194, 37634, ... Plantilla:OEIS. Llavors, M_p és primer si i només si

$s_{p-2}\equiv 0(\mathrm{mod}{M}_p);$

En un atre cas, M_p és compost. El número s_{p − 2} mod M_p es diu residu Lucas–Lehmer de p.

Una implementació que utilise l'algoritme de multiplicació ràpida de Schönhage–Strassen, basat a la seua volta en la transformada ràpida de Fourier, dona al test de Lucas–Lehmer una complexitat d'O(n² log n log log n), a on n és la llongitut del número.

Vore també

• Test de Lucas
• Conjectura de Mersenne

Referències

• Richard Crandall i Carl Pomerance (2001). Prime Numbers: A Computational Perspective, 1era edició edició, Springer. Section 4.2.1: The Lucas–Lehmer test, pp.167–170.