prueba de primalidad de lucas

En teoría computacional de números , la prueba de Lucas es una prueba de primalidad para un número natural n ; requiere que los factores primos de n − 1 ya se conozcan. ^{[1] [2]} Es la base del certificado 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

${\displaystyle a^{n-1}\ \equiv \ 1{\pmod {n}}\,}$

y para cada factor primo q de n  − 1

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

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 a n −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 un módulo raíz primitivo n , o generador del grupo ( Z / n Z )*. Tal generador tiene orden |( Z / n Z )*| =  n −1 y ambas equivalencias se cumplirá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 a =17  <  n . Ahora calculamos:

${\displaystyle 17^{70}\ \equiv \ 1{\pmod {71}}.}$

Para todos los números enteros a se sabe que

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}\ {\text{ if and only if }}{\text{ ord}}(a)|(n-1).}$

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. Entonces revisa 70 dividido por sus factores primos:

${\displaystyle 17^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 17^{14}\ \equiv \ 25\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 17^{10}\ \equiv \ 1\ \equiv \ 1{\pmod {71}}.}$

Desafortunadamente, obtenemos que 17 ¹⁰ ≡1 (mod 71). Entonces todavía no sabemos si 71 es primo o no.

Probamos con otro a aleatorio , esta vez eligiendo a  = 11. Ahora calculamos:

${\displaystyle 11^{70}\ \equiv \ 1{\pmod {71}}.}$

Nuevamente, esto no muestra que el orden multiplicativo de 11 (mod 71) sea 70 porque algún factor de 70 también puede funcionar. Entonces revisa 70 dividido por sus factores primos:

${\displaystyle 11^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 11^{14}\ \equiv \ 54\ \not \equiv \ 1{\pmod {71}}}$

${\displaystyle 11^{10}\ \equiv \ 32\ \not \equiv \ 1{\pmod {71}}.}$

Entonces, el orden multiplicativo de 11 (mod 71) es 70 y, por tanto, 71 es primo.

(Para llevar a cabo estas exponenciaciones modulares , se podría utilizar un algoritmo de exponenciación rápida como la exponenciación binaria o de cadena de suma ).

Algoritmo

El algoritmo se puede escribir en pseudocódigo de la siguiente manera:

Se  ingresa el algoritmo lucas_primality_test : n > 2, un entero impar que se probará para determinar la primalidad. k , un parámetro que determina la precisión de la prueba. salida : primo si n es primo; en caso contrario, compuesto o posiblemente compuesto . determine los factores primos de n −1. LOOP1: repetir  k veces: elija un aleatoriamente en el rango [2, n − 1] si  luego ${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$   devuelva  compuesto  else  #  ${\displaystyle \color {Gray}{a^{n-1}\equiv 1{\pmod {n}}}}$ LOOP2: para todos los factores primos q de n −1: si  entonces ${\displaystyle a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}}$   si comprobamos esta igualdad para todos los factores primos de n −1 entonces  devuelva  primo  else  continuar LOOP2 más  # continuar LOOP1  ${\displaystyle \color {Gray}{a^{\frac {n-1}{q}}\equiv 1{\pmod {n}}}}$  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 sólo requiere una factorización parcial de n  − 1
• certificado de primalidad

Notas

1. Crandall, Richard; Pomerancia, Carl (2005). Números primos: una perspectiva computacional (2ª ed.). Saltador. pag. 173.ISBN​ 0-387-25282-7.
2. Křížek, Michal; Luca, Florián; Somer, Lorenzo (2001). 17 conferencias sobre números de Fermat: de la teoría de números a la geometría . Libros CMS de Matemáticas. vol. 9. Sociedad Canadiense de Matemáticas/Springer. pag. 41.ISBN​ 0-387-95332-9.