Test de Lucas-Lehmer

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En matemáticas, la prueba de Lucas-Lehmer es una prueba que sirve para determinar si un determinado número de Mersenne Mp es primo. El test fue desarrollado por Edouard Lucas en 1878 y subsecuentemente mejorado por Derrick Henry Lehmer en la década de 1930.

El test[editar]

La prueba de Lucas-Lehmer consiste en lo siguiente: sea Mp = 2p− 1 el número de Mersenne a testear con p primo. Defínase la sucesión {si} para todo i ≥ 0 según:


  s_i=
  \left\{
   \begin{matrix}
    4,\qquad\ \,&&\mbox{si }i=0;\ \ \,
   \\
    s_{i-1}^2-2&&\mbox{en caso contrario.}
   \end{matrix}
  \right.

Los primeros términos de esta sucesión son 4, 14, 194, 37634, ... (sucesión A003010 en OEIS). Entonces, Mp es primo si y sólo si

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

En otro caso, Mp es compuesto. El número sp − 2 mod Mp se llama residuo Lucas–Lehmer de p.

Una implementación que utilice el algoritmo de multiplicación rápida de Schönhage–Strassen, basado a su vez en la transformada rápida de Fourier, da al test de Lucas–Lehmer una complejidad de O(n2 log n log log n), donde n es la longitud del número.

Véase también[editar]

Referencias[editar]

Enlaces externos[editar]