Test de Lucas-Lehmer

Test de Lucas-Lehmer

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.

Contenido

El test

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.

Con una implementación FFT, el test de Lucas–Lehmer tiene una complejidad de O(n2 log n), donde n es la longitud del número.

Véase también

Referencias

  • Richard Crandall y Carl Pomerance (2001). Prime Numbers: A Computational Perspective (1era edición edición). Springer. ISBN 0-387-94777-9.  Section 4.2.1: The Lucas–Lehmer test, pp.167–170.

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Test de primalite de Lucas-Lehmer pour les nombres de Mersenne — Test de primalité de Lucas Lehmer pour les nombres de Mersenne En mathématiques, le test de Lucas Lehmer est un test de primalité pour les nombres de Mersenne. Le test fut originellement développé par Édouard Lucas en 1878 et amélioré de façon… …   Wikipédia en Français

  • Test de primalité de lucas-lehmer pour les nombres de mersenne — En mathématiques, le test de Lucas Lehmer est un test de primalité pour les nombres de Mersenne. Le test fut originellement développé par Édouard Lucas en 1878 et amélioré de façon notable par Derrick Henry Lehmer dans les années 1930. Le test Le …   Wikipédia en Français

  • Lucas–Lehmer test for Mersenne numbers — This article is about the Lucas–Lehmer test (LLT), that only applies to Mersenne numbers. There is also a Lucas Lehmer Riesel test for numbers of the form N=k 2^n 1, with 2^n > k, based on the LLT: see Lucas Lehmer Riesel test. There is also a… …   Wikipedia

  • Lucas-Lehmer Test — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Test de primalité de Lucas-Lehmer pour les nombres de Mersenne — Pour les articles homonymes, voir Lucas et Lehmer. En mathématiques, le test de Lucas Lehmer est un test de primalité pour les nombres de Mersenne. Le test fut originellement développé par Édouard Lucas en 1878 et amélioré de façon notable par… …   Wikipédia en Français

  • Test de Lucas — En teoría de números, el test de Lucas es un test de primalidad para un número natural n y requiere que los factores primos de n − 1 sean conocidos. Si existe un número natural a menor que n y mayor que 1 que verifica las condiciones así como… …   Wikipedia Español

  • Test de primalite de Lucas-Lehmer — Test de primalité de Lucas Lehmer Le test de primalité de Lucas Lehmer est une méthode pour tester la primalité de certains nombres n ; il requiert que les facteurs premiers de n 1 soient connus. S il existe un a inférieur à n et plus grand… …   Wikipédia en Français

  • Test de primalité de lucas-lehmer — Le test de primalité de Lucas Lehmer est une méthode pour tester la primalité de certains nombres n ; il requiert que les facteurs premiers de n 1 soient connus. S il existe un a inférieur à n et plus grand que 1 tel que et, pour tous les… …   Wikipédia en Français

  • Lucas-Lehmer-Test — Ausschnitt von Seite 316 der Arbeit Théorie des Fonctions Numériques Simplement Périodiques von Édouard Lucas (1878) Der Lucas Lehmer Test ist ein Primzahltest für Mersenne Zahlen, das heißt für Zahlen der Form Mn = 2n − 1. Der Test wird im GIMPS …   Deutsch Wikipedia

  • Lucas-Lehmer-Riesel test — The Lucas Lehmer Riesel test is a primality test for numbers of the form N=k 2^n 1, with 2^n > k. The test was developed by Hans Riesel and it is based on the Lucas–Lehmer test for Mersenne numbers.The algorithmThe algorithm is very similar to… …   Wikipedia

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”