Тест первичности Миллера-Рабина в python: почему я продолжаю получать десятичные числа. Переполнение: [ ]?

Question

Я пытался сделать тест на примитивность Миллера-Рабина в 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')

Поэтому я решил использовать десятичный модуль, изменив несколько строк кода:

• Добавление части:

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 всегда возвращает float, даже если оба типа операнда int. float ограничено в том, что оно может представлять, из-за ошибки переполнения. Для выполнения целочисленного деления вы можете использовать x // y. В частности, в вашем коде строка s /= 2 должна быть изменена на s //= 2.