Prueba de primalidad más rápida

¿Podría sugerir un método rápido y determinista que se pueda usar en la práctica, para probar si un número grande es primo o no?Prueba de primalidad más rápida

Además, me gustaría saber cómo usar pruebas de primalidad no deterministas correctamente. Por ejemplo, si estoy usando dicho método, puedo estar seguro de que un número no es primo si la salida es "no", pero ¿qué pasa con el otro caso, cuando la salida es "probablemente"? ¿Debo probar la primalidad manualmente en este caso?

Gracias de antemano.

Fuente

2010-12-20 Anonymous

Las respuestas y comentarios sobre esta pregunta en CS, tienen algunas buenas ideas sobre qué métodos elegir cuándo y por qué: https://cs.stackexchange.com/questions/23260/when-is-the-aks-primality -test-actually-faster-other-tests –

El único algoritmo determinístico de tiempo de polinomios para pruebas de primalidad que conozco es la prueba de primalidad AKS (http://en.wikipedia.org/wiki/AKS_primality_test). Sin embargo, hay muchas pruebas de primalidad aleatorias muy buenas que son rápidas y tienen una probabilidad de éxito extremadamente buena. Usualmente funcionan al encontrar si el número es compuesto con una probabilidad exponencialmente buena, por lo que informarán que el número es compuesto o requerirán que diga "tal vez" con muy buena confianza.

Fuente

2010-12-20 20:38:26 templatetypedef

Cuando decimos "con muy buena confianza", ¿significa que la probabilidad de obtener una salida incorrecta debido a un mal funcionamiento del sistema es mayor que la probabilidad de que el algoritmo produzca un error? ¿responder? :-) –

@Grigory depende del algoritmo que estés usando. Algunos incluso le permitirán especificar sus posibilidades. Prueba ~ 50%, 75%, 90%, etc.El AKS que especificó responderá correctamente el 100% del tiempo, suponiendo que esté codificado correctamente. –

@Grigory: "mal funcionamiento del sistema"? Las probabilidades están involucradas porque un algoritmo "correcto" sería lento, por lo que puede verificar un conjunto de valores mucho más pequeño que le daría, por ejemplo, un 99,9% de probabilidad de respuesta correcta. ¿Qué crees que significa el término "no determinista" * que has usado? – ruslik

"Probablemente" en realidad significa 1-ε, y ε es lo más pequeño que necesita.

mayoría de las aplicaciones han alguna pequeña probabilidad aún no nulo de defecto no está conectado a la prueba de primalidad, por ejemplo

en aplicaciones criptográficas, un atacante adivinar por suerte el secreto con, por ejemplo, una probabilidad de 2^(- 100)
un fallo de hardware (inducido por la radiación) voltear al azar algunos bits de la memoria del sistema (tal vez una que contiene el resultado de la prueba "determinista" primalidad
errores (de hecho, más probables que el otro tipo de fracasos)

Así presionando el ε a ese orden de magnitud será suficiente en la práctica.

Por ejemplo, OpenSSL, GnuPG usa la prueba de primalidad no determinista solamente. `` Probablemente '' no quieres realmente ninguna prueba determinista. Pero compruebe lo que está disponible para usted: si tiene alguna biblioteca a mano, y se desempeñan lo suficiente, continúe y úselas.

Fuente

2010-12-20 20:48:21 Mitro

Si está buscando encontrar un primo aleatorio para usar en claves RSA, primero debe usar una prueba probabilística. Si la probabilidad es lo suficientemente alta para sus necesidades, entonces deténgase allí. Si debe estar seguro, una vez que encuentre un gran primo probable aleatorio, verifíquelo con AKS u otra prueba no probabilística. Esto le permite verificar una gran cantidad de no primos rápidamente mientras está seguro cuando cree que ha encontrado uno.

Si está tratando de verificar que un número específico existente es primordial, entonces debe usar una de las pruebas que responden con certeza. También hay otras pruebas no polinomiales, use la que sea más rápida en la práctica.

Fuente

2010-12-20 21:42:36 phkahler

Respuesta

Cuestiones relacionadas