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

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?

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 ⁿ 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.

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) .

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 ¹²⁸ o 2 ²⁵⁶ .

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).

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.

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.

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.