prueba de primalidad

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 las pruebas de primalidad son comparativamente fáciles (su tiempo de ejecución es polinómico en el tamaño de la entrada). Algunas pruebas de primalidad demuestran que un número es primo, mientras que otras, como la de Miller-Rabin, demuestran 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 la división de prueba : dado un número de entrada, verifique si es divisible por algún número primo entre 2 y (es decir, si la división no deja resto ). Si es así, entonces es compuesto . De lo contrario, es primo. ^[1] Para cualquier divisor , debe haber otro divisor y un divisor primo de , por lo que buscar divisores primos como máximo es suficiente. ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle n}$ ${\displaystyle p\geq {\sqrt {n}}}$ ${\displaystyle n/p\leq {\sqrt {n}}}$ ${\displaystyle q}$ ${\displaystyle n/p}$ ${\displaystyle {\sqrt {n}}}$

Por ejemplo, considere el número 100, cuyos divisores son estos números:

1, 2, 4, 5, 10, 20, 25, 50, 100.

Cuando se prueban todos los divisores posibles hasta , algunos divisores se descubrirán dos veces . Para observar esto, considere la lista de pares de divisores de 100: ${\displaystyle n}$

${\displaystyle 1\times 100,\;2\times 50,\;4\times 25,\;5\times 20,\;10\times 10,\;20\times 5,\;25\times 4,\;50\times 2,\;100\times 1}$.

Los productos pasados ​​son el reverso de los productos que aparecieron antes. Por ejemplo, y son opuestos entre sí. Además, la de los dos divisores, y . Esta observación se generaliza a todos : todos los pares de divisores contienen un divisor menor o igual que , por lo que el algoritmo solo necesita buscar divisores menores o iguales para garantizar la detección de todos los pares de divisores. ^[1] ${\displaystyle 10\times 10}$ ${\displaystyle 5\times 20}$ ${\displaystyle 20\times 5}$ ${\displaystyle 5\leq {\sqrt {100}}=10}$ ${\displaystyle 20\geq {\sqrt {100}}=10}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle {\sqrt {n}}}$

Además, 2 es primo que divide a 100, lo que demuestra inmediatamente que 100 no es primo. Todo número entero positivo excepto 1 es divisible por al menos un número primo según el Teorema Fundamental de la Aritmética . Por lo tanto, el algoritmo sólo necesita buscar divisores primos menores o iguales a . ${\displaystyle {\sqrt {n}}}$

Para otro ejemplo, considere cómo este algoritmo determina la primalidad de 17. Uno tiene , y los únicos primos son 2 y 3. Ninguno divide a 17, lo que demuestra que 17 es primo. Como último ejemplo, considere 221. Se tiene , y los primos son 2, 3, 5, 7, 11 y 13. Al verificar cada uno, se descubre que , lo que demuestra que 221 no es primo. ${\displaystyle 4<{\sqrt {17}}<5}$ ${\displaystyle \leq {\sqrt {17}}}$ ${\displaystyle 14<{\sqrt {221}}<15}$ ${\displaystyle \leq {\sqrt {221}}}$ ${\displaystyle 221/13=17}$

En los casos en los que no es factible calcular la lista de números primos , también es posible verificar de manera simple (y lenta) todos los números entre y en busca de divisores. Una optimización bastante simple es probar la divisibilidad por 2 y solo por los números impares entre 3 y , ya que la divisibilidad por un número par implica divisibilidad por 2. ${\displaystyle \leq {\sqrt {n}}}$ ${\displaystyle 2}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle {\sqrt {n}}}$

Este método se puede mejorar aún más. Observe que todos los primos mayores que 3 tienen la forma de un número entero no negativo y . De hecho, cada número entero tiene la forma de un número entero positivo y . Dado que 2 divide a , y , y 3 divide a y , los únicos restos posibles mod 6 para un primo mayor que 3 son 1 y 5. Por lo tanto, una prueba de primalidad más eficiente es probar si es divisible por 2 o 3 y luego verificar a través de todos los números del formulario y cuáles son . Esto es casi tres veces más rápido que probar todos los números hasta . ${\displaystyle 6k+i}$ ${\displaystyle k}$ ${\displaystyle i\in \{1,5\}}$ ${\displaystyle 6k+i}$ ${\displaystyle k}$ ${\displaystyle i\in \{0,1,2,3,4,5\}}$ ${\displaystyle 6k,6k+2}$ ${\displaystyle 6k+4}$ ${\displaystyle 6k}$ ${\displaystyle 6k+3}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 6k+1}$ ${\displaystyle 6k+5}$ ${\displaystyle \leq {\sqrt {n}}}$ ${\displaystyle {\sqrt {n}}}$

Generalizando aún más, todos los primos mayores que ( c primorial ) tienen la forma de números enteros positivos, y coprimos de . Por ejemplo, considere . Todos los números enteros tienen la forma de números enteros con . Ahora, 2 divisiones , 3 divisiones y 5 divisiones . Por tanto, todos los números primos mayores que 30 tienen la forma for . Por supuesto, no todos los números de la forma coprimo to son primos. Por ejemplo, no es primo, aunque 17 es coprimo con respecto a . ${\displaystyle c\#}$ ${\displaystyle c\#\cdot k+i}$ ${\displaystyle i,k}$ ${\displaystyle 0\leq i<c\#}$ ${\displaystyle i}$ ${\displaystyle c\#}$ ${\displaystyle 6\#=2\cdot 3\cdot 5=30}$ ${\displaystyle 30k+i}$ ${\displaystyle i,k}$ ${\displaystyle 0\leq i<30}$ ${\displaystyle 0,2,4,\dots ,28}$ ${\displaystyle 0,3,6,\dots ,27}$ ${\displaystyle 0,5,10,\dots ,25}$ ${\displaystyle 30k+i}$ ${\displaystyle i\in \{1,7,11,13,17,19,23,29\}}$ ${\displaystyle c\#\cdot k+i}$ ${\displaystyle i}$ ${\displaystyle c\#}$ ${\displaystyle 19\cdot 23=437=210\cdot 2+17=2\cdot 7\#+17}$ ${\displaystyle 7\#=2\cdot 3\cdot 5\cdot 7}$

A medida que crece, la fracción de restos coprimos respecto de los restos disminuye, por lo que el tiempo para realizar la prueba disminuye (aunque todavía es necesario comprobar la divisibilidad entre todos los primos menores que ). Observaciones análogas a las anteriores pueden aplicarse recursivamente , dando la Criba de Eratóstenes . ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle c}$

Una forma de acelerar estos métodos (y todos los demás que se mencionan a continuación) es precalcular y almacenar una lista de todos los números primos hasta un límite determinado, como todos los números primos hasta 200. (Dicha lista se puede calcular con el Tamiz de Eratóstenes o mediante un algoritmo que compara cada incremental con todos los números primos conocidos ). Luego, antes de probar la primalidad con un método a gran escala, primero se puede verificar la divisibilidad de cualquier primo de la lista. Si es divisible por cualquiera de esos números, entonces es compuesto y se pueden omitir más pruebas. ${\displaystyle m}$ ${\displaystyle \leq {\sqrt {m}}}$ ${\displaystyle n}$ ${\displaystyle n}$

Una prueba de primalidad simple pero muy ineficiente utiliza el teorema de Wilson , que establece que es primo si y sólo si: ${\displaystyle p}$

${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$

Aunque este método requiere multiplicaciones modulares, lo que lo hace poco práctico, los teoremas sobre primos y residuos modulares forman la base de muchos métodos más prácticos. ${\displaystyle p}$

Código de ejemplo

Las pruebas de primalidad se pueden implementar de varias maneras. A continuación se muestran ejemplos en diferentes lenguajes de programación :

Pitón

Esta prueba se realiza en Python utilizando la optimización simple de 6 k ± 1 mencionada anteriormente. Los métodos más sofisticados que se describen a continuación son mucho más rápidos para n grandes .

desde  la importación matemática  isqrt def  is_prime ( n :  int )  ->  bool : si  norte  <=  3 : devolver  n  >  1 si  n  %  2  ==  0  o  n  %  3  ==  0 :  falso retorno límite  =  isqrt ( n ) para  i  en  el rango ( 5 ,  límite + 1 ,  6 ): si  n  %  i  ==  0  o  n  %  ( i + 2 )  ==  0 :  falso retorno devolver  verdadero

C, C++, C#, D

Esta prueba pertenece a la familia C de lenguajes entre llaves y utiliza la misma optimización que la anterior.

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

OCaml

Esta prueba se realiza en OCaml y utiliza la misma optimización que la anterior.

sea_prime  n =​   si  n  <=  1  entonces FALSO demás ( si  n  =  2  ||  n  =  3  entonces verdadero demás ( si  n  mod  2  =  0  ||  n  mod  3  =  0  entonces FALSO demás sea  ​​i  =  ref  5  en mientras  ! i  *  ! i  <=  n  &&  n  mod  ! i  <>  0  &&  n  mod  (! i  +  2 )  <>  0  hacer yo  :=  ! yo  +  6 hecho ; (! yo  *  ! yo  >  norte ) ) )

Óxido

Esta prueba se realiza en Rust utilizando la misma optimización que la anterior.

fn  is_prime ( n : i32 )  -> bool  { si n == 2 || norte == 3 {         devolver verdadero ;  } si n <= 1 || norte % 2 == 0 || norte % 3 == 0 {                 falso retorno ;  } ( 5 .. ) . paso a paso ( 6 ) . tomar_mientras ( | i | i * i <= n )      . todos ( | i | n % i != 0 && n % ( i + 2 ) != 0 )             }

Java

Esta prueba se realiza en Java utilizando la misma optimización que la anterior.

importar java.util.* ; booleano estático público esPrime ( int n ){      si ( n <= 1 )    falso retorno ;   si ( n == 2 || n == 3 )        devolver verdadero ;   si ( n % 2 == 0 || n % 3 == 0 )            falso retorno ;   para ( int i = 5 ; i <= Math . sqrt ( n ); i = i + 6 )             si ( n % i == 0 || n % ( i + 2 ) == 0 )              falso retorno ;  devolver verdadero ; }

javascript

Esta prueba está en JavaScript usando la misma optimización que la anterior.

la función esPrime ( núm ) {   si ( número == 2 || número == 3 )        devolver verdadero ;  si ( núm <= 1 || núm % 2 == 0 || núm % 3 == 0 )                falso retorno ;   para ( sea i = 5 ; i * i <= num ; i += 6 ) {             si ( núm % i == 0 || núm % ( i + 2 ) == 0 )              falso retorno ;  } devolver verdadero ; }

R

Esta prueba se realiza en R utilizando la misma optimización que la anterior.

es.prime <- función ( número ) {    si ( número <= 1 ) {    falso retorno )​ } más si ( número <= 3 ) {      devolver ( VERDADERO ) } si ( número %% 2 == 0 || número %% 3 == 0 ) {            falso retorno )​ } yo <- 5   mientras ( yo * yo <= número ) {    si ( número %% i == 0 || número %% ( i +2 ) == 0 ) {            falso retorno )​ } yo = yo + 6     } devolver ( VERDADERO )}

Dardo

Esta prueba se realiza en Dart utilizando la misma optimización que la anterior.

checkIfPrimeNumber ( número ) {  si ( número == 2 || número == 3 ) {         devolver 'verdadero' ;  } else if ( número <= 1 || número % 2 == 0 || número % 3 == 0 ) {                   falso retorno ' ;  } para ( int i = 5 ; i * i <= número ; i += 6 ) {              si ( número % i == 0 || número % ( i + 2 ) == 0 ) {               falso retorno ' ;  } } devolver 'verdadero' ; }

Pascal libre

Esta prueba se realiza en Free Pascal y utiliza la misma optimización que la anterior.

función IsPrime ( N : Int64 ) : booleana ;  var Yo : Int64 ; comenzar si (( N = 2 ) o ( N = 3 )) entonces         Salir ( Verdadero ) ; si (( N <= 1 ) o (( N mod 2 ) = 0 ) o (( N mod 3 ) = 0 )) entonces                 Salir ( Falso ) ; Yo := 5 ;   mientras ( I * I <= N ) hago       comenzar si (( N mod I ) = 0 ) o (( N mod ( I + 2 )) = 0 ) entonces               Salir ( Falso ) ; Inc ( I , 6 ) ;  fin ; Salir ( Verdadero ) ;fin ;

Ir

Esta prueba se realiza en Go utilizando la misma optimización que la anterior.

func IsPrime ( num int ) bool {    si número > 1 && número <= 3 {        devolver verdadero }si número <= 1 || número % 2 == 0 || número % 3 == 0 {            falso retorno }para yo := 5 ; yo * yo <= número ; yo += 6 {          si núm % i == 0 || número % ( yo + 2 ) == 0 {        falso retorno }}devolver verdadero }

Haskell

Esta prueba se realiza en Haskell utilizando la misma optimización que la anterior.

isPrime :: Int -> Booleano    isPrime = ir $ 2 : 3 : scanl ( + ) 5 ( ciclo [ 2 , 4 ])              dónde ir ( p : ps ) norte   | p * p > n = Verdadero        | n ` mod ` p == 0 = Falso        | de lo contrario = ir ps n     

Expresión regular

El método simple también se puede realizar usando una expresión regular generando una cadena de n caracteres idénticos y ejecutando una expresión del formulario:

/^.?$|^(..+?)\1+$/

Si la expresión coincide, el número no es primo.

La expresión consta de dos ramas:

• La primera rama coincide con 0 y 1.
• La segunda rama comprobará si existe alguna secuencia de 2 o más caracteres que se repita un número entero de veces, comenzando por la secuencia más pequeña y avanzando. (El cuantificador +?es un cuantificador diferido , lo que significa que intentará hacer coincidir la menor cantidad de caracteres posible y solo aumentará el tamaño si no se encuentra ninguna coincidencia usando ese valor).

Si bien se trata de una verificación compacta, ejecuta la versión menos eficiente en la que se verifican todos los divisores posibles de 2 a n , sin detenerse en . ${\displaystyle {\sqrt {n}}}$

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 sencillos y muy eficaces 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 se cumplen las dos condiciones siguientes:

• 2 ^{p −1} ≡ 1 (mod p ),
• f _{p +1} ≡ 0 (mod p ),

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

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

• 2 ^{p −1} ≡ 1 (mod p ),
• f ( 1 ) _{p +1} ≡ 0 (mod p ),

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

Selfridge, Carl Pomerance y Samuel Wagstaff ofrecen juntos 620 dólares por un contraejemplo. ^[2]

Pruebas probabilísticas

Las pruebas probabilísticas son más rigurosas que las heurísticas porque proporcionan límites demostrables sobre la probabilidad de ser engañado por un número compuesto. Muchas pruebas de primalidad populares 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 independientemente ; para dos pruebas comúnmente utilizadas, para cualquier n compuesto , al menos la mitad de a detecta la composición de n, por lo que k repeticiones reducen la probabilidad de error a como máximo 2 ^{− k} , que puede hacerse arbitrariamente pequeña aumentando k .

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

1. Elija al azar un número a .
2. Verifique la igualdad (correspondiente a la prueba elegida) entre a y el número dado n . Si la igualdad no se cumple, entonces n es un número compuesto y a es un testigo de la composición, y la prueba se detiene.
3. Vuelva al paso uno hasta alcanzar la precisión requerida.

Después de una o más iteraciones, si se encuentra que n no es un número compuesto, entonces se puede declarar 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 número entero n , elija algún número entero a coprimo a n y calcule a ^{n − 1} módulo n . Si el resultado es diferente de 1, entonces n es compuesto. Si es 1, entonces n puede ser primo.

Si a ^{n −1} (módulo n ) es 1 pero n no es primo, entonces n se llama pseudoprimo con base a . En la práctica, si ^{n −1} ( ^módulo n ) es 1, entonces n suele ser primo. Pero he aquí un contraejemplo: si n = 341 y a = 2, entonces

${\displaystyle 2^{340}\equiv 1{\pmod {341}}}$

aunque 341 = 11·31 es compuesto. De hecho, 341 es la base 2 pseudoprime más pequeña (consulte la Figura 1 de ^[3] ).

Sólo hay 21853 pseudoprimos base 2 que miden menos de 2,5 × 10¹⁰ (ver página 1005 de ^[3] ). Esto significa que, para n hasta 2,5 × 10¹⁰ , si 2 ^{n −1} (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 ^an − ¹ 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 560 es 1 (módulo 561) para todo coprimo hasta 561. Sin embargo, la prueba de Fermat se utiliza 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 número entero n , elija algún entero positivo a  <  n . Sea 2 ^s d = n  − 1, donde d es impar. Si

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

y

${\displaystyle a^{2^{r}d}\not \equiv -1{\pmod {n}}}$para todos ${\displaystyle 0\leq r\leq s-1,}$

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

La prueba de primalidad de Solovay-Strassen utiliza otra igualdad: dado un número impar n , elija algún número entero a  <  n , si

${\displaystyle a^{(n-1)/2}\not \equiv \left({\frac {a}{n}}\right){\pmod {n}}}$, ¿dónde está el símbolo de Jacobi ? ${\displaystyle \left({\frac {a}{n}}\right)}$

entonces n es compuesto y a es un testigo de la composición. De lo contrario, n puede ser primo o no. La prueba de Solovay-Strassen es una prueba de probabilidad prima de Euler (ver PSW ^[3] página 1003).

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, entonces la prueba de Miller-Rabin muestra que n es compuesta, pero la prueba de Solovay-Strassen no. Esto se debe a que 1905 es una base pseudoprime 2 de Euler pero no una base pseudoprime 2 fuerte (esto se ilustra en la Figura 1 de PSW ^[3] ).

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 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 primalidad probable de Lucas para obtener una prueba de primalidad que no tiene contraejemplos conocidos. Es decir, no hay ningún compuesto conocido n para el cual esta prueba informe que n probablemente sea primo. ^{[4] [5]} Se ha demostrado que no existen contraejemplos para n . ${\displaystyle <2^{64}}$

Otras pruebas

Leonard Adleman y Ming-Deh Huang presentaron una variante sin errores (pero esperada en tiempo polinómico) 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 demostrar que un número es primo. ^[6] El algoritmo es prohibitivamente lento en la práctica.

Si estuvieran disponibles computadoras cuánticas , la primalidad podría probarse asintóticamente más rápido que usando computadoras clásicas. Una combinación del algoritmo de Shor , un método de factorización de enteros, con la prueba de primalidad de Pocklington podría resolver el problema en . ^[7] ${\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 podía utilizarse para comprobar la primalidad. ^[8] Esto resultó en la prueba de primalidad de Pocklington . ^[9] Sin embargo, como esta prueba requiere una factorización parcial de n  − 1, el tiempo de ejecución fue todavía bastante lento en el peor de los casos. La primera prueba determinista de primalidad 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. (El tiempo de ejecución se mide en términos del tamaño de la entrada, que en este caso es ~ log  n , siendo ese el número 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. ^{[ ¿cual? ]} De manera similar, bajo la hipótesis generalizada de Riemann , 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 ) ⁴ ). ^[10] 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 la primalidad . La prueba de primalidad de AKS se ejecuta en Õ((log  n ) ¹² ) (mejorado a Õ((log  n ) ^7,5 ) ^[11] en la revisión publicada de su artículo), que se puede reducir aún más a Õ((log  n ) ⁶ ) si la conjetura de Sophie Germain es cierta. ^[12] Posteriormente, Lenstra y Pomerance presentaron una versión de la prueba que se ejecuta en el tiempo Õ((log  n ) ⁶ ) incondicionalmente. ^[13]

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. ^[11] Una versión modificada de la conjetura de Agrawal, la conjetura de Agrawal-Popovych, ^[14] 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 COMPUESTOS está en NP porque uno puede decidir la composición adivinando un factor de manera no determinista.

En 1975, Vaughan Pratt demostró que existía un certificado de primalidad que se podía comprobar en tiempo polinómico y, por tanto, que PRIMES estaba en NP y, por tanto, en . Consulte el certificado de primalidad para obtener más detalles. ${\displaystyle {\mathsf {NP\cap coNP}}}$

El descubrimiento posterior de los algoritmos de Solovay-Strassen y Miller-Rabin puso PRIMES en coRP . En 1992, el algoritmo de Adleman-Huang ^[6] redujo la complejidad a , lo que reemplazó al resultado de Pratt. ${\displaystyle {\mathsf {{\color {Blue}ZPP}=RP\cap coRP}}}$

La prueba de primalidad de Adleman-Pomerance-Rumely de 1983 colocó PRIMES en QP ( tiempo cuasipolinomial ), 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 evidencias similares, durante mucho tiempo se sospechó, pero no se demostró, que la primalidad podría resolverse en tiempo polinómico. La existencia de la prueba de primalidad de 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 AC 0 . ^[15]

Métodos de teoría de números

Existen ciertos métodos de teoría de números para comprobar 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 pruebas de primalidad de propósito general, pero a menudo son bastante poderosas cuando se sabe que el número n probado tiene una característica especial. forma.

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 demostrar que a es primitivo para n , podemos demostrar que n es primo.

Referencias

1. Riesel (1994) págs.2-3
2. Conjetura de John Selfridge # Selfridge sobre las pruebas de primalidad .
3. Pomerancia, Carl ; Selfridge, John L .; Wagstaff, Samuel S. Jr. (julio de 1980). "Los pseudoprimos a 25·109" (PDF) . Matemáticas de la Computación . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 .
4. Baillie, Robert; Wagstaff, Samuel S. Jr. (octubre de 1980). «Lucas Pseudoprimos» (PDF) . Matemáticas de la Computación . 35 (152): 1391-1417. doi : 10.1090/S0025-5718-1980-0583518-6 . SEÑOR  0583518.
5. Baillie, Robert; Fiori, Andrés; Wagstaff, Samuel S. Jr. (julio de 2021). "Fortalecimiento de la prueba de primalidad de Baillie-PSW". Matemáticas de la Computación . 90 (330): 1931-1955. arXiv : 2006.14425 . doi : 10.1090/mcom/3616. S2CID  220055722.
6. Adleman, Leonard M .; Huang, Ming-Deh (1992). "Pruebas de primalidad y variedades abelianas en campos finitos" . Apuntes de clases de matemáticas. vol. 1512. Springer-Verlag . ISBN 3-540-55308-8.
7. Chau, HF; Mira, H.-K. (1995). "Prueba de primalidad mediante factorización cuántica". arXiv : quant-ph/9508005 .
8. Pocklington, HC (1914). "La determinación de la naturaleza prima o compuesta de números grandes mediante el teorema de Fermat". Cambr. Fil. Soc. Proc . 18 : 29–30. JFM  45.1250.02.
9. Weisstein, Eric W. "Teorema de Pocklington". MundoMatemático .
10. Gary L. Miller (1976). "Hipótesis y pruebas de primalidad de Riemann". Revista de Ciencias de la Computación y de Sistemas . 13 (3): 300–317. doi : 10.1016/S0022-0000(76)80043-8 .
11. Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "Los números primos están en P" (PDF) . Anales de Matemáticas . 160 (2): 781–793. doi : 10.4007/anales.2004.160.781 .
12. Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES está en P" (PDF) . Anales de Matemáticas . 160 (2): 781–793. doi : 10.4007/anales.2004.160.781 .
13. Carl Pomerance y Hendrik W. Lenstra (20 de julio de 2005). "Prueba de primalidad con períodos gaussianos" (PDF) .
14. Popovych, Roman (30 de diciembre de 2008). "Una nota sobre la conjetura de Agrawal" (PDF) .
15. E. Allender, M. Saks e IE Shparlinski, Un límite inferior para la primalidad, J. Comp. Sistema. Ciencia. 62 (2001), págs. 356–366.

Fuentes

• Crandall, Richard ; Pomerancia, Carl (2005). Números primos: una perspectiva computacional (2ª ed.). Saltador. ISBN 0-387-25282-7.Capítulo 3: Reconocimiento de números primos y compuestos, págs. 109-158. Capítulo 4: Prueba de primalidad, págs. 159-190. Sección 7.6: Prueba de primalidad de curva elíptica (ECPP), págs.
• Knuth, Donald (1997). "sección 4.5.4". El arte de la programación informática . vol. 2: Algoritmos seminuméricos (3ª ed.). Addison-Wesley. págs. 391–396. ISBN 0-201-89684-2.
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "Sección 31.8: Pruebas de primalidad". Introducción a los algoritmos (Segunda ed.). Prensa del MIT, McGraw-Hill. págs. 887–896. ISBN 0-262-03293-7.
• Papadimitriou, Christos H. (1993). "Sección 10.2: Primalidad". Complejidad computacional (1ª ed.). Addison Wesley. págs. 222-227. ISBN 0-201-53082-1. Zbl  0833.68049.
• Riesel, Hans (1994). Números primos y métodos informáticos de factorización . Progreso en Matemáticas. vol. 126 (segunda ed.). Boston, Massachusetts: Birkhäuser. ISBN 0-8176-3743-5. Zbl  0821.11001.

enlaces externos

• Solovay-Strassen (computacion.cs.cinvestav.mx) en archive.today (archivado el 20 de diciembre de 2012) – Implementación de la prueba de primalidad de Solovay-Strassen en Maple
• Distinguir números primos de números compuestos, por DJ Bernstein (cr.yp.to)
• Las páginas principales (primes.utm.edu)
• Prueba de primalidad de Lucas con factorizado N − 1 (MathPages.com) en los archivos web de la Biblioteca del Congreso (archivado el 6 de agosto de 2010)
• PRIMABOINCA es un proyecto de investigación que utiliza computadoras conectadas a Internet para buscar un contraejemplo a algunas conjeturas. La primera conjetura ( conjetura de Agrawal ) fue la base para la formulación del primer algoritmo determinista de prueba prima en tiempo polinómico ( algoritmo AKS ).