Test de Lucas

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

a^{n-1}\ \equiv\ 1 \pmod n

así como

a^{({n-1})/q}\ \not\equiv\ 1 \pmod n

para todos los factores primos q de n − 1, entonces n es primo. Si no puede encontrarse tal a, entonces n es un número compuesto.

Por ejemplo, tómese n = 71. Entonces, n − 1 = 70 = (2)(5)(7). Tómese ahora a = 11. En primer lugar:

11^{70}\ \equiv\ 1 \pmod {71}

Esto no demuestra que el orden multiplicativo de 11 mod 71 es 70, porque algún factor de 70 aún podría funcionar arriba. Verificamos entonces 70 dividido por sus factores primos:

11^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71}
11^{14}\ \equiv\ 54\ \not\equiv\ 1 \pmod {71}
11^{10}\ \equiv\ 32\ \not\equiv\ 1 \pmod {71}

Entonces, el orden multiplicativo de 11 mod 71 es 70 y de esta manera, 71 es primo.

Para realizar estas potencias modulares debería usarse el método acelerado de exponenciación binaria.

Este algoritmo es correcto ya que si a pasa el primer paso, podemos deducir que a y n son coprimos. Si a también pasa el segundo paso, entonces el orden de a en el grupo (Z/nZ)* es igual a n − 1, lo que significa que el orden de ese grupo es n − 1, implicando que n es primo. Recíprocamente, si n es primo, entones existe una raíz primitiva módulo n y cualquier raíz primitiva pasará ambos pasos del algoritmo.

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • Test de lucas — Le test de Lucas permet de préciser l appartenance d un alcool à l une des trois classes d alcool. Sommaire 1 Déroulement 1.1 Préparation du réactif 1.2 Test 2 Exemple …   Wikipédia en Français

  • Test de Lucas — Le test de Lucas permet de préciser l appartenance d un alcool à l une des trois classes d alcool. Sommaire 1 Déroulement 1.1 Préparation du réactif 1.2 Test 2 Exemple …   Wikipédia en Français

  • 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… …   Wikipedia Español

  • 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-Test — bezeichnet: Lucas Test (Mathematik), ein Primzahlentest in der Mathematik Lucas Probe, eine Probe zur Unterscheidung verschiedener Alkohole in der Chemie Diese Seite ist eine Begriffsklärung zur Unterscheidung mehrerer mi …   Deutsch Wikipedia

  • Test de primalite — Test de primalité Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier. Sommaire 1 Méthode naïve 2 Tests probabilistes 3 Tests déterministes rapides …   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 primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n …   Wikipedia Español

Compartir el artículo y extractos

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