python-3.x - 11+ 位整数不起作用

Question

我正在使用 python 3 进行小的额外学分分配来编写 RSA 破解程序。老师给了我们一个相当大(大到需要32位以上)的int和公钥。我的代码适用于 < 32 位的素数。我选择 python 3 的原因之一是因为我听说它可以处理任意大的整数。在 python 终端中，我通过做一些小事情来测试这个，比如 2**35 和 factorial(70)。这东西工作得很好。

现在我已经编写了代码，我遇到了溢出错误等问题。为什么对大量数字的操作似乎可以在终端中工作，但在我的实际代码中却不起作用？错误表明它们无法转换为 C 类型，所以我的第一个猜测是，由于某种原因，python 解释器中的内容没有转换为 C 类型，而编码的内容是。有没有办法让这个工作？

作为第一次尝试，我尝试计算 1 到 n(大数)之间所有素数的列表。这种工作直到我意识到列表索引器 [] 只接受整数并在数字高于整数时爆炸。此外，如果 n > 2**32，则创建长度为 n 的数组将不起作用。 (更不用说这将占用的内存)

因此，我转而使用我发现的一个函数，该函数可以非常准确地猜测一个数字是否为素数。这些方法粘贴在下面。

如您所见，我只执行 、*、/和 % 操作。所有这些似乎都可以在解释器中使用，但是与此代码一起使用时出现“无法转换为 c 类型”错误。

def power_mod(a,b,n):
if b < 0:
    return 0
elif b == 0:
    return 1
elif b % 2 == 0:
    return power_mod(a*a, b/2, n) % n
else:
    return (a * power_mod(a,b-1,n)) % n

最后 3 行是无法转换为 c-type 的地方。

下面的函数以非常高的确定性估计一个数是素数。如上所述，我使用它来避免创建大量数组。

def rabin_miller(n, tries = 7):
if n == 2:
    return True

if n % 2 == 0 or n < 2:
    return False

p = primes(tries**2)

if n in p:
    return True

s = n - 1
r = 0
while s % 2 == 0:
    r = r+1
    s = s/2
for i in range(tries):
    a = p[i]

    if power_mod(a,s,n) == 1:
        continue
    else:
        for j in range(0,r):
            if power_mod(a, (2**j)*s, n) == n - 1:
                break
        else:
            return False
        continue
return True

也许我应该通过粘贴错误来更具体:
第 19 行，在 power_mod 中
返回 (a * power_mod(a,b-1,n)) % n
溢出错误:Python int 太大而无法转换为 C double

这是我在执行算术时遇到的错误类型。尝试创建非常大的列表、集合等时会发生 Int 错误

Answer 1

您的问题(我认为)是您正在使用/运算符转换为浮点数。将其更改为//并且您应该留在 int 域中。