[Tarea 2 - Pregunta 2] Término del test de Miller-Rabin

[diegoheg]

Hola!

Para el test de Miller-Rabin no tengo claro el caso en el que termina el test, pues en clases se mostraron las bases para un test que termina en los siguientes casos para un número aleatorio a :

• a ( n-1/x ) mod n == -1, donde retorna primo para n
• a ( n-1/x ) mod n != -1 y a( n-1/x ) mod n != 1, donde retorna compuesto para n (con x una potencia de 2 con las características discutidas en clase)

Es esto correcto o en caso de que suceda que a( n-1/x ) mod n == -1 se deben seguir con los tests al igual que cuando a( n-1/x ) mod n == 1 y retornar primo solo en caso de que se cumplan las k iteraciones ?

[marceloarenassaavedra]

En clases vimos un poco de intuición sobre la forma cómo fue construido el test de Miller-Rabin. Como es mencionado en el material complementario del curso, la descripción detallada del test de Miller-Rabin puede ser sacada desde aquí:

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

En particular, dado n-1 = d*2^s y un número a sacado al azar desde el conjunto {2, ..., n-1}, las condiciones que son verificadas sobre la sucesión de números a^d mod n, a^(d*2) mod n, a^(d*2^2) mod n, ..., a^(d*2^(s-1)) mod n, y las condiciones de detención del test son mencionadas aquí:

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Miller%E2%80%93Rabin_test

Saludos!