How can i handle very high exponentials in Python?

user_13296852 0
Viewed 77

I'm working in a RSA algorithm in Python. My code runs smoothly, whenever I type prime values such as 17 and 41 no problems happens. However, if I try primes over 1000 the code "stops" running (I mean, it will get stuck in the exponential) and don't return.

The part where the problems relies is this:

msg = ''
msg = msg + (ord(char ** d) % n for char in array)

I know that doing exponentials for numbers like d = 32722667 and char = 912673 requires a lot of computing, but I guess it shouldn't be supposed to don't return anything in like 5, 10 minutes.

My computer is an i3-6006U and has 4GB of RAM

python
2 Answers

If you are interested in result of x**y%z rather than x**y you might harness built-in function pow, from help(pow):

Help on built-in function pow in module builtins:

pow(x, y, z=None, /)
    Equivalent to x**y (with two arguments) or x**y % z (with three arguments)

    Some types, such as ints, are able to use a more efficient algorithm when
    invoked using the three argument form.
user_107859750

What you're trying to do is to calculate modular exponentiation. You should not calculate the result of the exponentiation first and then the result of the modulo. There are more efficient algorithms like you can read on Wikipedia. In python you can use the built-in pow function for the modular exponentiation like it was already mentioned.

user_98592130
Related