Generando primos realmente grandes
https://stackoverflow.com/questions/1146274
-
16-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy jugando y tratando de escribir una implementación de RSA. El problema es que estoy atrapado en generar los números primos masivos que están involucrados en la generación de un par de claves. ¿Alguien podría señalarme una forma rápida de generar grandes primos/primos probables?
Solución
No generas números primos exactamente. Generas un gran número impar al azar, luego prueba si ese número es primo, si no genera otro al azar. Hay algunas leyes de números primos que básicamente indican que sus probabilidades de "golpear" un primo a través de intentos aleatorios es (2/ln n)
Por ejemplo, si desea un número primario aleatorio de 512 bits, encontrará uno en 2/(512*ln (2)), por lo que aproximadamente 1 de cada 177 de los números que intente será primo.
Hay múltiples formas de probar si un número es primo, una buena es la "Prueba Miller-Rabin" Como se indicó en otra respuesta a esta pregunta.
Además, OpenSSL tiene una buena utilidad para evaluar los primos:
$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime
Otros consejos
No mencionaste qué idioma estás usando. Algunos tienen un método para hacerlo. nextProbablePrime () en un biginteger.
La respuesta anterior es incorrecta: 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 509 * 59.
Creo que el póster está recordando mal la prueba (real) de que hay un número incontable de números primos.
Mono tiene una clase Biginteger que es de código abierto al igual que Java. Podrías echarle un vistazo a ellos. Probablemente sean portátiles :) G'luck
Hay un algoritmo debido a U. Maurer que genera primos propensos aleatorios (en contraste con estadísticamente altamente probables) que se distribuyen casi uniformemente sobre el conjunto de todos los primos de un tamaño especial. Tengo una implementación de Python que es bastante eficiente en:http://s13.zetaboards.com/crypto/topic/7234475/1/
