encryption - por - numeros primos premio
Generando REALMENTE grandes números primos (6)
Estoy jugando e intentando escribir una implementación de RSA. El problema es que estoy estancado en la generación de los números primos masivos que están involucrados en la generación de un par de claves. ¿Podría alguien señalarme una forma rápida de generar números primos / primos probables?
Eche un vistazo a cómo TrueCrypt lo hace. Además, eche un vistazo a Rabin-Miller para probar grandes pseudoprimas.
La respuesta anterior es incorrecta: 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 509 * 59.
Creo que el póster está recordando erróneamente la prueba (real) de que hay una cantidad incontable de números primos.
No mencionaste qué idioma estás usando. Algunos tienen un método para hacer esto incorporado. Por ejemplo, en Java esto es tan fácil como llamar a nextProbablePrime () en un BigInteger.
Mono tiene una clase BigInteger que es de código abierto al igual que Java. Puedes echarle un vistazo a esos. Probablemente sean portátiles :) g''luck
Existe un algoritmo debido a U. Maurer que genera primos probables aleatorios (en contraste con estadísticamente altamente probables) que están distribuidos casi uniformemente sobre el conjunto de todos los números 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/
No genera números primos exactamente. Generas un gran número impar al azar, luego pruebas si ese número es primo, si no generas otro aleatoriamente. Hay algunas leyes de números primos que básicamente establecen que tus probabilidades de "golpear" a un primo a través de intentos aleatorios son (2 / ln n)
Por ejemplo, si desea un número primo aleatorio de 512 bits, encontrará uno en 2 / (512 * ln (2)) Por lo tanto, aproximadamente 1 de cada 177 de los números que intente será primo.
Hay varias formas de probar si un número es primo, uno bueno es el "test de Miller-Rabin" como se indicó anteriormente.
Además, OpenSSL tiene una buena utilidad para probar primos:
$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime