CODEWITHSUNDEEP
python
Akari Oozora
Akari Oozora

Reputation: 368

How can i handle very high exponentials in Python?

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

Upvotes: 3

Views: 187

Answers (2)

Alex G
Alex G

Reputation: 703

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.

Upvotes: 1

Daweo
Daweo

Reputation: 36430

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.

Upvotes: 7

Related Questions