Prueba de simplicidad de Luke

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 7 de abril de 2021; la verificación requiere 1 edición .

En teoría de números , la prueba de primalidad de Lucas es la prueba de primalidad para un número natural n ; para que funcione, necesitas saber la factorización. Para un número primo n , los factores primos del número , junto con alguna base a , constituyen un certificado de Pratt , que permite probar en tiempo polinomial que n es primo. $n-1$ $n-1$

Descripción

Sea n > 1 un número natural. Si existe un entero a tal que y ${\ estilo de visualización 1<a<n}$

a^{n-1} \equiv 1 \pmod n

y para cualquier divisor primo q del número $n-1$

a^{\frac {n-1}{q}}\no \equiv 1{\pmod {n}}

entonces n es primo.

Si no existe tal número a , entonces n es un número compuesto .

Prueba

Si n es primo, entonces el grupo residuo es cíclico, es decir, tiene un generador cuyo orden coincide con el orden del grupo , lo que significa que para cualquier divisor primo del número , se realiza una comparación: $\mathbb {Z} _{n}$ $gramo$ $|\mathbb {Z} _{n}^{\times}|=n-1$ $q$ $n-1$

a^{\frac {n-1}{q}}\no \equiv 1{\pmod {n}}.

Si n es compuesto, entonces y luego , o . Si suponemos que para esto también se satisface a , entonces, dado que , encontramos que el grupo tiene un elemento de orden , significa que se divide , lo que contradice el hecho de que para el compuesto n . ${\text{mcd}}(a,n)>1$ $a^{n-1} \not\equiv 1 \pmod n$ $a^{n-1} \equiv 1 \pmod n$ $a^{\frac {n-1}{q}}\no \equiv 1{\pmod {n}}$ ${\frac{n-1}{q}}\mid n-1$ $\mathbb {Z} _{n}^{\veces}$ $n-1$ $|\mathbb {Z} _{n}^{\veces}|$ $n-1$ $|\mathbb {Z} _{n}^{\times}|=\varphi (n)<n-1$

De acuerdo con la ley de contraposición, obtenemos el criterio de Lucas.

Ejemplo

Por ejemplo, tomemos n = 71. Entonces . Elijamos al azar . Calculamos: $n-1=70=2\cdot 5\cdot 7$ ${\ estilo de visualización a = 17}$

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

Veamos las comparaciones para : $a^{\frac {n-1}{q}}\no \equiv 1{\pmod {n}}$ ${\ estilo de visualización q = 2; 5; 7}$

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

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

17^{10}\equiv 1\equiv 1{\pmod {71)).

Desafortunadamente _ Por lo tanto, todavía no podemos afirmar que 71 sea primo. $17^{10}\equiv 1\equiv 1{\pmod {71)).$

Probemos con otro número aleatorio a , elige . Calculamos: ${\ estilo de visualización a = 11}$

11^{70}\equiv 1{\pmod {71)).

Nuevamente verifique las comparaciones para : $a^{\frac {n-1}{q}}\no \equiv 1{\pmod {n}}$ ${\ estilo de visualización q = 2; 5; 7}$

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

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

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

Por lo tanto, 71 son primos.

Tenga en cuenta que para el cálculo rápido del módulo de exponentes, se utiliza el algoritmo de exponenciación binaria tomando el resto módulo n después de cada multiplicación.

Nótese también que para un n simple , se sigue de la hipótesis de Riemann generalizada que entre los primeros números hay al menos un generador del grupo , por lo que se puede argumentar condicionalmente que la base a se puede encontrar en tiempo polinomial. ${\ estilo de visualización O (\ ln ^ {2} n)}$ $\mathbb {Z} _{n}$

Algoritmo

El algoritmo, escrito en pseudocódigo , es el siguiente:

Entrada : n > 2 es un número impar que se está probando para primalidad; k - un parámetro que determina la precisión de la prueba Conclusión : simple si n es primo, de lo contrario compuesto o posiblemente compuesto ; Definimos todos los divisores primos .

n-1

Loop1: elige aleatoriamente a del intervalo [2, n − 1] Si devuelve un compuesto

a^{n-1} \not\equiv 1 \pmod n

De lo contrario Loop2: Para todos los números primos :

{\ estilo de visualización q \ mid n-1}

Si Si no verificamos la comparación para todos

a^{\frac {n-1}{q}}\no \equiv 1{\pmod {n}}

q

luego continuamos ejecutando Loop2 de lo contrario, devuelve un simple De lo contrario, regrese a Loop1 Es posible devolver un compuesto .

Véase también

Prueba de simplicidad

Literatura

Vasilenko O. N. Algoritmos teóricos de números en criptografía, MTsNMO, 2003
Trost E. - Primzahlen / Números primos - M .: GIFML, 1959, 135 s

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin