¿Cuál es un posible caso de uso de .isProbablePrime () de BigInteger?

84

El métodoBigInteger.isProbablePrime() es bastante extraño; de la documentación, esto dirá si un número es primo con una probabilidad de 1 - 1 / 2^arg, donde arges el argumento del número entero.

Ha estado presente en el JDK durante bastante tiempo, por lo que significa que debe tener usos. Mi conocimiento limitado en informática y algoritmos (y matemáticas) me dice que realmente no tiene sentido saber si un número es "probablemente" un primo pero no exactamente un primo.

Entonces, ¿cuál es un posible escenario en el que uno querría utilizar este método? ¿Criptografía?

fge
fuente
6
Además, prueba de primalidad de Miller-Rabin . La principal ventaja es la velocidad . Por ejemplo, cuando desee comprobar los factores, puede realizar dicha prueba para acelerar el proceso de factorización. Puede mantener la parte "probablemente" bastante baja, y es útil en la práctica. Pero estoy de acuerdo en que es un poco inestable y extraño, como flotadores.
keyer
2
@ maxx777 eso es un hecho - pido un caso de uso real
fge
4
Realmente me gustaría que los votantes en contra para explicar las razones detrás de los votos en contra, por favor
fge
17
"Ha estado presente en el JDK durante bastante tiempo, por lo que significa que debe tener usos". - o se agregó por una razón inútil, luego no se eliminó porque nunca se elimina nada.
user253751

Respuestas:

67

Sí, este método se puede utilizar en criptografía. El cifrado RSA implica la búsqueda de números primos enormes, a veces del orden de 1024 bits (alrededor de 300 dígitos). La seguridad de RSA depende del hecho de que factorizar un número que consta de 2 de estos números primos multiplicados es extremadamente difícil y requiere mucho tiempo. Pero para que funcione, deben ser primarios.

Resulta que demostrar que estos números son primos también es difícil. Pero la prueba de primordialidad de Miller-Rabin , una de las pruebas de primordialidad que utiliza isProbablePrime, detecta que un número es compuesto o no da ninguna conclusión. Al ejecutar esta prueba nveces le permite concluir que hay un 1 en 2 n probabilidades de que este número es muy compuesto. Ejecutarlo 100veces produce el riesgo aceptable de 1 en 2 100 de que este número sea compuesto.

rgettman
fuente
3
@ Mr.777 He visto a Rabin-Miller una o dos veces, pero a Miller-Rabin decenas de veces. Sin embargo, no estoy seguro de si hay un nombre oficial.
keyer
3
@ Mr.777 La página de Wikipedia que vinculé arriba dice "Miller-Rabin" primero, pero reconoce ambos nombres: "La prueba de primariaidad de Miller-Rabin o la prueba de primaria de Rabin-Miller".
rgettman
5
La implementación de isProbablyPrimees (por lo que puedo decir) completamente determinista. ¿Cómo mejoraría la ejecución de los ntiempos de prueba las probabilidades de un resultado correcto? (Incluso si fuera un elemento de aleatoriedad, se necesitaría que la aleatoriedad de múltiples llamadas sea independiente para afectar el riesgo de la manera que usted describe).
Ted Hopp
11
@TedHopp La implementación usa un generador aleatorio, y cada ronda con nuevos números aleatorios da 3/4 de probabilidad de detectar un compuesto. El generador predeterminado es SecureRandom, con fuertes garantías de aleatoriedad.
ese otro chico
4
Puede ser difícil, sin embargo, recuerde que PRIMES está en P. La prueba AKS puede ser más lenta que Miller-Rabin, pero no hay una diferencia exponencial o un polinomio entre ellos. Puede usar Miller-Rabin para encontrar un montón de números primos probables y usar AKS para probar definitivamente que son primos.
Bakuriu
20

Si la prueba le dice que un número entero no es primo , ciertamente puede creer que es 100%.

Es sólo el otro lado de la pregunta, si la prueba le dice que un número entero es "un número primo probable", puede albergar dudas. Repetir la prueba con diferentes "bases" permite que la probabilidad de tener éxito en "imitar" un número primo (que es un pseudoprimo fuerte con respecto a múltiples bases) sea tan pequeña como se desee.

La utilidad de la prueba radica en su rapidez y sencillez. Uno no estaría necesariamente satisfecho con el estado de "primo probable" como una respuesta final, pero definitivamente se evitaría perder el tiempo en casi todos los números compuestos utilizando esta rutina antes de incorporar las grandes armas de las pruebas de primalidad .

La comparación con la dificultad de factorizar números enteros es una especie de pista falsa. Se sabe que la primacía de un número entero se puede determinar en tiempo polinomial, y de hecho existe una prueba de que una extensión de la prueba de Miller-Rabin a un número suficiente de bases es definitiva (en la detección de primos, en oposición a los probables), pero esto asume la hipótesis de Riemann generalizada, por lo que no es tan seguro como la prueba de primalidad AKS (más cara) .

hardmath
fuente
4
Vale la pena señalar que AKS solo se descubrió en agosto de 2002, mientras que este método ha estado en JDK desde febrero de 2002
James_pic
3
No, espera, esto ha estado en el JDK desde febrero de 1997 (estaba viendo el probablePrimemétodo, no el isProbablePrimemétodo)
James_pic
1
De hecho, el título del artículo de 2002 de Agrawal, Kayal y Saxena "PRIMES está en P" señala la primera prueba incondicional de complejidad polinomial (en longitud de bits de n ) para la prueba de primalidad determinista (entero general). Miller (1975) había demostrado que, asumiendo GRH , la primacía de un número entero se puede probar de forma determinista en pasos proporcionales a la cuarta potencia de la longitud del bit, un exponente mucho mejor que el que se conoce actualmente para AKS o sus variantes.
hardmath
Si bien AKS es asintóticamente más rápido, métodos como ECPP serían mucho más eficientes para primos 'criptográficos' o 'industriales'.
Brett Hale
2
AKS es increíblemente lento y no será más rápido que APR-CL para cualquier número calculable en tiempo de escala geológica, mucho menos escala humana. APR-CL y ECPP ya existían en 1997. Como menciona Brett, ECPP es una buena opción si queremos una prueba. Todos estos son lentos en comparación con los métodos principales probables (por ejemplo, MR, BPSW, Frobenius).
DanaJ
19

El caso de uso estándar de BigInteger.isProbablePrime(int)es la criptografía. Específicamente, ciertos algoritmos criptográficos, como RSA , requieren números primos grandes elegidos al azar. Sin embargo, es importante destacar que estos algoritmos realmente no requieren que se garantice que estos números sean primos, solo necesitan ser primos con una probabilidad muy alta.

¿Qué tan alto es muy alto? Bueno, en una aplicación criptográfica, uno normalmente llamaría .isProbablePrime()con un argumento entre 128 y 256. Por lo tanto, la probabilidad de que un número no primo pase tal prueba es menor que uno en 2 128 o 2 256 .

Pongamos eso en perspectiva: si tuviera 10 mil millones de computadoras, cada una de las cuales genera 10 mil millones de números primos probables por segundo (lo que significaría menos de un ciclo de reloj por número en cualquier CPU moderna), y la primacía de esos números se probara con .isProbablePrime(128), usted esperaría, en promedio, que un número no primo se deslice una vez cada 100 mil millones de años .

Es decir, que sería el caso, si esos 10 mil millones de computadoras de alguna manera podría todos corren para cientos de miles de años sin experimentar ningún fallos de hardware. En la práctica, sin embargo, es mucho más probable que un rayo cósmico aleatorio golpee su computadora en el momento y lugar adecuados para cambiar el valor de retorno de .isProbablePrime(128)falso a verdadero, sin causar ningún otro efecto detectable, que para un no. -número primo para pasar la prueba de primalidad probabilística en ese nivel de certeza.

Por supuesto, el mismo riesgo de rayos cósmicos aleatorios y otras fallas de hardware también se aplica a las pruebas de primalidad deterministas como AKS . Por lo tanto, en la práctica, incluso estas pruebas tienen una tasa de falsos positivos (muy pequeña) de referencia debido a fallas de hardware aleatorias (sin mencionar todas las otras posibles fuentes de errores, como errores de implementación).

Dado que es fácil llevar la tasa intrínseca de falsos positivos de la prueba de primaria de Miller-Rabin utilizada .isProbablePrime()muy por debajo de esta tasa de referencia, simplemente repitiendo la prueba suficientes veces, y dado que, incluso repetida tantas veces, la prueba de Miller-Rabin sigue siendo Mucho más rápido en la práctica que las pruebas de primalidad deterministas más conocidas como AKS, sigue siendo la prueba de primalidad estándar para aplicaciones criptográficas.

(Además, incluso si seleccionara accidentalmente un pseudoprime fuerte como uno de los factores de su módulo RSA, generalmente no conduciría a una falla catastrófica. Por lo general, tales pseudoprimes serían productos de dos (o raramente más) primos de aproximadamente la mitad de la longitud, lo que significa que terminaría con una clave RSA de primos múltiples . Siempre que ninguno de los factores fuera demasiado pequeño (y si lo fueran, la prueba de primalidad debería haberlos detectado), el algoritmo RSA aún funciona bien, y la clave, aunque algo más débil contra ciertos tipos de ataques que las claves RSA normales de la misma longitud, debería ser razonablemente segura si no escatimó innecesariamente en la longitud de la clave).

Ilmari Karonen
fuente
El problema de la falla es una de las razones por las que AKS no se usa realmente (la velocidad sorprendentemente lenta es la otra), y ECPP es más común. Como puede observar, los errores de implementación en los algoritmos son bastante posibles, por lo que es útil tener un certificado verificado con código independiente.
DanaJ
8

Un posible caso de uso es probar la primordialidad de un número dado (en la prueba, que en sí mismo tiene muchos usos). El isProbablePrimealgoritmo se ejecutará mucho más rápido que un algoritmo exacto, por lo que si el número falla isProbablePrime, no es necesario incurrir en el gasto de ejecutar el algoritmo más caro.

Ted Hopp
fuente
Entonces, ¿es eso por razones prácticas? ¿Y por el hecho de que la factorización prima es un problema de NP?
fge
@fge - Sí, el caso de uso que propuse es práctico. No sé si esto ayuda con la factorización prima, que es un problema significativamente más difícil que probar la primaria. Para este último, existe un algoritmo de tiempo polinomial: la prueba de primalidad AKS .
Ted Hopp
5
@fge: La factorización está en NP, pero sospecho que te refieres a "NP-completo", que no se sabe que sea la factorización . Por el contrario, se sospecha fuertemente que no es NP-hard.
hmakholm dejó a Monica el
6

Encontrar números primos probables es un problema importante en criptografía. Resulta que una estrategia razonable para encontrar un número primo de k bits probable es seleccionar repetidamente un número de k bits aleatorio y probarlo para determinar su primo probable utilizando un método como isProbablePrime().

Para más información, consulte la sección 4.4.1 del Manual de criptografía aplicada .

Consulte también Sobre la generación de números primos probables mediante búsqueda incremental de Brandt y Damgård.

NPE
fuente
5

Los algoritmos como la generación de claves RSA se basan en poder determinar si un número es primo o no.

Sin embargo, en el momento en que isProbablePrimese agregó el método al JDK (febrero de 1997), no existía una forma comprobada de decidir de manera determinista si un número era primo en un período de tiempo razonable. El enfoque más conocido en ese momento era el algoritmo Miller-Rabin , un algoritmo probabilístico que a veces daría falsos positivos (es decir, reportaría no primos como primos), pero podría ajustarse para reducir la probabilidad de falsos positivos, a costa de de modestos aumentos en el tiempo de ejecución.

Desde entonces, se han descubierto algoritmos que pueden decidir determinísticamente si un número es primo razonablemente rápido, como el algoritmo AKS que se descubrió en agosto de 2002. Sin embargo, cabe señalar que estos algoritmos todavía no son tan rápidos como Miller-Rabin.

Quizás una mejor pregunta es por qué no isPrimese ha agregado ningún método al JDK desde 2002.

James_pic
fuente
¡Gracias por la perspectiva histórica! ¿Parece que @immibis estaba en el camino correcto con su comentario sobre "en el JDK pero nunca eliminado", entonces? :)
fge
1
Sé que Java nunca elimina cosas de la biblioteca estándar, pero no estoy seguro de que lo eliminarían incluso si pudieran. Para algunas aplicaciones, estar 99,999999999% seguro de que algo es excelente es lo suficientemente bueno y es mucho más rápido que estar 100% seguro.
James_pic