Test de primalidad de Miller-Rabin

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

El test de primalidad de Miller-Rabin es un test de primalidad, es decir, un algoritmo para determinar si un número dado es primo, similar al test de primalidad de Fermat. Su versión original fue propuesta por G. L. Miller, se trataba de un algoritmo determinista, pero basado en la no demostrada hipótesis generalizada de Riemann;[1] Michael Oser Rabin modificó la propuesta de Miller para obtener un algoritmo probabilístico que no utiliza resultados no probados.[2]

Descripción del test[3] [editar]

Supóngase que n > 1 es un número impar del cual queremos saber si es primo o no. Sean k el número natural y m el impar tales que n − 1 = 2k m y un entero escogido aleatoriamente entre 2 y n − 2.

(Paso 0) Se calcula .

Si , el test culmina con la conclusión de que n es probable primo.

(Paso 1) En caso contrario se calcula .

Si , el test culmina con la conclusión de que n es probable primo.
Si , el test culmina con la conclusión de que n no es primo.

(Paso i) De igual forma, siempre que y se calcula .

Si , el test culmina con la conclusión de que n es probable primo.
Si , el test culmina con la conclusión de que n no es primo.

(Paso k-1) Se calcula .

Si , el test culmina con la conclusión de que n es probable primo.
En cualquier otro caso, el test culmina con la conclusión de que n no es primo.

Si n es un probable primo se escoge un nuevo valor para a, y se itera nuevamente reduciendo el margen de error probable. Al utilizar exponenciación binaria las operaciones necesarias se realizan muy rápidamente.

Explicación[editar]

Las dos propiedades acerca de los números primos detrás del test son:

(1) el pequeño teorema de Fermat: si p es primo entonces (mod p),

(2) si p es primo y verifica (mod p) entonces (mod p), esto se deduce del hecho que es un cuerpo cuando p es primo.

El test de Miller-Rabin contesta que n no es primo cuando no verifica una de estas dos propiedades. Cuando ninguna de ellas falla contesta que es un probable primo.

Observe que si n no pasa el test en el paso i para algún 0<i<k-1 es porque se tiene y , o sea que n no cumple la propiedad (2).

Si el test llega al paso k-1 es porque . Si , tendremos que n no cumple la propiedad (2). Si pero , nuevamente falla la propiedad (2). Por construcción de los se tiene que , por lo tanto, si , entonces n no cumple la propiedad (1). O sea que una vez llegado al paso k-1, la única manera en que n puede ser primo es si se verifica .

Fiabilidad del test[editar]

Debido a su baja probabilidad de fallo, es el test más utilizado en la práctica, a la hora de aplicaciones en criptografía de clave pública.[4]

Se puede demostrar que un número compuesto es clasificado «probable primo» en una iteración del algoritmo con una probabilidad inferior a 1/4.[3] Es decir, que la probabilidad de que un número compuesto pase h iteraciones del test respondiendo ser posible primo es menor a si las bases son escogidas al azar. En la práctica, la probabilidad parece ser mucho menor, según un artículo de Damgård, Landrock y Pomerance.[5]

Asumiendo correcta la hipótesis generalizada de Riemann, se puede demostrar que, si todo valor de a hasta 2(ln n)² ha sido verificado y n todavía es clasificado como probable primo, entonces n es en realidad un número primo. Con esto se tiene un test de primalidad de costo O((ln n)4).

Referencias[editar]

  1. Miller, Gary (1975). «Riemann's Hypothesis and tests for primality». Journal of Computer and System Sciences 13 (3): 300-317. doi:10.1016/S0022-0000(76)80043-8. 
  2. Rabin, Michael (1980). «Probabilistic algorithm for testing primality». Journal of Number Theory 12 (1): 128-138. doi:10.1016/0022-314X(80)90084-0. 
  3. a b Stinson, Douglas (2005). «The RSA Cryptosystem and Factoring Integers». En Chapman and Hall/CRC. Cryptography - Theory and Practice (en inglés) (tercera edición). pp. 186-188. ISBN 978-1584885085. 
  4. Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott (2001). «Public-Key Parameters». En CRC. Handbook of applied cryptography (en inglés) (quinta edición). p. 138. ISBN 0-8493-8523-7. Consultado el 14 de febrero de 2016. 
  5. Damgård, Ivan; Landrock, Peter; Pomerance, Carl (1993). «Average case error estimates for the strong probable prime test». Mathematics of Computation (en inglés) 61 (203): 177-194. doi:10.2307/2152945. 

Enlaces externos[editar]