Prueba de primalidad de Lucas

En la teoría de números computacionales , la prueba de Lucas es una prueba de primalidad para un número natural n ; requiere que los factores primos de n − 1 ya sean conocidos. ^{[1] [2]} Es la base del certificado Pratt que da una verificación concisa de que n es primo.

Sea n un entero positivo. Si existe un 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}\ \no \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 corrección 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 una raíz primitiva módulo 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 de ese tipo.

Nótese que si existe un a  <  n tal que la primera equivalencia falla, a se denomina testigo de Fermat para la composición de n .

Por ejemplo, tomemos n = 71. Entonces n  − 1 = 70 y los factores primos de 70 son 2, 5 y 7. Seleccionamos aleatoriamente un 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{ si y solo si }}{\text{ ord}}(a)|(n-1).}$

Por lo tanto, el orden multiplicativo de 17 (mod 71) no es necesariamente 70, ya que algún factor de 70 también puede funcionar arriba. Por lo tanto, verifique 70 dividido por sus factores primos:

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

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

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

Lamentablemente, obtenemos que 17 ¹⁰ ≡1 (mod 71). Por lo tanto, aún no sabemos si 71 es primo o no.

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

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

Nuevamente, esto no demuestra que el orden multiplicativo de 11 (mod 71) sea 70, ya que algún factor de 70 también puede funcionar. Por lo tanto, verifique 70 dividido por sus factores primos:

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

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

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

Por lo tanto, 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 utilizar un algoritmo de exponenciación rápida como la exponenciación binaria o la exponenciación en cadena de adición ).

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

El algoritmo lucas_primality_test tiene 
    como entrada : n > 2, un entero impar que se va a probar para determinar su 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: repetir  k veces:
        elige un al azar en el rango [2, n − 1]
             si  entonces${\displaystyle a^{n-1}\no \equiv 1{\pmod {n}}}$ 
                 devuelve  compuesto 
            de lo contrario  # ${\displaystyle \color {Gris}{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}}\no \equiv 1{\pmod {n}}}$ 
                         si verificamos esta igualdad para todos los factores primos de n −1 entonces 
                            devuelve  primo 
                        de lo contrario 
                            continúa LOOP2
                     de lo contrario  # continúa LOOP1 ${\displaystyle \color {Gris}{a^{\frac {n-1}{q}}\equiv 1{\pmod {n}}}}$
                        

    devolver  posiblemente compuesto .

• Édouard Lucas , que dio 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 primalidad