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?Generando REALMENTE grandes números primos
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 sus probabilidades de "golpear" un primo mediante intentos aleatorios son (2/ln n)
Por ejemplo, si quiere un número primo aleatorio de 512 bits, encontrará uno en 2/(512 * ln (2)) Así que aproximadamente 1 de cada 177 de los números que intente será primo.
Hay varias formas de comprobar si un número es primo, uno bueno es el "Test de Miller-Rabin" como se indicó anteriormente.
También, OpenSSL tiene una utilidad agradable para la prueba de números primos:
$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime
Eche un vistazo a cómo lo hace TrueCrypt. Además, eche un vistazo a Rabin-Miller para probar pseudoprimas grandes.
¿Por qué asumes que TrueCrypt genera números primos? Hasta donde yo sé, solo usa crypto simétrico. – CodesInChaos
No mencionó el idioma que está utilizando. Algunos tienen un método para hacer esto incorporado. Por ejemplo, en Java esto es tan fácil como llamar al nextProbablePrime() en un BigInteger.
Estoy usando Objective-C – computergeek6
Dependiendo de cómo se implemente esa funcionalidad, puede comprometer la elección de su clave si se reduce el espacio de búsqueda. – Stephen
La respuesta anterior es incorrecta: 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 509 * 59.
Creo que el cartel se misremembering la prueba (reales) que hay son una incontable número de números primos.
En realidad, solo hay un número contable (pero infinito) de números primos. Además, el otro póster (cuya publicación parece borrarse ahora) no está recordando mal la construcción de la prueba (así es como funciona), sino que está haciendo un mal uso de ella. – oggy
De hecho. Recuerde que los enteros son contables, va "1, 2, ...". Entonces son primos y racionales; son números reales que no son contables. – jrockway
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
hay un algoritmo debido a U. Maurer que genera al azar demostrables (en contraste con estadísticamente altamente probable) números primos que son casi uniformemente distribuido en 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/
Gracias. Esto explica muchos de los problemas que estaba teniendo. – computergeek6
puede generar primos en openssl también: 'openssl prime -generate -bits 512' – mykhal