0

我试图在 python 中进行Miller-Rabin Primality Test 。我根据维基百科上的伪代码编写了如下代码：

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

我怎样才能解决这个问题？

4

1 回答 1

3

显然，您使用的是 Python 3，即使操作数类型都是，也x / y总是返回 a 。它可以表示的内容有限，可能会发生溢出错误。为了执行整数除法，您可以使用. 特别是在您的代码中，该行应更改为.floatintfloatx // ys /= 2s //= 2

于 2020-03-16T11:15:47.270 回答