11个以上的数字不起作用

Question

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

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

作为第一次尝试,我尝试计算1和n之间所有素数的列表(大数).这种方式有效,直到我意识到列表索引器[]只接受整数并且如果数字高于int则爆炸.此外,如果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 OverflowError:Python int太大而无法转换为C double

这是我在执行算术时得到的错误类型.尝试创建令人难以置信的大型列表,集等时会发生Int错误

Answer 1

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