无法处理 Python 中的大整数 3

Question

我正在尝试实现一个非常简单的 RSA 算法，当我选择 2 个大于 3 位的素数时，当我尝试解密消息时，我的 IDE 冻结了，我认为是因为它是一个 bigInt所以我等了大约 10 分钟，什么也没发生。

这是我的代码：

def gcd (m,n):
if (m%n ==0):
    return n
else:
    return gcd(n,m%n)

def extended_gcd(aa, bb):
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
          lastremainder, (quotient, remainder) = remainder,      divmod(lastremainder, remainder)
    x, lastx = lastx - quotient*x, x
    y, lasty = lasty - quotient*y, y
return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

def modinv(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
    raise ValueError
return x % m
p = 9883
q = 9887
n = p*q
phi = (p-1)*(q-1)
e = 509

    m = 320

    d = modinv(e,phi)
    c = (pow(m,e)%n) 
    msg = pow(c,d) % n ## MY IDE FREEZES WHEN IT REACHES THIS LINE! SURE OF IT
    print(msg)

Answer 1

您的线路：

c = (pow(m,e)%n)

应该是：

c = (pow(m,e,n))

根据 official documentation，这是一种更有效的计算大数取模的方法

编辑：同样适用于：

msg = pow(c,d) % n

变成：

msg = pow(c,d, n)

关于大小，Python 实际上对整数非常聪明，如果数字变得太大而无法放入传统整数，它会切换内部表示。因此大小通常不是问题

无法处理 Python 中的大整数 3

Can't handle large integers in Python 3

python

encryption

rsa