CODEWITHSUNDEEP
python-3.xcryptographyrsa
Siddharth Chittoor
Siddharth Chittoor

Reputation: 73

What is the most efficient way to calculate power of larger numbers in python

I am working on a cryptography assignment and trying to decrypt an rsa cipher. There is a step in which I calculate

plaintext = (cipher number) a mod n

Where a = 39222883199635910704838468978553915708840633543073057195 and 
n = 68102916241556954755526080258049854830403581949186670592
cipher number = 49158615403582362779085177062796191820833652424030845810

When I apply the plain text formula I am supposed to get a small number which will later be used. But this mod line runs for ever and I cannot get an output. For small a and n numbers it works fast. How can I make it work faster?

Here is the part of the code that has to do with my question

while True:
    # Get next line from file
    line = fileHandler.readline()
    plaintext = pow(int(line), a) % n

Upvotes: 0

Views: 883

Answers (2)

Rahul Negi
Rahul Negi

Reputation: 59

The most optimized way i found is :

pow = (a, b, mod) #where mod is you modulo

Example :

 mod = 1000000007
    ans = pow(2, n-1, mod) 
    print(ans)

This is way faster than using :

ans = ((pow(2, n-1) % 1000000007) + 1000000007) % 1000000007 #10 times slower

Upvotes: 0

Alex
Alex

Reputation: 1101

pow can actually take 3 arguments for this case:

pow(int(line), a, n)

According to the docs:

... if z is present, return x to the power y, modulo z (computed more efficiently than pow(x, y) % z).

Upvotes: 1

Related Questions