Test de primalidad de Miller Rabin

Para discutir problemas de competencias para graduados de secundaria (Número de Oro, CIMA/Paenza, etcétera) y problemas que requieran conocimientos avanzados.
Sergio Garcia
Mensajes: 2
Registrado: Mar 01 May, 2018 5:03 pm

Test de primalidad de Miller Rabin

Mensaje sin leer por Sergio Garcia » Mar 01 May, 2018 6:37 pm

Estimados, espero que alguien de aqui pueda resolver mi duda y agradezco de antemano. Voy a usar mayusculas para las variables.
El test de Miller Rabin comienza de la siguiente manera:
1. Se obtiene un numero N del cual se quiere saber si es primo
2. Se obtiene un numero al azar A entre 1 y N-1
3. Se calcula X=A^(N-1)/2 modulo N
4. Si X=1 ó X=N-1 entonces N es probable primo. Entiendo que esto es asi pues X^2 = A^((N-1)/2)^2 = A^(N-1), y por Fermat eso es igual a 1 mod N
5. Si X ≠ 1 y X ≠ N-1 entonces calcular X1=X^2 modulo N y si X1=1 entonces N NO es primo pues no cumple con los requerimientos de un Cuerpo.

Mi duda es:
Como X=A^(N-1)/2, X^2= (A^(N-1)/2)^2 = A^(N-1) en modulo N, en donde apliqué propiedades de las potencias: potencia de potencia es igual al producto de los exponentes: (1/2)*2= 1. Resumiendo: X^2 = A^(N-1) modulo N y eso por Fermat es igual a 1 si N es primo.
O sea que indefectiblemente por lo demostrado en el renglon anterior X^2 modulo N va a ser igual a 1 si N es primo y en caso de que X sea un numero distinto de 1 ó -1 se demuestra que N no es primo pues no cumple con la propiedad de cuerpo: existe un elemento tal que elevado al cuadrado es igual a 1 y ese elemento es distinto de 1 ó -1.

Luego, qué sentido tiene el paso 5? Si X ≠ 1 y X ≠ N-1 ya queda demostrado que N NO es primo
El paso 5 supone que X es distinto de 1 ó -1 y entonces hace X^2 modulo N para demostrar, en caso de que X^2=1, que N no es un Cuerpo pues existe un elemento tal que elevado al cuadrado es igual a 1 y ese elemento no es ni 1 ni -1

Espero haberme explicado con claridad. Es posible que en alguna igualdad (en las que corresponda) haya omitido escribir "modulo N", pero creo que quienes estan familiarizados con el tema sabran pasar por alto esas deficiencias técnicas. Muchas gracias por leerme.

Matías

OFO - Medalla de Bronce FOFO Pascua 2017 - Medalla OFO - Medalla de Plata
Mensajes: 157
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 4
Nivel: 2

Re: Test de primalidad de Miller Rabin

Mensaje sin leer por Matías » Mar 01 May, 2018 8:33 pm

Hola Sergio
Tenés razón, el paso 5 es innecesario, ya que, como bien decís, si $X\neq 1$ y $X\neq N-1$ entonces $N$ no puede ser primo (ya que si $N$ fuera primo, por el pequeño teorema de Fermat $X^2\equiv 1(N)\implies N\mid X^2-1=(X+1)(X-1)\implies X\equiv 1\vee -1(N)$)
Saludos

Sergio Garcia
Mensajes: 2
Registrado: Mar 01 May, 2018 5:03 pm

Re: Test de primalidad de Miller Rabin

Mensaje sin leer por Sergio Garcia » Mié 02 May, 2018 10:26 am

Gracias Matias. Alentado por tu comentario me dispuse a modificar el algoritmo y fue en ese momento que me di cuenta de mi error.

Con un razónamiento muy basico yo pensaba que si en el paso 5 se demostraba o no primalidad, ahi quedaba todo resuelto

El algoritmo no finaliza en el paso 5 sino que continua calculando las potencias Xi=A^(N-1)/(2^K) con k=2,3,4...
Y es en alguno de esos pasos en los que es posible arribar a que Xi ≠ 1 y Xi ≠ N-1 y aún N no pierde la calidad de probable primo.

Esto ultimo es asi ya que la división (N-1)/(2^K) es forzosamente entera pues no es posible hacer por ejemplo: (N-1)/(36.75) y por tal motivo tampoco es posible hacer el siguiente planteo: (Hagamos 2^K= R para no abultar tanto las ecuaciones)

X=A^(N-1)/R, X^R= (A^(N-1)/R)^R = A^(N-1), esta ecuacion ya no es valida pues el (N-1)/R de la primera igualdad ya no es el mismo que el (N-1)/R de la segunda igualdad pues hubo redondeo para evitar los decimales.

En fin, perdon por el embrollo y gracias a vos y a quienes se tomaron el trabajo de leer y entender tanta ecuacion.

Marcoslg
Mensajes: 1
Registrado: Mié 09 May, 2018 5:26 am
Nivel: Otro
Contactar:

Re: Test de primalidad de Miller Rabin

Mensaje sin leer por Marcoslg » Mié 09 May, 2018 5:31 am

se puede aprender mucho por aqui :)

Responder