resta - suma de biginteger java

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

El caso de uso estándar para BigInteger.isProbablePrime(int) está en criptografía. Específicamente, ciertos algoritmos criptográficos, como RSA , requieren 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 de cifrado, uno normalmente llamaría .isProbablePrime() con un argumento en algún lugar 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 esto en perspectiva: si tuvieras 10 mil millones de computadoras, cada una de las cuales generaría 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 primalidad de esos números se probó con .isProbablePrime(128) , esperaría, en promedio, que un número no primo se deslice una vez cada 100 mil millones de años .

Es decir, ese sería el caso, si esos 10 mil millones de computadoras pudieran funcionar de alguna manera durante cientos de miles de millones de años sin experimentar fallas 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 correctos para .isProbablePrime(128) valor de retorno de .isProbablePrime(128) de falso a verdadero, sin causar ningún otro efecto detectable, que corresponde a un número no primo pasar la prueba de primalidad probabilística a 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 primitivismo deterministas como AKS . Por lo tanto, en la práctica, incluso estas pruebas tienen una tasa de falsos positivos de referencia (muy pequeña) debido a fallas aleatorias de hardware (sin mencionar todas las otras posibles fuentes de errores, como errores de implementación).

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

(Además, incluso si accidentalmente seleccionó 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 multi-prime . Mientras ninguno de los factores fuera demasiado pequeño (y si lo fueran, la prueba de primalidad debería haberlos detectado), el algoritmo RSA lo hará 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 escatima innecesariamente la longitud de la clave).

El método BigInteger.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 arg es el argumento entero.

Ha estado presente en el JDK durante bastante tiempo, por lo que significa que debe tener usos. Mi limitado conocimiento 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 quisiera usar este método? ¿Criptografía?

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

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

Desde entonces, se han descubierto algoritmos que pueden decidir de manera determinista si un número es primo razonablemente rápido, como el algoritmo AKS que se descubrió en agosto de 2002. Sin embargo, debe tenerse en cuenta que estos algoritmos aún no son tan rápidos como Miller-Rabin.

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

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

Resulta que probar estos números primos también es difícil. Pero la prueba de primalidad de Miller-Rabin , una de las pruebas de primalidad utilizadas por isProbablePrime , detecta que un número es compuesto o no da ninguna conclusión. Ejecutar esta prueba n veces le permite concluir que hay una probabilidad de 1 en 2 ^{n de} que este número sea realmente compuesto. Ejecutarlo 100 veces produce el riesgo aceptable de 1 en 2 ^{100 de} que este número sea compuesto.

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

Es solo el otro lado de la pregunta, si la prueba te dice que un número entero es "un primo probable", es posible que tengas dudas. La repetición de la prueba con diferentes "bases" permite que la probabilidad de tener éxito falso en "imitar" un primo (que es un seudoprimado fuerte con respecto a múltiples bases) se haga tan pequeña como se desee.

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

La comparación con la dificultad de factorizar enteros es algo así como una pista falsa. Se sabe que la primalidad de un número entero se puede determinar en el tiempo polinómico, y de hecho hay una prueba de que una extensión de la prueba de Miller-Rabin a suficientes bases es definitiva (en la detección de números primos, a diferencia de los números primos probables), pero esto asume la hipótesis de Riemann generalizada, por lo que no es tan cierto como la prueba de primalidad AKS (más costosa).

Un posible caso de uso es probar la primalidad de un número dado (en una prueba que en sí misma tiene muchos usos). El algoritmo isProbablePrime se ejecutará mucho más rápido que un algoritmo exacto, por lo que si el número falla isProbablePrime , entonces uno no tiene que ir a expensas de ejecutar el algoritmo más costoso.

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

Para una discusión más detallada, vea la sección 4.4.1 del Manual de Criptografía Aplicada .

También vea Sobre la generación de números primos probables por búsqueda incremental de Brandt y Damgård.