Test de primalidad de Miller Rabin
Publicado: 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.
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.