How to get rid of overflow in math module?

Question

Python

I solve a study problem.
I get an OverflowError: math range error.

from math import *


def get_b(p, a):
    start_time = time.time()
    # b = math.fmod(math.pow(a, p-2), p)

    b = pow(a, p-2)
    b = b % p
    print("--- %s seconds ---" % (time.time() - start_time))
    return int(b)

print(get_b(2097151, 9))

How to solve the problem?

Without the math module, everything works, but I'm not on time. I tried to write my implementation of exponentiation in Python, but it does not give a gain in time.

I think that the error is that the module works in float. If so, then how can I make it work with int?

Answer 1

do you write powmod?

pow(x, y[, z])
return x to the power y; if z is present, return x to the power y, modulo z (computed more efficiently than pow(x, y) % z). The two-argument form pow(x, y) is equivalent to using the power operator: x**y.