¿Por qué Miller – Rabin en lugar de la prueba de primalidad de Fermat?

10

A partir de la prueba de Miller-Rabin , si un número pasa la prueba de primalidad de Fermat , también debe pasar la prueba de Miller-Rabin con la misma base (una variable en la prueba). Y la complejidad del cálculo es la misma.a

Lo siguiente es de la prueba de primalidad de Fermat :

Si bien los números de Carmichael son sustancialmente más raros que los números primos, 1 hay suficientes de ellos que la prueba de primalidad de Fermat a menudo no se usa en la forma anterior. En cambio, otras extensiones más potentes de la prueba de Fermat, como Baillie-PSW, Miller-Rabin y Solovay-Strassen, se usan con más frecuencia.

¿Cuál es el beneficio de Miller-Rabin y por qué se dice que es más poderoso que la prueba de primalidad de Fermat?

ZijingWu
fuente

Respuestas:

7

El algoritmo de Rabin-Miller también prueba, dado un número , si Z n tiene una raíz no trivial de Unity.norteZnorte

Números de Carmichael pasan la prueba de Fermat (para cada base ), pero por cada número Carmichael n , existen muchos números de un tal que la prueba para las raíces de la unidad falla en un (es decir, la secuencia de una , 2 una , . . . , 2 r a finalmente muestra una raíz no trivial de la unidad).unnorteununun,2un,...,2run

Así tenemos el siguiente:

Para la prueba de Fermat, si un número compuesto no es Carmichael, entonces la probabilidad de que la prueba detectará compositeness es de al menos 1 / 2 . Sin embargo, la prueba fallará en todos los números de Carmichael.norte1/ /2

Para la prueba de Rabin-Miller, será detectado cada número compuesto con una probabilidad de al menos . Esto significa que la probabilidad de corrección es independiente de la entrada (no hay entradas "duras"). Esto es lo que fortalece este algoritmo.1/ /2

Shaull
fuente
¿Quiere decir que Carmichael número n puede tener éxito en la prueba de Fermat pero falló en Rabin-Miller con la misma base a?
ZijingWu
Números de Carmichael pasan la prueba de Fermat para cada , pero por alguna una es todo fallará la prueba de Rabin-Miller (en concreto, la raíz de prueba de la Unidad). unun
Shaull
Pero Carmichael no pasará la prueba de Fermat por cada , ¿correcto? Por ejemplo, el primer número de Carmichael 561 = 3 * 11 * 17 no pasará la prueba de Fermat para a = 3 u 11 o 17.unun
ZijingWu
unun
1
El punto de las pruebas "más complejas" es que la fracción de bases que mienten (digamos que el número es primo, cuando no lo es) tiene un límite garantizado inferior a 1. Es decir, en Miller-Rabin se puede demostrar que a lo sumo 1/4 mentira (IIRC, y el límite es bastante pesimista).
vonbrand
0

Creo que su declaración es lo contrario de lo que sucede. Pasar la prueba de Miller-Rabin para una base determinada significa que pasará la prueba de Fermat para la misma base. En contraste, hay muchos compuestos que pasarán la prueba de Fermat para una base determinada pero no pasarán la prueba de Miller-Rabin para la misma base.

Ver, por ejemplo, el artículo de Pomerance / Selfridge / Wagstaff en la página de Wikipedia Miller-Rabin:

https://math.dartmouth.edu/~carlp/PDF/paper25.pdf

donde vemos un diagrama en la página 2 que muestra que las pseudoprimas de Euler son un subconjunto de las pseudoprimas de Fermat, y las pseudoprimas fuertes son un subconjunto de ellas. La prueba de Solovay-Strassen es, por lo tanto, más exigente que la prueba de Fermat, y la prueba de Miller-Rabin más que cualquiera. Ambos evitan el problema crítico de los números de Carmichael. Tienen esencialmente el mismo rendimiento, por lo que preferimos usar la prueba Miller-Rabin.

DanaJ
fuente
0

Debería ser obvio que Miller-Rabin es mejor que Fermat.

unpags-1

unpags-1pags-1=s·2kunsunpags-1

Nuevamente, si el resultado no es 1 (módulo p), entonces p es compuesto. Pero si el resultado es 1 módulo p, entonces verificamos si obtuvimos ese 1 al cuadrar un resultado intermedio que no era +1 o -1, y en ese caso x también se prueba compuesto.

Así que hacemos exactamente la misma cantidad de trabajo, pero hay más formas de demostrar que x es compuesto.

gnasher729
fuente