Prueba de primalidad de Lucas - Lucas primality test

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 los factores primos de n - 1 ya sean conocidos. 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 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 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:

{\ Displaystyle 17 ^ {70} \ \ equiv \ 1 {\ pmod {71}}.}

Para todos los 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 porque algún factor de 70 también puede funcionar arriba. Así que marque 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). Así que todavía no sabemos si 71 es primo o no.

Intentamos otro aleatorio a , 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. Así que marque 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 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 adición ).

Algoritmo

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

algorithm lucas_primality_test is
    input: n > 2, an odd integer to be tested for primality.
           k, a parameter that determines the accuracy of the test.
    output: prime if n is prime, otherwise composite or possibly composite.

    determine the prime factors of n−1.

    LOOP1: repeat k times:
        pick a randomly in the range [2, n − 1]
            if  $a^{n-1}\not \equiv 1{\pmod {n}}$  then
                return composite
            else #  $\color {Gray}{a^{n-1}\equiv 1{\pmod {n}}}$ 
                LOOP2: for all prime factors q of n−1:
                    if  $a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}$  then
                        if we checked this equality for all prime factors of n−1 then
                            return prime
                        else
                            continue LOOP2
                    else #  $\color {Gray}{a^{\frac {n-1}{q}}\equiv 1{\pmod {n}}}$ 
                        continue LOOP1

    return possibly composite.