Acabo de responder a la misma pregunta en stackoverflow, por lo que duplicaré mi respuesta aquí (no creo que la duplicación sea el camino a seguir; tal vez la pregunta debería migrarse):
Supongamos que seleccionas un primer p seleccionando valores aleatorios hasta que encuentres uno para el que Miller-Rabin dice: ese parece un primo. Usas rondas de n como máximo para la prueba de Miller-Rabin. (Para un llamado "primer seguro", las cosas no se cambian, excepto que se ejecutan dos pruebas anidadas).
La probabilidad de que un entero de 1024 bits aleatorio sea primo es aproximadamente 1/900. Ahora, no desea hacer nada estúpido por lo que genera solo valores impares (se garantiza que un entero par de 1024 bits no es primo) y, en general, solo ejecuta la prueba de Miller-Rabin Si el valor no es "obviamente" no primo, es decir, se puede dividir por un primo pequeño. Así que terminas probando unos 300 valores con Miller-Rabin antes de alcanzar un prime (en promedio). Cuando el valor no es primo, Miller-Rabin lo detectará con una probabilidad de 3/4 en cada ronda, por lo que el número de rondas de Miller-Rabin que ejecutará en promedio para un solo valor no primo es de 1+ (1/4 ) + (1/16) + ... = 4/3. Para los 300 valores, esto significa aproximadamente 400 rondas de Miller-Rabin, independientemente de lo que elija para n .
( Editar: en realidad, para un no primo elegido al azar, Miller-Rabin funciona mejor que eso (consulte la respuesta de @Brett) y el número promedio de rondas será más cercano a 300 de 400. No cambia sustancialmente mi argumento.)
Entonces, si selecciona n como, por ejemplo, 40, entonces el costo implícito por n es inferior al 10% del costo computacional total. El proceso de selección de primos aleatorios está dominado por la prueba en primos, que no se ven afectados por el valor de n que elija. Hablé aquí sobre los enteros de 1024 bits; para números más grandes, la elección de n es incluso menos importante ya que los números primos se vuelven más dispersos a medida que aumenta el tamaño (para enteros de 2048 bits, el "10%" de arriba se convierte en "5%").
Por lo tanto, puedes elegir n = 40 y estar contento con él (o al menos saber que reducir n no te comprará mucho de todos modos). Por otro lado, usar un n mayor de 40 no tiene sentido, porque esto te llevaría a probabilidades más bajas que el riesgo de una simple falta de cómputo. Las computadoras son hardware, pueden tener fallas aleatorias. Por ejemplo, una función de prueba de primalidad podría devolver "verdadero" para un valor no primo porque un rayo cósmico (una partícula de alta energía que circula a través del Universo a alta velocidad) llega a golpear el transistor correcto en el momento adecuado, volteando el devuelva el valor de 0 ("falso") a 1 ("verdadero"). Esto es muy poco probable, pero no menos probable que sea la probabilidad 2-80 . Consulte esta respuesta de stackoverflow para más detalles. La conclusión es que, independientemente de cómo se asegure de que un entero sea primo, todavía tenga un elemento probabilístico inevitable, y 40 rondas de Miller-Rabin ya le dan lo mejor que puede esperar.
Para resumir, usa 40 rondas.