Diferencia entre revisiones de «Test de Lucas»
m robot Añadido: ca, da, pl, ru, zh |
Deshecha la edición 26899500 de AstaBOTh15 (disc.) Enlaces incorrectos |
||
Línea 28: | Línea 28: | ||
[[Categoría:Tests de primalidad|Test de Lucas-Lehmer]] |
[[Categoría:Tests de primalidad|Test de Lucas-Lehmer]] |
||
[[ca:Prova de Lucas-Lehmer per a nombres de Mersenne]] |
|||
[[da:Lucas-Lehmer]] |
|||
[[de:Lucas-Test (Mathematik)]] |
[[de:Lucas-Test (Mathematik)]] |
||
[[en:Lucas primality test]] |
[[en:Lucas primality test]] |
||
Línea 36: | Línea 34: | ||
[[he:מבחן לוקאס-להמר]] |
[[he:מבחן לוקאס-להמר]] |
||
[[nl:Algemene Lucas-Lehmertest]] |
[[nl:Algemene Lucas-Lehmertest]] |
||
[[pl:Test Lucasa-Lehmera]] |
|||
[[ru:Тест Люка — Лемера]] |
|||
[[sv:Lucas-Lehmers test]] |
[[sv:Lucas-Lehmers test]] |
||
[[vi:Kiểm tra Lucas-Lehmer]] |
[[vi:Kiểm tra Lucas-Lehmer]] |
||
[[zh:卢卡斯-莱默检验法]] |
Revisión del 01:58 3 jun 2009
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
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:
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:
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.