[Tarea 2] Pregunta 2 - Exponenciación rápida para números grandes

[VicenteMerino]

Hola, pude implementar el test de primalidad de miller rabin, sin embargo falla para números muy grandes. Me di cuenta que se debe por el método de exponenciación rápida, que en el paso recursivo calcula b/2. Por ejemplo si tengo un número muy grande en python como 2**300 - 153 (el mismo que se usa en el paper), al calcular b/2, python arroja lo siguiente:

Lo que termina haciendo cálculos poco exactos y finalmente siempre me arroja False para primos grandes. Cómo podemos manejar estos casos? Por mientras estoy usando el método pow para hacer la exponenciación y funciona, sin embargo esto está prohibido. Se me ocurre que deben haber librerías que permiten manejar estos números, pero no estoy seguro.

[mugartec]

Hola @VicenteMerino, el problema es con los tipos de las variables. Al dividir un entero por otro en la práctica estás trabajando con números de punto flotante, que en python no son de largo arbitrario.

>>> a = (2 ** 300 - 153)
>>> type(a / 2)
float

Si trabajas siempre con enteros esto no ocurre, por lo que tu problema se resuelve usando división entera:

>>> a = (2 ** 300 - 153)
>>> b = a // 2
>>> type(b)
int
>>> print(a)
2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397223
>>> print(b)
1018517988167243043134222844204689080525734196832968125318070224677190649881668353091698611
>>> print(2 * b)
2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397222

Me cuentas si tienes problemas, espero que sirva. Saludos!

[VicenteMerino]

Toda la razón, ahora me funcionó!!