# RSA code giving result after more than 10 minutes

I am trying to implement RSA algorithm. I got a code in python. When I run it, it takes more than 10 minutes even when the primes are within 100 and message size is 8 decimal digits. Plese suggest what may be the problem in the code.

# Write Python3 code here
from decimal import Decimal

def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)

p = int(input('Enter the value of p = '))
q = int(input('Enter the value of q = '))
no = int(input('Enter the value of text = '))
n = p * q
t = (p - 1) * (q - 1)

for e in range(2, t):
if gcd(e, t) == 1:
break

for i in range(1, 10):
x = 1 + i * t
if x % e == 0:
d = int(x / e)
break
print('pvt key= ', d)

ctt = Decimal(0)
ctt = pow(no, e)
ct = ctt % n

dtt = Decimal(0)
dtt = pow(ct, d)
dt = dtt % n

print('n = ' + str(n) + ' e = ' + str(e) + ' t = ' + str(t) + ' d = ' + str(d) + ' cipher text = ' + str(
ct) + ' decrypted text = ' + str(dt))

• What primes within 100 are selected? And what are the decimal digits of size 8. It seems impossible that it takes more than 10 minutes. – 孙海城 Jul 11 '20 at 14:17
• If p,q are less than 100 then n is less than 9999, and RSA does not work for messages >= n (or < 0). Also note the primes must be distinct or RSA doesn't work; see the basic definitions in wikipedia. – dave_thompson_085 Jul 12 '20 at 1:18

What we've got here is a so-called naive implementation, which doesn't consider time complexity of power-then-modulo operations involving large integers. I'd recommend you to read up on square and multiply, exponentiation by squaring, binary exponentiation, for a bit of context. Typical naive implementations have O(2m) complexity, while optimised versions could achieve only O(m).

If you replace the commented-out code with the uncommented, you'll get significant execution speed improvements:

# ctt = pow(no, e)
# ct = ctt % n
ct = pow(no, e, n)
...
# dtt = pow(ct, d)
# dt = dtt % n
dt = pow(ct, d, n)


See Python built-in function docs for more details of what I've done.

• The question's code already does multiplication by squaring (or similar), because two-argument pow does. What remains to be gained (which is, a lot) comes mostly from early modular reduction. Wikipedia has an article on modular exponentitaition. If one is really into making things as fast as they can be, there's R. Brent and P. Zimmermann's modern computer artihmetic. – fgrieu Jul 11 '20 at 11:02