python中的米勒-拉宾素数测试:为什么我总是得到decimal.Overflow：[<class‘class’十进制。
python中的米勒-拉宾素数测试:为什么我总是得到decimal.Overflow：[<class‘class’十进制。
提问于 2020-03-16 11:07:57
我试图在python中做米勒-拉宾素数检验。我在维基百科上基于伪码编写了如下代码：
from math import *
from numpy import *
def Miller_Rabin(n, k): #Miller-Rabin Primality Test
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
s = n - 1
d = 0
r = 0
while True:
if s % 2 == 0:
r += 1
s /= 2
else:
d = s
break
for i in range(k):
a = random.randint(2, n-1)
t = a**d
x = t % n
if x == 1 or x == n-1:
continue
for j in range(r-1):
x = x**2 % n
if x == n-1:
continue
return False
return True但是，当我运行代码并输入像5336101这样的素数时，我得到了以下错误：
File "C:\Users\kienp\Documents\Math Projects\Primality Test\primality_test.py", line 46, in Miller_Rabin
t = a**d
OverflowError: (34, 'Result too large')因此，我决定使用Decimal模块，修改了几行代码：
- 添加部分：
from decimal import Decimal #Adding
from decimal import Context #Adding- 修改部分：
for i in range(k):
a = random.randint(2, n-1)
t = Decimal(Decimal(a)**Decimal(d))
x = Decimal(t) % n但我又犯了一个错误：
File "C:\Users\kienp\Documents\Math Projects\Primality Test\primality_test.py", line 46, in Miller_Rabin
t = Decimal(Decimal(a)**Decimal(d))
decimal.Overflow: [<class 'decimal.Overflow'>]我怎么才能解决这个问题？
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-03-16 11:15:47
显然，您使用的是Python3，其中x / y总是返回一个float，即使操作数类型都是int。float在所能表示的内容上受限于可能发生的溢出错误。为了执行整数除法，可以使用x // y。具体来说，在您的代码中，s /= 2行应该更改为s //= 2。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/60704831
复制相关文章
相似问题
腾讯云开发者
