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 »

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-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años
OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 206
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Re: Test de primalidad de Miller Rabin

Mensaje sin leer por Matías »

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 »

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 »

se puede aprender mucho por aqui :)
Responder