python 中的 Miller-Rabin 素数测试：为什么我一直得到 decimal.Overflow：[<class 'decimal.Overflow'>]？

Question

我正在尝试在维基百科上做 Miller-Rabin Primality Test in python. I've written the code like below based on pseudocode：

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'>]

我该如何解决这个问题？

Answer 1

显然您使用的是 Python 3，其中 x / y 总是 returns 和 float，即使操作数类型都是 int。 float 表示的内容有限，可能会发生溢出错误。为了执行整数除法，您可以使用 x // y。具体来说，在您的代码中，行 s /= 2 应更改为 s //= 2.

python 中的 Miller-Rabin 素数测试：为什么我一直得到 decimal.Overflow：[<class 'decimal.Overflow'>]？

Miller-Rabin Primality Test in python: Why I keep getting decimal.Overflow: [<class 'decimal.Overflow'>]?

python

primality-test