En la teoría computacional de números , la prueba de Lucas es una prueba de primalidad para un número natural n ; requiere que ya se conozcan los factores primos de n - 1. [1] [2] Es la base del certificado de Pratt que proporciona una verificación concisa de que n es primo.
Conceptos
Sea n un número entero positivo. Si existe un número entero a , 1 < a < n , tal que
y para cada factor primo q de n - 1
entonces n es primo. Si no existe tal número a , entonces n es 1, 2 o compuesto .
La razón de la exactitud de esta afirmación es la siguiente: si la primera equivalencia se cumple para a , podemos deducir que a y n son coprimos . Si a también sobrevive al segundo paso, entonces el orden de a en el grupo ( Z / n Z ) * es igual an −1, lo que significa que el orden de ese grupo es n −1 (porque el orden de cada elemento de un grupo divide el orden del grupo), lo que implica que n es primo . Por el contrario, si n es primo, entonces existe una raíz primitiva módulo n , o generador del grupo ( Z / n Z ) *. Tal generador tiene el orden | ( Z / n Z ) * | = n −1 y ambas equivalencias se mantendrán para cualquier raíz primitiva.
Tenga en cuenta que si existe un a < n tal que la primera equivalencia falla, a se denomina testigo de Fermat de la composición de n .
Ejemplo
Por ejemplo, tome n = 71. Entonces n - 1 = 70 y los factores primos de 70 son 2, 5 y 7. Seleccionamos aleatoriamente an a = 17 < n . Ahora calculamos:
Para todos los enteros a se sabe que
Por lo tanto, el orden multiplicativo de 17 (mod 71) no es necesariamente 70 porque algún factor de 70 también puede funcionar arriba. Así que marque 70 dividido por sus factores primos:
Desafortunadamente, obtenemos que 17 10 ≡1 (mod 71). Así que todavía no sabemos si 71 es primo o no.
Tratamos otra al azar una , esta vez la elección de un = 11. Ahora calculamos:
Nuevamente, esto no muestra que el orden multiplicativo de 11 (mod 71) sea 70 porque algún factor de 70 también puede funcionar. Así que marque 70 dividido por sus factores primos:
Entonces, el orden multiplicativo de 11 (mod 71) es 70, y por lo tanto 71 es primo.
(Para llevar a cabo estas exponenciaciones modulares , se podría usar un algoritmo de exponenciación rápida como exponenciación binaria o de cadena de suma ).
Algoritmo
El algoritmo se puede escribir en pseudocódigo de la siguiente manera:
algoritmo lucas_primality_test es entrada : n > 2, un número entero impar someterse a ensayo de primalidad. k , un parámetro que determina la precisión de la prueba. salida : primo si n es primo, de lo contrario compuesto o posiblemente compuesto . determinar los factores primos de n −1. LOOP1: repite k veces: elegir al azar en el rango [2, n - 1] si luego devuelve composite else # LOOP2: para todos los factores primos q de n −1: si entonces, si verificamos esta igualdad para todos los factores primos de n −1 , devuelva primo si no continúa LOOP2 si no # continuar LOOP1 retorno posiblemente compuesto .
Ver también
- Édouard Lucas , que da nombre a esta prueba
- El pequeño teorema de Fermat
- Prueba de primalidad de Pocklington , una versión mejorada de esta prueba que solo requiere una factorización parcial de n - 1
- Certificado de primacía
Notas
- ^ Crandall, Richard; Pomerance, Carl (2005). Números primos: una perspectiva computacional (2ª edición) . Saltador. pag. 173. ISBN 0-387-25282-7.
- ^ Křížek, Michal; Luca, Florian; Somer, Lawrence (2001). 17 Conferencias sobre los números de Fermat: de la teoría de los números a la geometría . Libros CMS en Matemáticas. 9 . Sociedad Matemática Canadiense / Springer. pag. 41. ISBN 0-387-95332-9.