Una consulta, el metodo de multiplicacion rapida que dimos en el curso, lo podemos implementar incluso sin el mod (N). Mi duda es qué es mas eficiente, implementarlo nosotros (basicamente tomar el del practico y "adaptarlo") o usar el que provee python (el operador **).
Saludos
Hice una comparación GROSERA pero te la comento y por ahi a alguno mas le sirve.
En una PC de facultad corrí en 2 terminales 2 versiones de hallar_primo:
Versión A: Utilizó el algoritmo de exponenciación rápida visto en el práctico y una versión refinada del test de Miller-Rabin.
Versión B: Utilizó el algoritmo de exponenciación nativo de python (pow(x,y,[z])) y una versión "leal" al test de Miller-Rabin.
Test:
Se corrió 3 veces, para cada una de las versiones, un script que contenía:
Un for de 10000 iteraciones con hallar_primo
Un for de 5000 iteraciones con hallar_primo
Un for de 5000 iteraciones con hallar_primo
Resultado
En las 3 oportunidades la versión A finalizó cerca de los 2:30 minutos y 40 segundos antes que la versión B.
A pesar de que la comparación fue muy desprolija, 40 segundos parecería ser un dato significativo. Estaría bueno que alguno más se animara a aportar datos u algún marco de análisis más serio y ajustar las conclusiones.
Saludos,
Octavio
Ustedes deberían usar su propia implementación, no solamente por la razón que menciona Octavio. El operador ** no es potenciación rápida porque no puede reducir módulo N cada vez que hace una multiplicación.
N