Prueba de primalidad

ImprimirCitar

Algoritmo para determinar si un número es primo

Una prueba de primalidad es un algoritmo para determinar si un número de entrada es primo. Entre otros campos de las matemáticas, se utiliza para la criptografía. A diferencia de la factorización de enteros, las pruebas de primalidad generalmente no dan factores primos, solo indican si el número de entrada es primo o no. Se cree que la factorización es un problema computacionalmente difícil, mientras que la prueba de primalidad es comparativamente fácil (su tiempo de ejecución es polinomial en el tamaño de la entrada). Algunas pruebas de primalidad prueban que un número es primo, mientras que otras como Miller-Rabin prueban que un número es compuesto. Por lo tanto, estas últimas podrían denominarse con mayor precisión pruebas de composición en lugar de pruebas de primalidad.

Métodos simples

La prueba de primalidad más simple es División de Primera Instancia: dado un número de entrada, n, comprobar si es uniformemente divisible por cualquier número primo entre 2 y √n (es decir, que la división no deja ningún resto). Si es así, entonces n es composite. De lo contrario, es genial. De hecho, para cualquier divisor ${sqrt {n}}}" xmlns="http://www.w3.org/1998/Math/MathML">p■n{displaystyle p confía{sqrt {n}}{sqrt {n}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/012a3e4052283dfa3fdd34e09c9b51b04331bd45" style="vertical-align: -1.005ex; margin-left: -0.089ex; width:7.688ex; height:3.009ex;"/>$ , debe haber otro divisor $<math alttext="{displaystyle n/pn/p.n{displaystyle No. <img alt="{displaystyle n/p$ , y por lo tanto buscando divisores más pequeños que √n es suficiente.

Por ejemplo, considere el número 100, que es divisible por estos números:

2, 4, 5, 10, 20, 25, 50

Tenga en cuenta que el factor más grande, 50, es la mitad de 100. Esto es válido para todos los n: todos los divisores son menores o iguales que n/2.

Cuando se prueban todos los divisores posibles hasta n/2, algunos factores se descubrirán dos veces. Para observar esto, reescribe la lista de divisores como una lista de productos, cada uno igual a 100:

2 \times 50, 4 \times 25, 5 \times 20, 10 \times 10, 20 \times 5, 25 \times 4, 50 \times 2

Observe que los productos más allá de 10 × 10 simplemente repiten números que aparecieron en productos anteriores, simplemente conmutados. Por ejemplo, 5 × 20 y 20 × 5 consisten en los mismos números en orden opuesto. Esto es válido para todos los n: todos los divisores únicos de n son números menores o iguales que √n, por lo que no necesitamos buscar más allá de eso. (En este ejemplo, √n = √100 = 10.)

Todos los números pares mayores que 2 también se pueden eliminar: si un número par puede dividir a n, también lo puede hacer 2.

Un ejemplo es utilizar la división de pruebas para probar la primalidad de 17. Sólo necesitamos pruebas para divisores hasta √n, es decir, números inferiores o iguales a ${displaystyle scriptstyle {sqrt {17}}approx 4.12}$ , a saber, 2, 3, y 4. 4 puede ser saltado porque es un número uniforme: si 4 podría dividir uniformemente 17, 2 también, y 2 ya está en la lista. Eso deja 2 y 3. Divide 17 con cada uno de estos números, y encontramos que ni divide 17 uniformemente, ninguna división deja un resto. Así que el 17 es el primero.

Este método puede mejorar aún más. Observe que todos los primos mayores de 3 son de la forma $6 k \pm 1$ , donde k es cualquier entero mayor que 0. Esto es porque todos los enteros se pueden expresar como $(66) k + i)$ , donde i = −1, 0, 1, 2, 3, o 4. $(66) k + 0), (6 k + 2), y (6) k + 4)$ y 3 divisiones $(66) k + 3)$ . Así que un método más eficiente es probar si n es divisible por 2 o 3, entonces para comprobar a través de todos los números del formulario ${displaystyle scriptstyle 6k pm 1leq {sqrt {n}}}$ . Esto es 3 veces más rápido que probar todos los números √n.

Generalizando aún más, todos los primos mayores que c# (c primorial) son de la forma c# · k + i , por i < c#, donde c y k son números enteros y i representa los números coprimos de c#. Por ejemplo, sea $c = 6$ . Entonces $c # = 2 \cdot 3 \cdot 5 = 30$ . Todos los números enteros tienen la forma $30 k + i$ para i en $i = 0, 1, 2,...,29$ y k un número entero. Sin embargo, 2 divide a 0, 2, 4,..., 28; 3 divide a 0, 3, 6,..., 27; y 5 divide a 0, 5, 10,..., 25. Así que todos los números primos mayores que 30 tienen la forma $30 k + i$ para $i = 1, 7, 11, 13, 17, 19, 23, 29$ (es decir, para $i < 30$ tal que $gcd(i,30) = 1$ ). Tenga en cuenta que si i y 30 no fueran coprimos, entonces $30 k + i$ sería divisible por un divisor primo de 30, es decir, 2, 3 o 5, y por lo tanto no sería primo. Para igualar el método anterior de permitir i negativa, en lugar de verificar cada i de 1 a c#-1 (porque 0 y c# siempre son pares), verifique cada i de 1 a c#</2, que será la lista de valores i tales que todos los enteros sean de la forma $c # k \pm i$ . En este ejemplo, $30 k \pm i$ para $i = 1, 7, 11, 13$ . Tenga en cuenta que esta lista siempre incluirá 1 y el conjunto de primos mayores que c pero menores que c#/2. No todos los números que cumplen las condiciones antes mencionadas son primos. Por ejemplo, 437 tiene la forma de c#k + i para c = 7, c#=210, k=2, i=17. Sin embargo, 437 es un número compuesto igual a 19*23. Es por eso que los números de la forma dada todavía necesitan ser probados por primalidad.

Como $c \to \infty$ , el número de valores que $c # k + i$ puede tomar dentro de un cierto rango disminuye, por lo que el tiempo para probar n disminuye. Para este método, también es necesario verificar la divisibilidad entre todos los números primos menores que c. Observaciones análogas a las anteriores pueden aplicarse recursivamente, dando la Tamiz de Eratóstenes.

Una forma de acelerar estos métodos (y todos los demás que se mencionan a continuación) es calcular previamente y almacenar una lista de todos los números primos hasta cierto límite, como todos los números primos hasta 200. (Dicha lista se puede calculado con la criba de Eratóstenes o mediante un algoritmo que compara cada m incremental con todos los números primos conocidos < √m). Entonces, antes de probar la primalidad de n con un método serio, primero se puede comprobar la divisibilidad de n por cualquier número primo de la lista. Si es divisible por cualquiera de esos números, entonces es compuesto y se pueden omitir otras pruebas.

Una prueba de primalidad simple pero muy ineficiente utiliza el teorema de Wilson, que establece que p es primo si y solo si:

(p-1)!equiv -1{pmod {p}},

Aunque este método requiere alrededor de p multiplicaciones modulares, lo que lo hace poco práctico, los teoremas sobre números primos y residuos modulares forman la base de muchos métodos más prácticos.

Código de ejemplo

Pitón

La siguiente es una prueba de primalidad simple en Python usando la optimización simple $6 k \pm 1$ mencionado anteriormente. Los métodos más sofisticados que se describen a continuación son mucho más rápidos para n grandes.

desde matemáticas importación isqrtdef is_prime()n: int) - bool: si n . 3: retorno n ■ 1 si n % 2 == 0 o n % 3 == 0: retorno Falso límite = isqrt()n) para i dentro rango()5, límite+1, 6): si n % i == 0 o n % ()i+2) == 0: retorno Falso retorno Cierto.

C, C++, C# & D

La siguiente es una prueba de primalidad en la familia de lenguajes C que utiliza la misma optimización que la anterior.

bool IsPrime()int n){} si ()n == 2 Silencio n == 3) retorno verdadero; si ()n . 1 Silencio n % 2 == 0 Silencio n % 3 == 0) retorno falso; para ()int i = 5; i * i . n; i += 6) {} si ()n % i == 0 Silencio n % ()i + 2) == 0) retorno falso; } retorno verdadero;}

Java

La siguiente es una prueba de primalidad en Java usando la misma optimización que la anterior.

importación Java.util. *;público estática boolean isPrime()int n){  si ()n . 1) retorno falso;  si ()n == 2 Silencio n == 3) retorno verdadero;  si ()n % 2 == 0 Silencio n % 3 == 0) retorno falso;  para ()int i = 5; i . Matemáticas.Sqrt()n); i = i + 6) si ()n % i == 0 Silencio n % ()i + 2) == 0) retorno falso; retorno verdadero; }

JavaScript

La siguiente es una prueba de primalidad en JavaScript usando la misma optimización que la anterior.

función isPrime()num) {} si ()num == 2 Silencio num == 3) retorno verdadero; si ()num . 1 Silencio num % 2 == 0 Silencio num % 3 == 0) retorno falso;  para ()Deja i = 5; i * i . num ; i+=6) si ()num % i == 0 Silencio num % ()i + 2) == 0) retorno falso; retorno verdadero;}

R

La siguiente es una prueba de primalidad en R (lenguaje de programación) usando la misma optimización que la anterior.

es. . función()Número) {} si ()Número . 1) {} retorno ()FALSE) } más si ()Número . 3) {} retorno ()TRUE) } si ()Número %% 2 == 0 Silencio Número %% 3 == 0) {} retorno ()FALSE) } i . 5 mientras ()i*i . Número) {} si ()Número %% i == 0 Silencio Número %% ()i+2) == 0) {} retorno ()FALSE) } i = i + 6 } retorno ()TRUE)}

Dardo

La siguiente es una prueba de primalidad en Dart (lenguaje_programación) usando la misma optimización que la anterior.

checkIfPrimeNumber()Número) {} si ()Número == 2 Silencio Número == 3) {} retorno 'verdad '; } más si ()Número . 1 Silencio Número % 2 == 0 Silencio Número % 3 == 0) {} retorno 'falso '; } para ()int i = 5; i * i . Número; i += 6) {} si ()Número % i == 0 Silencio Número % ()i + 2) == 0) {} retorno 'falso '; } } retorno 'verdad ';}

Pascal Libre

La siguiente es una prueba de primalidad en Free Pascal usando la misma optimización que la anterior.

función IsPrime()N:Integer):Boolean;Var I:Integer;comenzar si ()N = 2) o ()N = 3) entonces Exit()Cierto.); si ()N . 1) o ()N mod 2 = 0) o ()N mod 3 = 0) entonces Exit()Falso); I := 5; mientras ()I * I . N) do comenzar si ()N mod I = 0) o ()N mod ()I+2) = 0) entonces Exit()Falso); Inc()I, 6); final; Exit()Cierto.);final;

Ir

La siguiente es una prueba de primalidad en Golang que utiliza la misma optimización que la anterior.

func IsPrime()num int) bool {}si num ■ 1 " num . 3 {}retorno verdadero}si num . 1 Silencio num%2 == 0 Silencio num%3 == 0 {}retorno falso}para i := 5; i*i . num; i += 6 {}si num%i == 0 Silencio num%()i+2) == 0 {}retorno falso}}retorno verdadero}

Pruebas heurísticas

Estas son pruebas que parecen funcionar bien en la práctica, pero no están probadas y, por lo tanto, técnicamente hablando, no son algoritmos en absoluto. La prueba de Fermat y la prueba de Fibonacci son ejemplos simples y son muy efectivos cuando se combinan. John Selfridge ha conjeturado que si p es un número impar, y p ≡ ±2 (mod 5), entonces p será primo si ambos de la siguiente retención:

2^p−1 (modelo) p),
f_{p+ 1} (modelo) p),

donde f_k es el k-ésimo número de Fibonacci. La primera condición es la prueba de primalidad de Fermat en base 2.

En general, si p ≡ a (mod x²+4), donde a es a sin residuo cuadrático (mod x²+4), entonces p debería ser primo si se cumplen las siguientes condiciones:

2^p−1 (modelo) p),
f()1)_{p+ 1} (modelo) p),

f(x)_k es el k-ésimo polinomio de Fibonacci en x.

Selfridge, Carl Pomerance y Samuel Wagstaff juntos ofrecen $620 por un contraejemplo. El problema sigue abierto a partir del 11 de septiembre de 2015.

Pruebas probabilísticas

Las pruebas probabilísticas son más rigurosas que las heurísticas, ya que proporcionan límites comprobables sobre la probabilidad de ser engañado por un número compuesto. Muchas pruebas populares de primalidad son pruebas probabilísticas. Estas pruebas utilizan, además del número probado n, algunos otros números a que se eligen al azar de algún espacio muestral; las pruebas de primalidad aleatorias habituales nunca informan un número primo como compuesto, pero es posible que un número compuesto se informe como primo. La probabilidad de error se puede reducir repitiendo la prueba con varios valores de a elegidos de forma independiente; para dos pruebas de uso común, para cualquier compuesto n al menos la mitad de a's detectan n' s composición, por lo que k las repeticiones reducen la probabilidad de error a un máximo de 2^−k, que puede hacerse arbitrariamente pequeño aumentando k .

La estructura básica de las pruebas aleatorias de primalidad es la siguiente:

Aleatoriamente elegir un número a.
Comprobar la igualdad (correspondiendo a la prueba elegida) implicando a y el número dado n. Si la igualdad no se mantiene fiel, entonces n es un número compuesto y a es un testigo para la composibilidad, y la prueba para.
Regrese al primer paso hasta que se alcance la precisión necesaria.

Después de una o más iteraciones, si n no se encuentra como un número compuesto, entonces puede declararse probablemente primo.

Prueba de primalidad de Fermat

La prueba de primalidad probabilística más simple es la prueba de primalidad de Fermat (en realidad, una prueba de composición). Funciona de la siguiente manera:

Dado un entero n, elegir un número entero a coprime n y calcular aⁿ^{− 1} modulo n. Si el resultado es diferente de 1, entonces n es composite. Si es 1, entonces n puede ser la primera.

Si aⁿ⁻¹ (módulo n) es 1 pero n no es primo, entonces n se llama un pseudoprimo a base a. En la práctica, observamos que, si aⁿ⁻¹ (módulo n) es 1, entonces n suele ser primo. Pero aquí hay un contraejemplo: si n = 341 y a = 2, entonces

2^{340}equiv 1{pmod {341}}

aunque 341 = 11·31 es compuesto. De hecho, 341 es la base 2 pseudoprima más pequeña (ver Figura 1 de ).

Solo hay 21853 pseudoprimos en base 2 que tienen menos de 2,5×10¹⁰ (ver página 1005 de). Esto significa que, para n hasta 2,5×10¹⁰, si 2ⁿ⁻¹ (módulo n) es igual a 1, entonces n es primo, a menos que n sea uno de estos 21853 pseudoprimos.

Algunos números compuestos (números de Carmichael) tienen la propiedad de que aⁿ^{− 1} es 1 (módulo n) para cada a que es coprimo de n. El ejemplo más pequeño es n = 561 = 3·11·17, para el cual a⁵⁶⁰ es 1 (módulo 561) para todo a coprime a 561. Sin embargo, la prueba de Fermat se usa a menudo si se necesita una detección rápida de números, por ejemplo, en la fase de generación de claves del algoritmo criptográfico de clave pública RSA.

Prueba de primalidad de Miller-Rabin y Solovay-Strassen

La prueba de primalidad de Miller-Rabin y la prueba de primalidad de Solovay-Strassen son variantes más sofisticadas, que detectan todos los compuestos (una vez más, esto significa: para cada número compuesto n, al menos 3/4 (Miller–Rabin) o 1/2 (Solovay–Strassen) de los números a son testigos de la composición de n). Estas también son pruebas de composición.

La prueba de primalidad de Miller-Rabin funciona de la siguiente manera: Dado un entero n, elige algún entero positivo a < n. Sea 2^sd = n − 1, donde d es impar. Si

{displaystyle a^{d}not equiv pm 1{pmod {n}}}

a^{2^{r}d}not equiv -1{pmod {n}}

para todos

{displaystyle 0leq rleq s-1,}

entonces n es compuesto y a es un testigo de la composición. De lo contrario, n puede o no ser primo. La prueba de Miller-Rabin es una prueba principal probable fuerte (consulte la página 1004 de PSW).

La prueba de primalidad de Solovay-Strassen usa otra igualdad: Dado un número impar n, elige algún número entero a < n, si

a^{(n-1)/2}not equiv left({frac {a}{n}}right){pmod {n}}

, donde

left({frac {a}{n}}right)

es el símbolo Jacobi,

entonces n es compuesto y a es un testigo de la composición. De lo contrario, n puede o no ser primo. La prueba de Solovay-Strassen es una prueba de primos probables de Euler (consulte la página 1003 de PSW).

Para cada valor individual de a, la prueba de Solovay-Strassen es más débil que la prueba de Miller-Rabin. Por ejemplo, si n = 1905 y a = 2, la prueba de Miller-Rabin muestra que n es compuesto, pero Solovay–Strassen la prueba no lo hace. Esto se debe a que 1905 es un Euler base pseudoprima 2 pero no una fuerte base pseudoprima 2 (esto se ilustra en la Figura 1 de PSW).

Prueba de primalidad de Frobenius

Las pruebas de primalidad de Miller-Rabin y Solovay-Strassen son simples y mucho más rápidas que otras pruebas de primalidad generales. Un método para mejorar aún más la eficiencia en algunos casos es la prueba de pseudoprimalidad de Frobenius; una ronda de esta prueba dura aproximadamente tres veces más que una ronda de Miller-Rabin, pero logra un límite de probabilidad comparable a siete rondas de Miller-Rabin.

La prueba de Frobenius es una generalización de la prueba de los primos probables de Lucas.

Prueba de primalidad de Baillie-PSW

La prueba de primalidad de Baillie-PSW es una prueba de primalidad probabilística que combina una prueba de Fermat o Miller-Rabin con una prueba de Lucas probable para obtener una prueba de primalidad que no tiene contraexamples conocidos. Es decir, no hay un compuesto conocido n para el cual esta prueba reporta que n Probablemente sea la primera. Se ha demostrado que no hay contraexamples para n $<math alttext="{displaystyle .264{displaystyle] <img alt="{displaystyle$ .

Otras pruebas

Leonard Adleman y Ming-Deh Huang presentaron una variante sin errores (pero en tiempo polinomial esperado) de la prueba de primalidad de la curva elíptica. A diferencia de otras pruebas probabilísticas, este algoritmo produce un certificado de primalidad y, por lo tanto, puede usarse para probar que un número es primo. El algoritmo es prohibitivamente lento en la práctica.

Si hay computadoras cuánticas disponibles, la primalidad podría ser probada asintotically más rápido que usando computadoras clásicas. Una combinación del algoritmo de Shor, un método de factorización entero, con la prueba de primalidad de Pocklington podría resolver el problema en ${displaystyle O((log n)^{3}(log log n)^{2}log log log n)}$ .

Pruebas deterministas rápidas

Cerca de principios del siglo XX, se demostró que un corolario del pequeño teorema de Fermat podría usarse para probar la primalidad. Esto resultó en la prueba de primalidad de Pocklington. Sin embargo, como esta prueba requiere una factorización parcial de n − 1, el tiempo de ejecución fue bastante lento en el peor de los casos. La primera prueba de primalidad determinista significativamente más rápida que los métodos ingenuos fue la prueba de ciclotomía; se puede demostrar que su tiempo de ejecución es O((log n)^{c log log log n}), donde n es el número para probar la primalidad y c es una constante independiente de n. Se realizaron muchas mejoras adicionales, pero no se pudo demostrar que ninguna tuviera un tiempo de ejecución polinomial. (Tenga en cuenta que el tiempo de ejecución se mide en términos del tamaño de la entrada, que en este caso es ~ log n, que es la cantidad de bits necesarios para representar el número n.) Se puede demostrar que la prueba de primalidad de la curva elíptica se ejecuta en O((log n)⁶), si algunas conjeturas sobre la teoría analítica de números son ciertas. De manera similar, bajo la hipótesis de Riemann generalizada, se puede demostrar que la prueba determinista de Miller, que forma la base de la prueba probabilística de Miller-Rabin, se ejecuta en Õ((log n)⁴). En la práctica, este algoritmo es más lento que los otros dos para tamaños de números que se pueden manejar. Debido a que la implementación de estos dos métodos es bastante difícil y crea un riesgo de errores de programación, a menudo se prefieren pruebas más lentas pero más simples.

En 2002, Manindra Agrawal, Neeraj Kayal y Nitin Saxena inventaron la primera prueba de tiempo polinomial determinista demostrablemente incondicional para primalidad. La prueba de primalidad de AKS se ejecuta en Õ((log n)¹²) (mejorado a Õ((log n)^7.5) en la revisión publicada de su artículo), que puede reducirse aún más a Õ((log n)⁶) si la conjetura de Sophie Germain es cierta. Posteriormente, Lenstra y Pomerance presentaron una versión de la prueba que se ejecuta en el tiempo Õ((log n)⁶) incondicionalmente.

Agrawal, Kayal y Saxena sugieren una variante de su algoritmo que se ejecutaría en Õ((log n)³) si la conjetura de Agrawal es cierta; sin embargo, un argumento heurístico de Hendrik Lenstra y Carl Pomerance sugiere que probablemente sea falso. Una versión modificada de la conjetura de Agrawal, la conjetura de Agrawal-Popovych, aún puede ser cierta.

Complejidad

En la teoría de la complejidad computacional, el lenguaje formal correspondiente a los números primos se denomina PRIMOS. Es fácil demostrar que PRIMES está en Co-NP: su complemento COMPOSITES está en NP porque uno puede decidir la composición adivinando un factor de forma no determinista.

En 1975, Vaughan Pratt mostró que existía un certificado de primalidad que era verificable en tiempo polinomio, por lo que PRIMES estaba en NP, y por lo tanto en ${displaystyle {mathsf {NPcap coNP}}}$ . Ver certificado de primalidad para detalles.

El descubrimiento posterior de los algoritmos Solovay–Strassen y Miller–Rabin puso PRIMES en coRP. En 1992, el algoritmo Adleman-Huang redujo la complejidad a ${displaystyle {mathsf {{color {Blue}ZPP}=RPcap coRP}}}$ , que superó el resultado de Pratt.

La prueba de primalidad de Adleman-Pomerance-Rumely de 1983 situó a PRIMES en QP (tiempo cuasi-polinomial), que no se sabe que sea comparable con las clases mencionadas anteriormente.

Debido a su manejabilidad en la práctica, los algoritmos de tiempo polinomial que asumen la hipótesis de Riemann y otras pruebas similares, durante mucho tiempo se sospechó, pero no se probó, que la primalidad podría resolverse en tiempo polinomial. La existencia de la prueba de primalidad AKS finalmente resolvió esta cuestión de larga data y colocó PRIMES en P. Sin embargo, no se sabe que PRIMES sea P-completo, y no se sabe si se encuentra en clases que se encuentran dentro de P, como NC o L. Se sabe que PRIMES no está en AC0.

Métodos de teoría de números

Existen ciertos métodos teóricos de números para probar si un número es primo, como la prueba de Lucas y la prueba de Proth. Estas pruebas generalmente requieren la factorización de n + 1, n − 1, o una cantidad similar, lo que significa que no son útiles para las pruebas de primalidad de propósito general, pero son a menudo bastante poderoso cuando se sabe que el número probado n tiene una forma especial.

La prueba de Lucas se basa en el hecho de que el orden multiplicativo de un número a módulo n es n − 1 para un primo n cuando a es una raíz primitiva módulo n. Si podemos mostrar que a es primitivo para n, podemos mostrar que n es primo.

Contenido relacionado

Más resultados...